Les Nombres Premiers

1. L'ensemble des nombres premiers

Définition

Soit \(p\) un entier naturel supérieur ou égal à \(2\).

On dit que \(p\) est premier si il possède exactement deux diviseurs distincts, un et lui-même.

Remarques

• En d'autres termes \(p\) n'est divisible que par un et par lui-même.

• \(1\) n'est pas un nombre premier.

• Cette définition peut être étendue aux entiers relatifs.

• Ne pas confondre nombre premier et nombres premiers entre eux.

Définition

Tout nombre non premier strictement supérieur à 1 est appelé nombre composé.

Propriété

Soit \(n\) un entier supérieur ou égal à \(2\). Alors :

\(n\) admet au moins un diviseur premier.

Si \(n\) n'est pas premier, il admet au moins un diviseur premier \(p\) tel que \(p \leqslant \sqrt{n}\).

Preuve

Si \(n\) est premier, il suffit de dire que \(n\) est un diviseur de \(n\).

Supposons que \(n\) soit un nombre composé. Il existe donc un diviseur de \(n\) autre que \(1\) et \(n\).

Notons \(a\) le plus petit des diviseurs de \(n\) autres que \(1\) et \(n\). (\(a\) existe car l'ensemble de ces nombres est une partie non vide de \(\mathbb{N}\)).

Supposons que \(a\) soit lui aussi un nombre composé.

Alors il existe un diviseur \(d\) de \(a\) différent de \(1\) tel que \(d < a\).

Mais comme \(d\) divise \(a\) et \(a\) divise \(n\) alors \(d\) divise \(n\).

On a donc trouvé un diviseur de \(n\) plus petit que le plus petit des diviseurs de \(n\). Ce qui est absurde.

Donc \(a\) est un nombre premier.

Soit \(a\) un entier naturel non premier strictement supérieur à 1.

Soit \(n\) un diviseur premier de \(a\). On peut écrire \(a=n \times k\) avec \(k \in \mathbb{N}^*\).

On a  \(k \neq 1\)  puisque \(a\) qui n'est pas premier ne peut pas être égal à \(n\) qui est premier.

Donc \(k > 1\).

Si  \(n \leq \sqrt{a}\) ,  alors \(n\) est un diviseur premier de \(a\) inférieur ou égal à \(\sqrt{a}\).

Si \(n > \sqrt{a}\) ,  alors \(n \times k > k\sqrt{a}\)    c'est-à-dire \(a > k\sqrt{a}\) donc \(k < \sqrt{a}\).

\(k\) est donc un diviseur de \(a\) inférieur à \(\sqrt{a}\).

\(k\) étant strictement supérieur à \(1\), il a un diviseur premier \(p\)  et on sait que  \(p \leq k\)   donc \(p \leq \sqrt{a}\).

\(p\) étant un diviseur de \(k\) et \(k\) un diviseur de \(a\), on en déduit que \(p\) est un diviseur de \(a\).

\(p\) est donc un diviseur premier de \(a\) inférieur ou égal à \(\sqrt{a}\).

Dans tous les cas on a donc trouvé un diviseur premier de \(a\) inférieur ou égal à \(\sqrt{a}\).

Le crible d'Eratosthène est un moyen de trouver tous les nombres premiers inférieurs à un entier \(N\) donné.

Grâce à la seconde assertion de ce théorème on peut utiliser un test d'arrêt dans le crible d'Eratosthène.

Principe

On inscrit tous les entiers inférieurs à \(N\) dans un tableau.

On barre le 1 qui n'est pas premier.

2 est un nombre premier on ne le barre pas.

On barre alors tous les multiples de 2.

Le premier nombre non barré est 3. 3 est un nombre premier on barre alors tous les multiples de 3.

Le premier nombre non barré est 5 qui est premier. En effet il n'est multiple d'aucun des nombres qui le précède. On barre alors tous les multiples de 5.

Le premier nombre non barré qui suit est lui aussi un nombre premier. On barre alors tous ces multiples.

Il suffit de s'arrêter lorsque l'on a barré tous les multiples de l'entier \(p\) premier tel que \(p \leqslant \sqrt{N}\).

Preuve

Si un entier \(k\) non barré de la liste possède un facteur premier \(p\) strictement supérieur à \(\sqrt{N}\) alors \(k = pq\).

Si \(q\) est premier alors forcément \(q > \sqrt{N}\)  sinon on aurait déjà barré \(k\) comme multiple de \(q\).

Donc \(k = pq \> \sqrt{N} \times \sqrt{N} = N\). Ce qui contredit le fait que \(k\) soit un entier de la liste. Donc \(p \leqslant \sqrt{N}\).

Exemple :

Trouver tous les nombres premiers inférieurs à 170.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100
101	102	103	104	105	106	107	108	109	110
111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130
131	132	133	134	135	136	137	138	139	140
141	142	143	144	145	146	147	148	149	150
151	152	153	154	155	156	157	158	159	160
161	162	163	164	165	166	167	168	169	170

Théorème

L'ensemble des nombres premiers est infini.

preuve

Nous allons raisonner par l'absurde.

Supposons que l'ensemble des nombres premiers est fini. Notons cet ensemble \(\left\{p_1;p_2;...;p_n\right\}\)

Considérons l'entier \(p=p_1 \times p_2 \times ... \times p_n +1\) donc \(p \notin \left\{p_1;p_2;...;p_n\right\}\).

Comme \(p\) est strictement supérieur à 1, il admet donc un diviseur premier: c'est à dire qu'il existe une valeur \(k\) telle que \(p_k\) divise \(p\).

Or \(p_k\) divise \(p\) et divise \(p_1p_2...p_n\) donc divise 1 ce qui est absurde.

L'ensemble des nombres premiers est donc infini.

2. Décomposition en produit de facteurs premiers

Théorème

Soit \(n\) un entier naturel supérieur ou égal à 2.

Alors \(n\) s'écrit de manière unique sous la forme \(p_1^{\alpha_1} \times p_2^{\alpha_2} \times ... \times p_k^{\alpha_k}\) où \(p_1\), \(p_2\), \(...\), \(p_k\) sont des nombres premiers tels que \(p_1<p_2<...<p_k\) et \(\alpha_1\), \(\alpha_2\), \(...\), \(\alpha_k\) sont des entiers naturels non nuls.

Remarque

Une telle écriture de \(n\) s'appelle décomposition en produit de facteurs premiers.

Nous allons démontrer l'existence de cette décomposition mais admettre l'unicité.

Preuve

Soit \(n\) un entier naturel quelconque. Nous allons démontrer que cet entier \(n\) (et donc tous les entiers puisque ce \(n\) est quelconque) se décompose en produit de facteurs premiers.

Si \(n\) est premier, \(n\) se décompose en un seul facteur premier : lui-même.

Si \(n\) n'est pas premier, il admet au moins un diviseur premier \(p\) et : \(n=p \times d_1\), avec \(1 < p < n\) et \(1 < d_1 < n\).

Si \(d_1\) est un nombre premier on a décomposé \(n\) en produit de deux facteurs premiers.

Si \(d_1\) n'est pas premier, \(d_1\) admet au moins un diviseur premier \(p'\) et : \(d_1=p' \times d_2\), avec \(1 < p' < d_1\) et \(1 < d_2 < d_1\).

On a alors \(n=p \times p' \times d_2\).

Les entiers \(d_1\), \(d_2, \ldots\) forment une suite strictement décroissante d'entiers naturels. On continue alors le procédé jusqu'à ce que le quotient soit égal à 1. On a alors la décomposition de \(n\) en produit de facteurs premiers.

3. Nombres premiers et divisibilité

Pgcd

Théorème

si la décomposition en facteurs premiers de l'entier \(n\) est \(p_1^{\alpha_1} \times p_2^{\alpha_2} \times ... \times p_k^{\alpha_k}\) alors tout diviseur de \(n\) s'écrit sous la forme \(p_1^{\beta_1} \times p_2^{\beta_2} \times...\times p_k^{\beta_k}\) avec \(\forall i \in [\![1;k]\!], \beta_i \in \mathbb{N}\) et \(0 \leqslant \beta_i \leqslant \alpha_i\).

preuve

Considérons un entier \(n\) dont la décomposition en facteurs premiers est \(p_1^{\alpha_1} \times p_2^{\alpha_2} \times...\times p_k^{\alpha_k}\). Soit \(d\) un diviseur de \(n\).

Considérons un nombre premier \(p\) de la décomposition de \(d\), en produit de facteurs premiers, et \(\beta\) l'exposant de \(p\) dans cette décomposition.

\(p\) étant un diviseur de \(d\) et \(d\) un diviseur de \(n\), \(p\) est un diviseur de \(n\).

Par unicité de la décomposition en produit de facteurs premiers, \(p\) est un nombre premier de la décomposition de \(n\) en produit de facteurs premiers. Notons \(\alpha\) l'exposant de \(p\) dans cette décomposition.

Alors \(n=d \times q=(p^{\beta}a)q\) avec \(a\) et \(q\) deux entiers.

On a \(n=(p^{\beta}a)q\). Si \(p\) n'apparaît pas dans la décomposition de \(q\) en produit de facteurs premiers alors \(\alpha=\beta\).

Si \(p\) apparaît dans la décomposition de \(q\) en produit de facteurs premiers avec l'exposant \(\gamma\) on a alors \(\alpha=\beta+\gamma\) et donc \(\alpha>\beta\). Dans tous les cas on a montré que \(\alpha \geqslant \beta\).

Réciproquement : soit \(n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times...\times p_k^{\alpha_k}\) et \(d = p_1^{\beta_1} \times p_2^{\beta_2} \times...\times p_k^{\beta_k}\) avec \(\forall i \in [1;k], \beta_i \in \mathbb{N}\) et \(0 \leqslant \beta_i \leqslant \alpha_i\).

Alors \(n = p_1^{\alpha_1-\beta_1} \times p_2^{\alpha_2-\beta_2} \times...\times p_k^{\alpha_k-\beta_k} \times d\) et comme \(0 \leqslant \beta_i \leqslant \alpha_i\) alors \(p_1^{\alpha_1-\beta_1} \times p_2^{\alpha_2-\beta_2} \times...\times p_k^{\alpha_k-\beta_k} \in \mathbb{N}\) donc \(d\) divise \(n\).

Théorème

Soient \(a\) et \(b\) deux entiers supérieurs ou égaux à deux se décomposant sous la forme :

\(a = p_1^{\alpha_1} \times p_2^{\alpha_2} \times...\times p_k^{\alpha_k}\) et \(b = p_1^{\beta_1} \times p_2^{\beta_2} \times...\times p_k^{\beta_k}\) où \(p_1\), \(p_2\), \(...\) , \(p_k\) sont des nombres premiers et \(\alpha_1\), \(\alpha_2\), ...,\(\alpha_k\), \(\beta_1\), \(\beta_2\), \(...\), \(\beta_k\) des entiers naturels éventuellement nuls.

Alors \(pgcd(a;b)=p_1^{min(\alpha_1,\beta_1)} \times p_2^{min(\alpha_2,\beta_2)} \times...\times p_k^{min(\alpha_k,\beta_k)}\)

Preuve

Posons \(a = p_1^{\alpha_1} \times p_2^{\alpha_2} \times...\times p_k^{\alpha_k}\) et \(b = p_1^{\beta_1} \times p_2^{\beta_2} \times...\times p_k^{\beta_k}\) où où \(p_1\), \(p_2, \ldots , p_k\) sont des nombres premiers.

Tout diviseur commun à \(a\) et \(b\) est donc de la forme \(p_1^{\omega_1} \times p_2^{\omega_2} \times ... \times p_k^{\omega_k}\) avec \(\forall i \in [\![1;k]\!], \beta_i \in \mathbb{N}\) \(0 \leqslant \omega_i \leqslant \alpha_i\) et \(0 \leqslant \omega_i \leqslant \beta_i\) donc \(0 \leqslant \omega_i \leqslant min(\alpha_i,\beta_i)\).

Le plus grand diviseur commun à \(a\) et \(b\) s'obtient donc en prenant la plus grande valeur de possible d'où :

\(pgcd(a ; b) =p_1^{min(\alpha_1,\beta_1)} \times p_2^{min(\alpha_2,\beta_2)} \times...\times p_k^{min(\alpha_k,\beta_k)}\)

Divisibilité par un nombre premier

Théorème

Tout nombre premier est premier avec tout entier qu'il ne divise pas.

Remarque

Le théorème précédent n'est pas explicitement au programme mais sa démonstration peut faire l'objet d'une question préliminaire dans un exercice. Il pourra alors ensuite être utilisé.

Théorème

\(p\) est un nombre premier qui divise le produit \(ab\) de deux entier naturels \(a\) et \(b\). Alors \(p\) divise \(a\) ou \(p\) divise \(b\).

Théorème

\(p\) est un nombre premier qui divise le produit \(ab\) de deux nombres premiers \(a\) et \(b\).

Alors \(p = a\) ou \(p = b\).

Le petit théorème de Fermat

Théorème

\(p\) est un nombre premier et \(a\) un entier non divisible par \(p\). Alors \(a^{p-1} \equiv 1 [p]\).

Corollaire

Si \(p\) est un nombre premier et \(a\) un entier quelconque, alors \(a^{p}-a\) est divisible par \(p\).

Preuve

Commençons par démontrer le résultat préliminaire suivant si \(p\) est un nombre premier alors \(p\) est premier avec \((p-1)!\).

\(p\) étant premier il est premier avec \(1\) ; \(2\) ; \(3\) ; ... ; \((p - 1)\) , sinon \(p\) admettrait un diviseur positif autre que \(1\) et \(p\). Donc \(p\) est premier avec \((p-1)!\).

Si \(k\) est un entier tel que \(1 \leq k \leq p - 1\), alors le reste \(r_k\) de la division de \(ka\) par \(p\) est non nul. En effet si \(p\) divise \(ka\) alors \(p\) divise \(a\) car \(p\) est premier avec \(k\). Or ceci est absurde par hypothèse.

Si \(k'\) est un entier distinct de \(k\) par exemple, \(k < k'\) tel que \(1 \leq k \leq p - 1\), alors les restes \(r_k\) et \(r_{k'}\) des divisions respective de \(ka\) et \(k'a\) par \(p\) sont distincts. En effet si \(r_{k'} = r_k\) alors \(p\) divise \(k'a - ka\), c'est à dire \((k - k')a\) avec \(1 \leq k' - k \leq p - 1\) . Ce qui est absurde car \(a\) n'est pas divisible par \(p\).

Ainsi les \(p-1\) restes \(r_1\), \(r_2\), \(...\), \(r_{p-1}\) des divisions respectives de \(a\), \(2a\), \(...\) ,\((p-1)a\) par \(p\) sont donc des entiers naturels non nuls strictement inférieurs à \(p\) et tous distincts. Donc l'un des restes est égal à \(1\), l'autre à \(2\), ... , l'autre à \(p-1\).

D'où en utilisant le produit des congruences : \(a(2a)...((p-1)a) \equiv r_1r_2...r_{p-1} [p]\)

C'est à dire : \((p-1)!a^{p-1} \equiv (p-1)! [p]\)

Donc \(p\) divise \((p-1)!a^{p-1}-(p-1)!\) d'où \(p\) divise \((p-1)!(a^{p-1}-1)\).

Or \(p\) premier avec \((p-1)!\) donc \(p\) divise \(a^{p-1}-1\) d'après le théorème de Gauss.

Exercice :

Démontrer que \(12^6 + 6\) est divisible par \(7\).

Corollaire

\(p\) désigne un nombre premier et \(a\) un entier naturel.

Alors \(a^p - a\) est divisible par \(p\), c'est à dire \(a^p \equiv a[p]\).

Exercice :

Démontrer le corollaire ci-dessus.