Tag Archives: arithmétique

Le théorème de Wilson

Posted on by
7

Le théorème de Wilson est un résultat très connu d’artihmétique élémentaire, qui donne une caractérisation anecdotique des nombres premiers.

Dans cet article, je rappellerai les démonstrations connues et vous présenterai une démonstration un peu plus étonnante (et très anecdotique) basée sur le théorème de Sylow en théorie des groupes.

Historique

Le théorème de Wilson a été découvert par Ibn al-Haytham (aussi connu comme Alhazen) vers les années 1000, mais est attribué à John Wilson (un étudiant de Edward Waring) qui l’a conjecturé au dix-huitième sicècle. C’est Waring qui publia la conjecture 1770, mais sans démonstration. La première preuve est dûe à Lagrange, et a été publiée en 1773. Il semblerait que Leibniz connaissait le résultat un siècle plus tôt, mais ne l’a jamais publié.

Théorème de Wilson

Un entier naturel p>1 est premier si et seulement si

(p-1)!+1 \equiv 0 \pmod p

Cette caractérisation des nombres premiers est un peu anecdotique et ne constitue pas un test de primalité utile (calculer la factorielle de p-1 n’est pas envisageable). Son principal intérêt réside dans son histoire et la simplicité de son énoncé et de ses preuves (exceptée bien entendu celle dont je vais parler en dernier et qui justifie l’existence de cet article).

Démonstration du sens réciproque

Commençons par démontrer que si (p-1)!+1\equiv 0\pmod p, alors p est premier. Supposons que cette équation est vraie, cela signifie qu’il existe k\in\mathbf Z tel que

kp-(p-1)!=1

Ainsi, on a une relation de Bezout entre p et 1<\ell <p, donc p est premier.

Démonstration du sens direct

par Lagrange

Notons \mathbf F_p=\mathbf Z/p\mathbf Z. C’est un corps et le groupe \mathbf F_p^\times de ses inversibles est d’ordre p-1. Ainsi, le petit théorème de Fermat implique que ses p-1 éléments sont racines du polynôme X^{p-1}-1\in\mathbf F_p[X] de degré p-1. Comme \mathbf F_p est un corps, et que les éléments 1\leq \ell < p sont racines de ce polynôme, on a

X^{p-1}-1=(X-1)(X-2)\cdots(X-(p-1)).

En évaluant cette expression en p, on trouve le résultat voulu.

par Gauss

Si p=2, le résultat est clair. On suppose donc p impair.

Le principe de cette jolie démonstration est de grouper deux par deux les éléments de \mathbf F_p^\times. Pour tout k\in\mathbf F_p^\times, k\neq 1, -1, il existe \ell\in \mathbf F_p^\times, \ell\neq k (sinon k^2=1, i.e., k\in\left\{-1,1\right\} ce qu’on a justement exclu) tel que k\ell =1. Ainsi, lorsqu’on élimine, dans le produit \prod_{1\leq k\leq p-1}k\in\mathbf F_p, les paires d’inverses mutuels dont le produit vaut 1, il ne reste que

\prod_{1\leq k\leq p-1}k = 1\times (p-1) = -1 \in \mathbf F_p,

ce qui prouve le résultat.

… par le théorème de Sylow

Commençons par dénombrer le nombre de p-Sylow du groupe symétrique \mathfrak S_p

Dans \mathfrak S_p, il y a (p-1)! éléments d’ordre p. En effet, un élément d’ordre p est un p-cycle car p est premier, et un p-cycle peut s’écrire avec n’importe quel élément en premier, et c’est l’ordre des p-1 éléments restants qui importe.

Maintenant, un p-Sylow est de cardinal p^\alpha maximal avec p^\alpha qui divise le cardinal de \mathfrak S_p. Ainsi, \alpha=1 et les p-Sylow sont d’ordre p, et contiennent l’identité et p-1 p-cycles. Réciproquement, chaque p-cycle est contenu dans un p-Sylow. Il y a donc

\frac{(p-1)!}{p-1}=(p-2)! p-Sylow.

Avec le théorème de Sylow…

on sait que le nombre de p-Sylow est congru à 1 modulo p. Ainsi

(p-2)!\equiv 1\pmod p,

et en multipliant par p-1, on a

(p-1)!\equiv p-1\equiv -1\pmod p.

Petit mot de la fin

J’aime bien cette dernière démonstration pour deux raisons. La première, c’est qu’elle relie les sous-groupes de Sylow avec un théorème d’arithmétique élémentaire, ce qui prouve (si besoin est encore) qu’en mathématiques il n’y a jamais qu’un seul moyen de prouver les choses. La seconde est que les étudiants, face au dénombrement des p-Sylow de \mathfrak S_p, utilisent immédiatement le théorème de Sylow et restent bloqué avec

n_p\equiv 1\pmod p,

où n_p est le nombre de p-Sylow. Là, il faut remettre les mains dans le cambouis pour s’en sortir. De plus, ce n’est pas un exercice difficile.

L’historique et les premières démonstrations sont tirées de la page sur le théorème de Wilson de la wikipédia.

Entiers et probabilité

Posted on by
2

Voilà un résultat fort intéressant :

Soient a et b deux entiers naturels non nuls inférieurs à n!. En notant p_n la probabilité que a et b soient premiers entre eux, on a

\lim_{n \to +\infty} p_n= \frac{6}{\pi^2} \approx 61\%.

C’est-à-dire que la « probabilité » que deux entiers soient premiers entre eux est de 6/\pi^2. Mais il faut faire attention avec ce mot, comme nous le verrons plus bas !

On rappelle que n!=1\times 2\times 3 \times \cdots \times n.

La fonction zêta de Riemann

Une fonction très connue en théorie des nombres est la fonction zêta de Riemann, notée \zeta. Sur les entiers supérieurs ou égaux à 2, elle est définie par :

\zeta(n)=1+\frac{1}{2^n}+\frac{1}{3^n}+\cdots=\sum_{k=1}^{+ \infty} \frac{1}{k^n}.

Ce qui est remarquable, c’est qu’elle est fortement reliée aux nombres premiers à travers la formule suivante :

\zeta(n)=\left( \frac{1}{1-1/2^n}\right)\left( \frac{1}{1-1/3^n}\right)\left( \frac{1}{1-1/5^n}\right)\cdots=\prod_{p \in \mathbb P} \frac{1}{1-1/p^n}

où l’on fait le produit sur tous les nombres premiers.

Un autre fait remarquable, c’est que la valeur de \zeta(2) est connue :

\zeta(2)=\sum_{k=1}^{+\infty} \frac{1}{k^2}=\frac{\pi^2}{6}.

Pour des démonstrations de ces résultats, on pourra se reporter aux articles produit eulérien et problème de Bâle sur Wikipédia.

Pourquoi ce « n! » ?

On peut se demander pourquoi on demande que les deux entiers a et b soient bornés par n! Tout simplement parce qu’il n’existe pas de mesure de probabilité uniforme sur l’ensemble \mathbb N des entiers naturels, ce qui empêche de parler de probabilité sur les entiers directement. Une loi uniforme est la seule qui modélise correctement le fait de prendre des objets au hasard, car elle associe la même probabilité à chaque élément.

Plus formellement, si on disposait d’une mesure de probabilités uniforme \mu sur \mathbb N, alors on aurait d’une part \mu(\mathbb N)=1, mais aussi \mu(\{n\})=\varepsilon pour tout n. Or c’est impossible, car on a

1=\mu(\mathbb N)=\mu\left( \bigcup_{n \in \mathbb N} \{n\} \right)=\sum_{n =0}^{+\infty} \mu(\{n\})=\sum_{n =0}^{+\infty} \varepsilon.

Si \varepsilon=0, on aurait 1=0 et si \varepsilon>0 on aurait 1=+\infty, absurde.

Il est donc incorrect de parler de probabilité que deux entiers soient premiers entre eux. Le résultat énoncé plus haut n’en reste pas moins intéressant.

Démonstration

Soit p un nombre premier inférieur à n. Notons A_p l’évènement p n’est pas un diviseur commun de a et b.

La probabilité pour que a soit divisible par p est de 1/p. En effet, le nombre k de multiples de p dans \{1,\ldots,n!\} vérifie

n!-p < kp\leq n!

c’est-à-dire

\frac{n!}{p}-1 < k \leq \frac{n!}{p}.

Or n! est divisible par p, donc n!/p est un entier. Le nombre k étant lui-même un entier, on a nécessairement k=n!/p.

La proportion (et donc la probabilité que a soit divisible par p) d’entiers divisibles dans \{1,\ldots,n!\} est donc de

\frac{k}{n!}=\frac{n!/p}{n!}=\frac{1}{p}.

On refait le même raisonnement pour b. Par indépendance sur les choix de a et b, la probabilité que a et b soient tous les deux divisibles par p est de 1/p^2. La probabilité de l’événement A_p est donc de 1-1/p^2.

L’événement B_n : « a et b sont premiers entre eux » est se produit quand ils n’ont pas de facteurs commun, c’est-à-dire quand les événements A_i sont tous réalisés en même temps. On a donc

p_n=P(B_n)=P\left( \bigcap_{p \leq n!} A_p\right)

et par indépendance

p_n=\prod_{p \leq n!} P(A_p)=\prod_{p \leq n!} \left(1-\frac{1}{p^2}\right)

d’où en passant à la limite sur n :

\lim_{n \to +\infty} p_n = \frac{1}{\zeta(2)}=\frac{6}{\pi^2}

ce qui achève la démonstration.

Pour aller plus loin

On peut raffiner le théorème en travaillant avec n plutôt qu’avec n! mais la démonstration est plus difficile.