ช่วยคิดหน่อยครับ

[Panithi Vanasirikul]

จงหาเศษจากการหาร $1+3^1+3^2+...+3^{98}$ จาก $101$ อ่ะครับ

[FranceZii Siriseth]

เพราะว่า $101$ เป็นจำนวนเฉพาะ
$3^{101-1} \equiv 1 \pmod{101}$
$(3-1)(3^{99}+3^{98}+3^{97}+...+3+1)\equiv 0 \pmod{101}$
เพราะเหตุว่า $101\nmid 2$ ดังนั้น $101\mid 3^{99}+3^{98}+3^{97}+...+3+1$

$3^{98}+3^{97}+...+3+1 \equiv -3^{99} \pmod{101} $

แทนค่าเรื่อยๆ พบว่า
$3^{25} \equiv 10 \pmod{101} $
$3^{50} \equiv 100 \equiv -1 \pmod{101} $
$3^{75} \equiv -10 \pmod{101}$
ทำต่อดูครับ ได้ เศษ $67$

[Panithi Vanasirikul]

mod กับเครื่องหมาย สามขีดนั่นคืออะไรครับ คือผมยังไม่ได้เรียนเลยอ่ะครับ ไปเจอในข้อสอบเก่าเข้ากำเนิดวิทย์เลยลองถามอ่ะครับ

[FranceZii Siriseth]

$a \equiv b \pmod{c}$ หมายความว่า $a$ และ $b$ แต่ละตัวเมื่อหารด้วย $c$ จะเหลือเศษเท่ากัน
เครื่องหมาย $\equiv$ อ่านว่าคอนกรูเอนซ์

$Fermat's$ $Little$ $Theorem$ $a^{p-1} \equiv 1 \pmod {p}$ เมื่อ $p$ เป็นจำนวนเฉพาะ

[FranceZii Siriseth]

ลองอ่านบทความจากเว็บนี้ดูครับ http://www.vcharkarn.com/vblog/36819

[Panithi Vanasirikul]

อ่านเเล้วงงอ่ะครับ อย่างเช่นว่าทำไมเศษจากการหาร 3^101-1=1 อ่ะครับ มีวิธีอธิบายอื่นมั้ยครับ

[Thgx0312555]

อ่านอันนี้ก็ได้นะ http://www.mathcenter.net/forum/showthread.php?t=11249 ของคุณbanker
แต่จริงๆช้อแบบนี้มีวิธีสวยๆที่ใช้ Fermat อย่างเดียวอยู่ครับ

ก่อนอื่น พิจารณาว่า $2(1+3+3^2+\cdots+3^{98})=3^{99}-1$
แต่โดย Fermat Little Theorem $3^{100} \equiv 1 \pmod {101}$

$3\times 3^{99} \equiv 1 \pmod {101}$
จะเห็นว่าอยู่ในรูป
$3A \equiv 1 \pmod {101}$

ก็จะเป็นการแก้สมการคอนกรูเอนซ์ ซึ่งลองแก้แบบนี้ก็ได้ ก่อนอื่นพิจารณาว่า $1+101 =3\times 41$ ซึ่งหารด้วย $3$ ลงตัว

$3A \equiv 102 \pmod {101}$
$3A \equiv 3 \times 34 \pmod {101}$
จะได้ $A \equiv 34 \pmod {101}$ จาก $(3,101)=1$ (เป็นสมบัติคอนกรูเอนซ์)

$3^{99} \equiv 34 \pmod {101}$
ซึ่งถ้าทำแบบบข้อความข้างบนต่อก็จะได้ $1+3+3^2+\cdots+3^{98} \equiv -3^{99} \equiv -34 \equiv 67 \pmod {101}$

ดังนั้นก็จะตอบเหลือเศษ $67$

แต่ถ้าอยากลองฝึกใช้เทคนิคแบบนี้ต่ออีกที ก็ลองทำต่อ จาก
$2(1+3+3^2+\cdots+3^{98})=3^{99}-1 \equiv 33 \equiv -68 \pmod {101}$
$1+3+3^2+\cdots+3^{98} \equiv -34 \pmod {101} \quad ((2,101)=1)$
หรือ
$1+3+3^2+\cdots+3^{98} \equiv 67 \pmod{101}$
ได้คำตอบเท่ากันครับ

วิธีนี้ทำจริงๆก็ถือว่าสั้นครับ

[FranceZii Siriseth]

สั้นมากๆเลยครับวิธีของพี่ Thgx0312555 ขอบคุณครับ

[tngngoapm]

$1+3^1+3^2+...+3^{98}=\frac{(3^{99}-1)}{2}$
เศษที่ได้จากการหาร $1+3^1+3^2+...+3^{98}$ ด้วย $101$ = เศษที่ได้จากการหาร $\frac{(3^{99}-1)}{2}$ ด้วย $101$
เศษที่ได้จากการหาร $\frac{(3^{99}-1)}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(3^8)^{12}\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(6561)^{12}\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(-4)^{12}\cdot 3^3-1}{2}$ ด้วย $101$.....[$101$ หาร ุ$6561$ ได้เศษ $97$ ซึ่งเสมือนว่าเศษ $(-4)$
=เศษที่ได้จากการหาร $\frac{4^{12}\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(4^5)^2\cdot 4^2\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(1024)^2\cdot 16\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(14)^2\cdot 4^2\cdot 3^3-1}{2}$ ด้วย $101$....[$101$ หาร ุ$1024$ ได้เศษ $14$]
=เศษที่ได้จากการหาร $\frac{196\cdot 16\cdot 3^3-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(-6)\cdot 16\cdot 3^3-1}{2}$ ด้วย $101$....[$101$ หาร ุ$196$ ได้เศษ $95$ เสมือนว่าเศษ $(-6)$]
=เศษที่ได้จากการหาร $\frac{(-2592)-1}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $\frac{(-67)-1}{2}$ ด้วย $101$...[$101$ หาร ุ$2592$ ได้เศษ $67$]
=เศษที่ได้จากการหาร $\frac{(-68)}{2}$ ด้วย $101$
=เศษที่ได้จากการหาร $(-34)$ ด้วย $101$
=เศษ $(-34)$........[เศษ $(-34)$ คือเศษ $67$]
เศษคือ $67$