Re: [代數] 數論問題~

[jeromeshih (以謹慎態度來面對問題)]

提供另外一個想法參考(不過時代有點久遠,如有有誤也請指正)

因為任意整數次方除以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
→ suhorng     :最後那邊我很好奇 假若 n非質數, a跟n不互質,
→ suhorng     :乘一乘最後也是一定得循環的,
→ suhorng     :不過有辦法算什麼時候會循環嗎?
→ jeromeshih  :樓上可以查一下代數coset的說法
→ jeromeshih  :以除6所得餘數來舉例,與6互質的{1,5}會循環
→ jeromeshih  :剩下的集合會是2{1,5}={2,4},3{1,5}={3},循環不會超
→ jeromeshih  :過比較小集合的個數,但要較仔細證明須參考大學代數