Re: [代數] 數論問題~
(之前小弟打過費瑪小定理的數歸法證明在批兔個板，就直接複製貼過來囉XDDD)
--
p
Fermat's little theorem : a ≡ a (mod p) , for p is a prime number
a is an arbitrary integer
Proof by Mathemetical Induction Theorem
Consider a = 1 , 1 ≡ 1 (mod p) for all p , holds .
p
Assume a = k , k ≡ k (mod p) for all p , holds .
p
When a = k + 1 , ( k + 1 )
p p p p-1 P P
= C k + C k + ......... + C k + C 1
0 1 p-1 0
p p-1 p
Because p | ( C k + ......... + C k )
1 p-1
(上式是需要證明的，但因為不太難證，這裡就略過XD)
p p
Therefore , ( k + 1 ) ≡ k + 1 ≡ k + 1 (mod p) , holds .
This proves the theorem .
--
然後順便補一下 a=0 和 a為負數 的證明
Consider a = 0 , it's trivial .
Consider a < 0
2 2
If p = 2 , a = (-a) ≡ (-a) ≡ a (mod 2) ( where (-a) > 0 )
If p is other prime numbers , then p must be odd .
p p p
→ a = -(-a) = (-1)(-a) ≡ (-1)(-a) = a (mod p)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.35.243
※ 編輯: jellyfishing 來自: 123.194.35.243 (10/08 02:43)
推
10/08 08:37, , 1F
10/08 08:37, 1F
討論串 (同標題文章)