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

$\dfrac{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} \ {\dfrac{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