การหารลงตัว

[dan1689]

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

Find all odd n such that $ n\mid 3^n +1 $

[ฟินิกซ์เหินฟ้า]

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

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

Find all odd n such that $ n\mid 3^n +1 $

จาก $n \mid 3^n+1$ จะได้ว่า $ gcd (n,3)=1$ เพราะถ้า $3 \mid n$ จะได้ $3 \mid 1$ ขัดแย้ง

ถ้า $n=1$ แล้ว $1\mid 4$ จะหา $ n>1$ ซี่ง $ n\mid 3^n +1 $

ให้ $p$ เป็นจำนวนเฉพาะที่น้อยที่สุด ซึ่ง $p \mid n$ จะได้ $n=pk ,\exists k$

จะได้ว่า $gcd(k,p-1)=1$ เพราะ $p-1$ มีค่าน้อยกว่าทุกๆจำนวนเฉพาะที่หาร $n$ ลงตัว

จาก $n \mid 3^n+1$ ได้ $\displaystyle 3^{pk} \equiv -1 \pmod{p} $ หรีอ $\displaystyle (3^p)^k \equiv -1 \pmod{p} $

จาก Fermat's theorem จะได้ $3^p \equiv 3 \pmod{p} $ เมื่อ $p \not= 3$

ดังนั้น $3^k \equiv -1 \pmod{p} $ จะได้ $3^{2k} \equiv 1 \pmod{p} $

ให้ $d$ เป็นจำนวนเต็มท่ี่น้อยที่สุด ซึ่ง $3^d \equiv 1 \pmod{p} $ (order)

ดังนั้น $d \mid 2k$ แต่จาก Fermat's theorem $3^{p-1} \equiv 1\pmod{p} $

ดังนั้น $d \mid p-1$ และ $d \mid 2k$

แต่จาก $gcd(k,p-1)=1$

ดังนั้น $d \mid 2$ จะได้ $d=1,2$ แทนค่ากลับไปใน $3^d \equiv 1 \pmod{p} $

จะได้ $p=2$ แต่โจทย์ต้องการ $p$ เป็น odd จีงไม่มี $ n>1$ ซี่ง $ n\mid 3^n +1 $

$\therefore$ $n=1$ เท่านั้น

[Thgx0312555]

$n$ ไม่จำเป็นต้องหาร $\binom{n}{k}$ นะครับ ระวังด้วย

[Thamma]

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

$n$ ไม่จำเป็นต้องหาร $\binom{n}{k}$ นะครับ ระวังด้วย

ขอบคุณมากค่ะ

การพิสูจน์ว่าไม่มี odd n > 1 ที่ $ n \mid 3^n +1 $

$ n \mid 3^n +1 $
$ n \mid (3^n +1) (3^n -1) $
$ n \mid 9^n -1,\; n>1 $

ให้ P(n) เป็นข้อความ $ n\mid 9^n -1 , \; n > 1 $
และ n เป็นจำนวนเต็มบวกที่น้อยที่สุด ที่สอดคล้องกับเงื่อนไข
ถ้ามีจำนวนเต็มบวก d < n ที่สอดคล้องกับ P(n), นั่นคือ $ d \mid 9^d -1 , \; d >1 $
จะขัดแย้งกับข้อกำหนดที่ว่า n เป็นจำนวนเต็มบวกที่น้อยที่สุด
ทำให้สรุปได้ว่า ไม่มีจำนวนเต็มบวก n > 1 ที่สอดคล้องกับเงื่อนไขนี้

เนื่องจาก n ไม่เป็นพหุคูณของ 3 , ดังนั้น (9,n) = 1

โดย Euler theorem, $ 9^ {\phi (n)} \equiv 1 \bmod n , \; \phi (n) < n $ , for all n

ให้ $ d = ( \phi (n), n ) $

ดังนั้น $ d \leq \phi (n) < n , \;d \mid \phi (n) $ และ $ d \mid n $

จาก $ 9^{\phi (n)} \equiv 1 \bmod n $ และ $ d \mid \phi (n) $ ทำให้ $ 9^d \equiv 1 \bmod n $ ..... พิสูจน์ได้

( d > 1 เพราะ $ n \not\mid 8 $ )

และจาก $ n\mid 9^d -1$ และ $ d\mid n $ , ทำให้ $ d\mid 9^d -1 $