Re: [代數] 數論問題~
提供另外一個想法參考(不過時代有點久遠,如有有誤也請指正)
因為任意整數次方除以p之後可以分成餘1,2...,p-1(不為p整除,所以不可能餘0)
以下假設p不為2的情形
1.也可利用鴿籠原理證出可切割成有限多個,因為多的那一個一定落在餘1,2,...,p-1內
2.假設在m≠1,使得a^(p-1)≡m(mod p)
(i)a≡p-1≡-1 (mod p)
因為p-1為偶數,所以a^(p-1)≡1 (mod p)
(ii)a≡1(mod p) (trivial case)
(iii)假設a不為p-1,亦不為1,不存在k<p-1,使得a^k≡1(mod p),
設r>p-1,a^r≡1(mod p)
所以元素a,...,a^p-1,...,a^r,有超過p-1的數不重疊(矛盾)
(iv)假設a不為p-1,亦不為1,存在k<p-1,使得a^k≡1(mod p)
(a)k整除p-1,設p-1=kh
(a^k)^h≡1≠m≡a^(p-1) (mod p)(矛盾)
(b)k不整除p-1
{a,a^2,...,a^k} a{a,a^2,...,a^k},...,a^t{a,a^2,...,a^k}
會導致超出p-1個數(矛盾)
由1.2,可得出a^(p-1)≡1(mod p)
費馬小定理有點類似循環的概念(或者想像數字在裡面跳格子)
但因為質數的特殊性(只能被1和自己整除),導致循環是有限的,
因此如果隨著數字往上跳卻沒到1,最後會多出原先不預期的數字出現矛盾,因此得證
存在k<p-1,使得a^k≡1(mod p)敘述與a^n≡a^m (mod p)敘述等價
類似想法還可以推到
a^ψ(n)≡1 mod n,(a.n)=1
ψ(n)為尤拉函數,為和n互值的個數和
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.164.224.107
→
10/12 17:54, , 1F
10/12 17:54, 1F
→
10/12 17:54, , 2F
10/12 17:54, 2F
→
10/12 17:54, , 3F
10/12 17:54, 3F
→
10/13 01:26, , 4F
10/13 01:26, 4F
→
10/13 01:27, , 5F
10/13 01:27, 5F
→
10/13 01:29, , 6F
10/13 01:29, 6F
→
10/13 01:29, , 7F
10/13 01:29, 7F
討論串 (同標題文章)