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.

Hello,

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

is an integer.

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

If we take

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

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,

c) Let's prove it by induction.

step 1 - for x = 0

This is trivial to notice that

Step 2 - we assume that this is true for k

meaning

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

We use the results of b)

and we use the induction hypothesis to say

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

Thank you

step-by-step explanation:

hjkj