ทฤษฎีจำนวน เรื่อง คอนกรูเอนซ์

[pont494]

1.จงแแสดงว่า $561\mid (2^{561}-2)$ และ $561\mid (3^{561}-3)$

2.ให้ $p$ เป็นจำนวนเฉพาะซึ่ง $p>5$ จงพิสูจน์ว่า จะมีสมาชิกในลำดับ $9,99,999,...$ เป็นจำนวนไม่จำกัดที่มี $p$ เป็นตัวหาร

3.ถ้า $p$ เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $(p-1)!+1=p^k$ สำหรับจำนวนเต็ม $k$ บางตัว ก็ต่อเมื่อ $p=2,3$ หรือ $5$

4.จงพิสูจน์ว่า $(p-1)!\equiv (p-1)(mod$ $1+2+3+?+(p-1))$ เมื่อ $p$ เป็นจำนวนเฉพาะ

5.ให้ $p$ เป็นจำนวนเฉพาะและ $h+k = p-1$ เมื่อ $h\geqslant 0$ และ $k\geqslant 0 $
จงพิสูจน์ว่า $h!k!+(-1)^h\equiv 0(mod$ $p)$

[FranceZii Siriseth]

ข้อ 2 $a_{n}=10^n-1$
เมื่อ $p>5$ $gcd(10,p)=1,10^{p-1} \equiv 1\pmod{p} $
เลือก $n=p-1$

[tngngoapm]

ผมทำวิธีทำการลดรูปลงไปเรื่อยๆ......ดังนี้ครับ
$561|2^{561}-2$
$561|(2^{9})^{62}(2^{3})-2$
$561|(-49)^{62}(8)-2$..............[561 หาร $2^{9}$ เสมือนได้เศษ $(-49)$]
$561|(49)^{62}(8)-2$
$561|(49^{2})^{31}(8)-2$
$561|(157)^{31}(8)-2$..............[561 หาร $49^{2}$ ได้เศษ $157$]
$561|(157^{2})^{15}(157)(8)-2$
$561|(-35)^{15}(1256)-2$...........[561 หาร $157^{2}$ เสมือนได้เศษ $(-35)$]
$561|-(35^{3})^{5}(1256)-2$
$561|-(239)^{5}(134)-2$............[561 หาร $35^{3}$ ได้เศษ $239$ และ 561 หาร $1256$ ได้เศษ $134$]
$561|-(239^{2})^2(239)(134)-2$
$561|-(-101)^{2}(49)-2$............[561 หาร $239^{2}$ เสมือนได้เศษ $(-101)$ และ 561 หาร $(239)(134)$ ได้เศษ $49$]
$561|-(101)^{2}(49)-2$
$561|-(103)(49)-2$...........[561 หาร $101^{2}$ ได้เศษ $103$]
$561|(-5049)$............ได้ $(-9)$ ลงตัว
แสดงว่า..........$561|2^{561}-2$.......จริง

[FranceZii Siriseth]

ข้อ 4 ทำแบบนี้ได้หรือปล่าวครับ

1.กรณี $p=2$ แสดงได้โดยไม่ยาก
2.กรณี $p>2$ จะได้ว่า $2\nmid p$ จะได้ว่า $2 \mid p-1$
$(p-1)!\equiv p-1 \pmod{\frac{p(p-1)}{2}}$

เพราะว่า $gcd(p,\frac{p-1}{2})=1$ ดังนั้น $p,\frac{p-1}{2}$ ไม่มีตัวประกอบร่วมกัน


$(p-1)!-(p-1)\equiv 0\pmod{\frac{p(p-1)}{2}}$
$(p-1)((p-2)!-1) \equiv 0\pmod{\frac{p(p-1)}{2}}$

เห็นได้ชัดว่า $\frac{p-1}{2}\mid p-1$ และ จะแสดงว่า $(p-2)!-1 \equiv 0 \pmod{p}$

จาก Wilson's Theorem $(p-1)!\equiv -1 \pmod{p}$
$(p-1)!\equiv p-1 \pmod{p}$
$(p-1)!-(p-1)\equiv 0 \pmod{p}$
$(p-1)((p-2)!-1) \equiv 0\pmod{p}$

เพราะว่า $p \nmid p-1$ จะได้ว่า $p\mid (p-2)!-1$ ดังนั้น $(p-2)!-1 \equiv 0 \pmod{p}$

[mathwarrior]

ข้อ 1 ต้องใช้ความรู้เรื่อง Fermat's little theorem ครับ (สามารถศึกษาได้ในหนังสือ สอวน. ครับ)
จาก $(3,2) = 1$ โดย Fermat's little theorem ได้ว่า
$2^{3-1} \equiv 1 ( mod 3 )$
$2^{2} \equiv 1 ( mod 3 )$
$\therefore 2^{560} \equiv 1 ( mod 3 )$
$\therefore 2^{561} \equiv 2 ( mod 3 )$ $--- (1)$

จาก $(11,2) = 1$ โดย Fermat's little theorem ได้ว่า
$2^{11-1} \equiv 1 ( mod 11 )$
$2^{10} \equiv 1 ( mod 11 )$
$\therefore 2^{560} \equiv 1 ( mod 11 )$
$\therefore 2^{561} \equiv 2 ( mod 11 )$ $--- (2)$

จาก $(17,2) = 1$ โดย Fermat's little theorem ได้ว่า
$2^{17-1} \equiv 1 ( mod 17 )$
$2^{16} \equiv 1 ( mod 17 )$
$\therefore 2^{560} \equiv 1 ( mod 17 )$
$\therefore 2^{561} \equiv 2 ( mod 17 )$ $--- (3)$

จาก $(1) , (2) , (3)$ $\therefore 2^{561} \equiv 2 ( mod [3 , 11 , 17] )$
$\therefore 2^{561} \equiv 2 ( mod 561 )$
สรุปได้ว่า $561 \left|\,\right. 2^{561} - 2$

จาก $3 \left|\,\right. 3(3^{560} - 1) = 3^{561} - 3$
$\therefore 3^{561} \equiv 3 ( mod 3 )$ $--- (4)$

จาก $(11,3) = 1$ โดย Fermat's little theorem ได้ว่า
$3^{11-1} \equiv 1 ( mod 11 )$
$3^{10} \equiv 1 ( mod 11 )$
$\therefore 3^{560} \equiv 1 ( mod 11 )$
$\therefore 3^{561} \equiv 3 ( mod 11 )$ $--- (5)$

จาก $(17,3) = 1$ โดย Fermat's little theorem ได้ว่า
$3^{17-1} \equiv 1 ( mod 17 )$
$3^{16} \equiv 1 ( mod 17 )$
$\therefore 3^{560} \equiv 1 ( mod 17 )$
$\therefore 3^{561} \equiv 3 ( mod 17 )$ $--- (6)$

จาก $(4) , (5) , (6)$ $\therefore 3^{561} \equiv 3 ( mod [3 , 11 , 17] )$
$\therefore 3^{561} \equiv 3 ( mod 561 )$
สรุปได้ว่า $561 \left|\,\right. 3^{561} - 3$

[Scylla_Shadow]

ข้อความเดิมเขียนโดยคุณ mathwarrior

ข้อ 1 ต้องใช้ความรู้เรื่อง Fermat's little theorem ครับ (สามารถศึกษาได้ในหนังสือ สอวน. ครับ)
จาก $(561,2) = 1$ โดย Fermat's little theorem ได้ว่า
$2^{561-1} \equiv 1 ( mod 561 )$
$2^{561} \equiv 2 ( mod 561 )$
$\therefore 561 \left|\,\right. (2^{561} - 2)$

จาก $(561,3) = 1$ โดย Fermat's little theorem ได้ว่า
$3^{561-1} \equiv 1 ( mod 561 )$
$3^{561} \equiv 3 ( mod 561 )$
$\therefore 561 \left|\,\right. (3^{561} - 3)$

สวัสดีค่ะ
จำนวน 561 ไม่ใช่จำนวนเฉพาะค่ะ
สวัสดีค่ะ

[Napper]

ข้อความเดิมเขียนโดยคุณ pont494

5.ให้ $p$ เป็นจำนวนเฉพาะและ $h+k = p-1$ เมื่อ $h\geqslant 0$ และ $k\geqslant 0 $
จงพิสูจน์ว่า $h!k!+(-1)^h\equiv 0(mod$ $p)$

ข้อ 5 เป็นโจทย์ค่อนข้างง่ายนะครับ แค่ต้องมองให้ออกนิดนึง
เริ่มจาก Wilson's theorem ดูครับ
$$(p-1)! \equiv -1 \pmod{p}$$
ซึ่งตรงนี้เราแตกออกมาเป็นสองก้อน
$$\Big[ (p-1)(p-2) \cdots (k+1) \Big] \cdot k! \equiv -1 \pmod{p}$$
ซึ่ง $p-1 \equiv -1 \pmod{p}$ และตัวอื่นๆก็เช่นกัน จึงได้ว่า
$$\Big[ (-1)(-2) \cdots (-p+(k+1)) \Big] \cdot k! \equiv -1 \pmod{p}$$
เราก็จะได้ว่าในวงเล็บก้ามปู ตัวสุดท้ายคือ $-h$ นั่นเอง แสดงว่าในวงเล็บคือ $(-1)^{h} \cdot h!$ ดังนั้น
$$(-1)^{h} \cdot h!k! \equiv -1 \pmod{p}$$
ซึ่งสามารถจัดรูป และสมมูลกับสิ่งที่โจทย์ต้องการครับ

หมายเหตุ : เนื่องจาก $h+k=p-1$ ซึ่งเป็นเลขคู่ ดังนั้นตัวยกกำลังของ -1 จะเป็น h หรือ k ก็ได้ครับ มีค่าเท่ากัน