Question 6222: Use the binomial theorem and mathematical induction to show the following. Let p be a prime. Then for any integer a, we have a^p =a (mod p). The "=" sign should be congruence. I need help, I have no idea what they want.
Answer by khwang(438)   (Show Source):
You can put this solution on YOUR website! Proof by Math. Ind. a^p = a mod p for any (fixed prime p) (**)
Basic:when a = 1, a^p = 1 mod p = a mod p.
So, (**) is true for a = 1.
Inductive Hypothesis, assume that when a = k,(**) is true.
That is, k^p = k mod p
Conside, (k+1)^p = E C(p,i) k^i (i =0,..,p)
[E means summation,by the binomial Theorem]
since p is a prime, for any i , 1 <= i <= p-1, p is a divisor of C(p,i),
hence C(p,i) = 0 mod p for such i.
So, we have C(p,i) k^i = 0 mod p, for all 1 <= i <= p-1
Hence, (k+1)^p = E C(p,i) k^i = k^p + 1 mod p = (k + 1) mod p.
[ by the induction hypothesis]
This means (**) is true for a = k+1 and the inductive proof is complete.
This is an important fact about prime numbers . It is an direct result
about the group Zp.
Kenny
|
|
|
