ถ้า $n \mid a^n - 1$, พิสูจน์ $ a + 1 $, $ a^2 + 2 $, …, $ a^n + n $ มีความชัดเจน $ \bmod n $.
ฉันได้ลองแก้ไขปัญหาต่อไปนี้:
ปล่อย $ a $ และ $ n $ เป็นจำนวนธรรมชาติสองตัว $ n \mid a^n - 1 $. พิสูจน์ว่า$ a + 1 $, $ a^2 + 2 $, ... , $ a^n + n $ มีความชัดเจน $ \bmod n $.
ฉันกำลังคิดเกี่ยวกับการเหนี่ยวนำ (ชัดเจน) อาจจะเป็นลำดับขององค์ประกอบ (ทฤษฎีจำนวนพื้นฐาน) ฉันไม่มีความคิดที่จะทำตาม ปัญหานี้ได้รับเลือกให้เป็นหลักสูตรคณิตศาสตร์สำหรับเด็กจากหนังสือ:
<< การเหนี่ยวนำทางคณิตศาสตร์: วิธีการพิสูจน์ที่ทรงพลังและสง่างาม >> Andreescu Titu, Crișan Vlad, XYZ Press, 2017
คำตอบ
นี่เป็นคำถามที่ค่อนข้างน่าสนใจและเป็นคำถามที่ค่อนข้างท้าทายสำหรับหลักสูตรคณิตศาสตร์สำหรับเด็ก ถ้า$n = 1$แล้วใด ๆ $a$ ทำงานให้ $a + 1 \equiv 0 \pmod{1}$. มิฉะนั้นสำหรับ$n \gt 1$ชุดขั้นตอนต่อไปนี้จะแสดงโดยใช้คำสั่งทวีคูณมีชุดของปัจจัยที่ลดลงของ $n$ จนถึง $a \equiv 1$โมดูโลปัจจัยบางอย่าง เริ่มกับ$m_1 = n$ และ $r = 1$.
- ถ้า $a \equiv 1 \pmod{m_r}$, ชุด $j = r$ และออกจากขั้นตอนชุดนี้
- ให้ลำดับการคูณของ$a$ โมดูโล $m_r$ เป็น $m_{r+1} = \operatorname{ord}_{m_{r}}(a) \gt 1$. ตั้งแต่$a^{m_r} \equiv 1 \pmod{m_r}$แล้ว $m_{r+1} \mid m_{r}$. พร้อมด้วย$a^{m_{r+1}} \equiv 1 \pmod{m_{r}}$ซึ่งหมายความว่า $a^{m_{r+1}} \equiv 1 \pmod{m_{r+1}}$. นอกจากนี้ด้วยฟังก์ชัน totient ของออยเลอร์ตั้งแต่นั้นเป็นต้นมา$m_{r+1} \mid \varphi(m_r)$ และ $\varphi(m_r) \lt m_r$, คุณได้รับ $m_{r+1} \lt m_{r}$.
- เพิ่มขึ้น $r$ และไปที่ขั้นตอนที่ #$1$.
ตั้งแต่ละ $m_r$ กำลังลดลง แต่ต้องเป็น $\gt 1$ขั้นตอนข้างต้นจะต้องออกในที่สุดกล่าวคือมี $j \ge 1$. ชุดขั้นตอนต่อไปนี้จะแสดงสำหรับแต่ละขั้นตอน$m_r \; \forall \; 1 \le r \le j$ ว่าแต่ละ $a^i + i \; \forall \; 1 \le i \le m_r$ ไม่เหมือนใคร $\bmod m_r$.
- จากขั้นตอนที่ #$1$, ตั้งแต่ $a \equiv 1 \pmod{m_j}$, คุณมี $a^{i} + i \equiv 1 + i \pmod{m_j} \; \forall \; i$. ซึ่งหมายความว่า$a^i + i \; \forall \; 1 \le i \le m_{j}$ มีความชัดเจน $\bmod m_j$. ชุด$r = j$.
- ถ้า $r = 1$, ตั้งแต่ $m_1 = n$ออกจากขั้นตอนเหล่านี้
- สำหรับใด ๆ $k \ge 1$พิจารณาใด ๆ $s \gt k$ ที่ไหน $a^{k} + k \equiv a^{s} + s \pmod{m_{r-1}}$. โปรดทราบว่าต้องมีความสอดคล้องกันโมดูโล$m_r$ ตั้งแต่ $m_r \mid m_{r-1}$. ตั้งแต่$a^{i} + i \; \forall \; 1 \le i \le m_{r}$ มีความแตกต่างกันทั้งหมด $\bmod m_r$แล้ว $s \equiv k \pmod{m_{r}}$. ด้วยประการฉะนี้$s = qm_{r} + k$ สำหรับจำนวนเต็ม $q \ge 1$. การใช้$a^{m_{r}} \equiv 1 \pmod{m_{r-1}}$แล้ว $a^{s} + s \equiv a^{qm_{r} + k} + qm_{r} + k \equiv a^k + qm_{r} + k \pmod{m_{r-1}}$. สิ่งนี้ให้$qm_{r} \equiv 0 \pmod{m_{r-1}}$กล่าวคือสำหรับบางคน $t \ge 1$, คุณมี $s = tm_{r-1} + k$. ซึ่งหมายความว่าค่าจะซ้ำกัน$m_{r-1}$ดังนั้น $a^{i} + i \; \forall \; 1 \le i \le m_{r-1}$ จะต้องแตกต่างกัน $\bmod m_{r-1}$.
- การลดลง $r$ และไปที่ขั้นตอนที่ #$5$.
ตั้งแต่ $r$ จะลดลงทุกครั้งที่ขั้นตอน #$7$, $r$ ในที่สุดก็ต้องกลายเป็น $1$ ดังนั้นขั้นตอนจะออกที่ขั้นตอน #$5$โดยได้ผลลัพธ์ตามที่อธิบายไว้ในขั้นตอนที่ #$4$ หรือสิ้นสุดขั้นตอนที่ #$6$กล่าวคือแต่ละ $a^{i} + i \; \forall \; 1 \le i \le n$ มีความชัดเจน $\bmod n$.
ตัวอย่างคือ $n = 18$ และ $a = 5$. สิ่งนี้ให้$m_1 = 18$, $m_2 = 6$ และ $m_3 = 2$ดังนั้น $j = 3$.
สังเกตลูปในขั้นตอนที่ #$1$ ถึง $3$ เพิ่มขึ้น $r$ ทุกครั้งในขณะที่วนซ้ำในขั้นตอนที่ #$5$ ถึง $7$ ลดลง $r$ทุกครั้งทำให้ทั้งคู่คล้ายกับการเหนี่ยวนำ (ฉันเลือกที่จะใช้ลูปแทนเนื่องจากฉันคิดว่ามันจะง่ายกว่าที่จะอธิบายและเข้าใจได้ง่ายกว่าการใช้การเหนี่ยวนำที่มีเงื่อนไขพิเศษต่างๆในการตรวจสอบ) นี่เป็นไปได้ว่าทำไมคำถามจึงรวมอยู่ในหนังสือเกี่ยวกับการอุปนัยทางคณิตศาสตร์