Question

Let p be a prime number. The following exercises lead to a proof of Fermat's Little Theorem, which we prove by another method in the next chapter. a) For any integer k with 0 ≤ k ≤ p, let (p k) = p!/k!(p - k)! denote the binomial coefficient. Prove that (p k) 0 mod p if 1 ≤ k ≤ p - 1. b) Prove that for all integers x, y, (x + y)^p x^? + y^p mod p.c) Prove that for all integers x, x^p x mod p.

Answer 1

Hello,

a) We know the binomial coefficients are all integers, so

`(p!)/(k!(p-k)!)`

is an integer.

And we can notice that the numerator p! is divisible by p.

If we take
`1\leq k\leq (p-1)`

It means that k! does not contain p, and we can say the same for (p-k)!

So, we have no p at the denominator so the binomial coefficient is divisible by p, meaning this is 0 modulo p.

b) We can write that

`\displaystyle (x+y)^p=\sum_(i=0)^(p) \ {(p!)/(i!(p-i)!)x^(p-i)y^i`

We use the result from question a) and the binomial coefficients are 0 modulo p for i=1,2 , ... p-1 so there are only two terms left and then,

`(x+y)^p=x^p+y^p \text{ modulo p}`

c) Let's prove it by induction.

step 1 - for x = 0

This is trivial to notice that

`0^p=0 \text{ modulo p}`

Step 2 - we assume that this is true for k

meaning
`k^p=k \text{ modulo p}`

and we need to prove that this is true for the k+1

We use the results of b)

`(k+1)^p=k^p+1^p=k^p+1 \text{ modulo p}`

and we use the induction hypothesis to say

`(k+1)^p=k^p+1^p=k^p+1=k+1 \text{ modulo p}`

And it means that this is true for k+1

Step 3 - conclusion

We have just proved by induction the Fermat's little theorem.

p a prime number, for for all x integers

`\Large \boxed{\sf \bf x^p=x \textbf{ modulo p}}`

Thank you