1. On montre par récurrence sur k que $ \forall k \in N $, $ 0 < k < p $ : $ \binom{n}{k} $ est divisible par p.
Initialisation pour k=1 :
$ \binom{n}{k} = \frac{n!}{(n-1)!}=n $
Or, tout nombre supérieur à deux admet un diviseur premier (la flemme de le redémontrer, je l'admet, mais sinon par récurrence forte)
D'où p|n, et la
propriété est vérifiée au rang 1.
Hérédité :Supposons que $ p|\binom{n}{k} $pour un entier naturel k fixé. Démontrons que $ p|\binom{n}{k+1} $
Montrons tout d'abord que $ (n+1)!\equiv 0\pmod p $
En effet, par hypothèse, $ p|\binom{n}{k} $ donc $ \frac{n!}{k!(n-k)!}\equiv 0\pmod p $ et $ n!\equiv 0\pmod p $ d'où $ (n+1)!\equiv 0\pmod p $.
De plus, par hypothèse, $ p|\binom{n}{k} $ donc $ p|\binom{n+1}{k+1}-\binom{n}{k+1} $ et $ \frac{n+1!}{(k+1)!(n-k)!}-\frac{n!}{(k+1)!(n-k-1)!}\equiv 0\pmod p $
Comme $ (n+1)!\equiv 0\pmod p $, $ \frac{n!}{(k+1)!(n-k-1)!}\equiv 0\pmod p $ et $ p|\binom{n}{k+1} $.
La propriété est donc héréditaire.
Conclusion : $ \forall k \in N $, $ 0 < k < p $ : $ p|\binom{n}{k} $
2. On cherche à montrer (toujours) par récurrence sur x que $ p|x^p-x $.
Initialisation pour x=0 :
$ 0^p-0=0 $
et $ p|0 $
La propriété est vérifiée au rang 0.
Hérédité :Supposons que $ p|x^p-x $ pour un entier naturel x fixé. Démontrons que $ p|(x+1)^p-(x+1) $
Remarquons que $ (x+1)^p= x^p +\sum_{k=1}^{p} x^{p-k} 1^k $ d'après le binôme de Newton. Or, $ \sum_{k=1}^{p} x^{p-k} 1^k $ est divisible par $ \binom{p}{k} $, qui est lui même divisible par p pour tout k<p.
Pour k = p, $ \sum_{k=0}^{p} x^{p-k} 1^k = 1 $, d'où $ \sum_{k=1}^{p} x^{p-k} 1^k \equiv 1\pmod p $.
Ainsi, par hypothèse, $ x^p\equiv x\pmod p $ d'où $ x^p +\sum_{k=1}^{p} x^{p-k} 1^k \equiv x+1\pmod p $ et $ (x+1)^p - (x+1) \equiv 0\pmod p $
La propriété est donc héréditaire.
Conclusion : $ \forall k \in N $, $ p|x^p-x $
3. Soient x et premiers entre eux.
$ p|x^p-x \Leftrightarrow x^p \equiv x\pmod p $
Comme x et p sont premiers entre eux, alors x est inversible modulo p. On note u son inverse.
$ x^p \equiv x\pmod p \Rightarrow x^p.u \equiv x.u\pmod p \Rightarrow x^{p-1} \equiv 1\pmod p $.
Réciproquement, si $ x^{p-1} \equiv 1\pmod p $ alors par multiplication $ x^p \equiv x\pmod p $.
D'où le petit théorème de Fermat.
