Cours

Objectifs du programme officiel :

Divisibilité et division euclidienne

• Divisibilité dans \(\mathbb{Z}\)

• Divisieurs, multiples

• Entiers associés

• Division euclidienne

PGCD et algorithme d'Euclide

• PGCD de deux entiers

• Algorithme d'Euclide

• Relation de Bézout, algorithme d'Euclide étendu

• PPCM

Entiers premiers entre eux

• Couple d'entiers premiers entre eux

• Théorème de Bézout

• Lemme de Gauss

• \([a\wedge b =1, a\mid n, b\mid n] \Longrightarrow ab \mid n\)

• \([a\wedge n = 1, b\wedge n = 1]\Longrightarrow ab \wedge n = 1\)

• Extension à une famille d'entiers, premiers dans leur ensemble, deux à deux, relation de Bézout

Nombres premiers

• Nombre premier

• Crible d'Erathostène

• Infinité de nombres premiers

• Décomposition d'un entier non nul en produits de nombres premiers

• Valuation \(p\)-adique, d'un produit, caractérisation de la divisibilité, PGCD et PPCM en fonction des valuations

Congruence

• Relation de congruence modulo un entier

• Opérations sur les congruences

• Utilisation d'un inverse modulo \(n\) pour résoudre une congruence modulo \(n\)

• Petit théorème de Fermat

I. Divisibilité et division euclidienne

Remarque

Les notions qui peuvent être énoncées dans un anneau plus général que l'anneau des entiers \(\mathbb{Z}\) seront écrites avec un anneau \(A\).

Définition : Divisibilité

On considère un anneau commutatif \(A\) et deux éléments \(a,b\in A\). Alors on dit que l'élément \(a\) divise l'élément \(b\) s'il existe \(c \in A\) tel que \(b = a\times c\). Dans ce cas on le note \(a\mid b\). On dit alors que l'élément \(a\) est un diviseur de l'élément \(b\), ou encore que l'élément \(b\) est un multiple de l'élément \(a\).

Exemple

Remarque

On note \(aA\) l'ensemble des multiples de l'élément \(a\).

Proposition

On considère des éléments \(a,b,c,d\in A\).

• Si \(a\mid b\) et \(a\mid c\) alors \(a \mid bu+cv\) pour tout \(u,v\in A\).

• Si \(a\mid b\) et \(c\mid d\) alors \(ac\mid bd\).

• Si \(a\mid b\) alors \(a^k \mid b^k\) pour tout \(k\in \mathbb{N}\).

Démonstration

Proposition

On considère deux entiers \(a,b \in \mathbb{Z}\).

• \(a \mid b \Longleftrightarrow |a| \mid |b|\).

• Si \(b\neq 0\) et \(a\mid b\) alors \(|a| \leq |b|\).

• Pour tout \(m\in \mathbb{Z}^*\), \(a\mid b\) si et seulement si \(ma\mid mb\).

Démonstration

Remarque

La dernière propriété peut également être énoncé dans un anneau quelconque \(A\) de deux façons différentes :

• Pour tout élement inversible \(m\in A^\times\), \(a\mid b\) si et seulement si \(ma \mid mb\).

• Si l'anneau \(A\) est un corps alors pour tout \(m\in A^*\), \(a\mid b\) si et seulement si \(ma\mid mb\).

Définition : Eléments associés

On considère un anneau commutatif \(A\) et deux éléments \(a,b\in A\). Alors on dit que les éléments \(a\) et \(b\) sont associés si \(a\mid b\) et \(b\mid a\).

Exemple

Une matrice inversible \(A\) de taille \(n\) est associée à la matrice \(I_n\) :

\[I_n = AA^{-1} \quad \text{et} \quad A = I_n A.\]

Proposition : Caractérisation des éléments associés

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors les assertions suivantes sont équivalentes.

• Les entiers \(a\) et \(b\) sont associés.

• Il existe \(\varepsilon \in \{-1,1\}\) tel que \(a = \varepsilon b\).

• \(a\mathbb{Z} = b\mathbb{Z}\).

Démonstration

Exemple

Soit \(a \in \mathbb{Z}\) associé à l'entier \(2\). Alors \(a = \pm 2\).

Théorème : Théorème de la division euclidienne

On considère deux entiers \(a,b \in \mathbb{Z}\) tel que \(b\neq 0\). Alors il existe un unique couple d'entiers \((q,r) \in \mathbb{Z}\), appelés quotient et reste, tel que

\[a = bq+r, \quad 0\leq r<|b|.\]

Démonstration

Remarque

Pour effectuer la division euclidienne en pratique on procède comme en primaire pour poser la division.

Exemple

Nous avons la division euclidienne de \(314\) par \(149\)

\[314 = 149\times 2 + 16.\]

Ou encore la division euclidienne de \(15\) par \(-4\)

\[15 = (-4)\times (-3) + 3.\]

Corollaire

On considère deux entiers \(a,b\in \mathbb{Z}\) tel que \(b\neq 0\). Alors \(b\mid a\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.

Démonstration

Exemple

La division euclidienne de \(126\) par \(7\) donne

\[126 = 7\times 18 + 0.\]

Donc \(7 \mid 128\).

II. PGCD et algorithme d'Euclide

Définition : Ensemble des diviseurs

On considère un entier \(a \in \mathbb{Z}\). Alors on définit \(D_a\) comme l'ensemble des diviseurs de l'entier \(a\).

Exemple

\[D_{10} = \{-10, -5, -2, -1, 1, 2, 5, 10\}.\]

Définition : Ensemble des diviseurs communs

On considère deux entiers \(a,b \in \mathbb{Z}\). Alors on définit \(D_{a,b}\) comme l'ensemble des divieurs communs aux entiers \(a\) et \(b\).

Exemple

\[D_{10,16} = \{-2, -1, 1, 2\}.\]

Proposition

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors

\[D_{a,b} = D_a \cap D_b.\]

Démonstration

Définition : PGCD

On considère deux entiers \(a,b \in \mathbb{Z}\) non tous nuls. Alors le plus grand commun diviseur (PGCD) entre \(a\) et \(b\) est l'unique entier \(d \in \mathbb{N}^*\) tel que \(d\mid a, d\mid b\) et

\[\forall c\in \mathbb{Z}, \quad c\mid a, c\mid b \quad \Longrightarrow \quad c\leq d.\]

On le note alors \(d = a\wedge b\).

Exemple

\[10 \wedge 16 = 2.\]

Remarque

Autrement dit le PGCD \(a\wedge b\) est définit comme le majorant de l'ensemble \(D_{a,b}\) qui est un ensemble non vide \((1\in D_{a,b})\) et majorée (par \(\max(|a|,|b|)\)) de \(\mathbb{Z}\).

Remarque

Par convention on définit également \(0\wedge 0 = 0\).

Proposition

On considère deux entiers \(a,b\in \mathbb{Z}\).

• \(a\wedge 0 = |a|\).

• \(a\wedge b = |a| \wedge |b|\).

• Soit \(r\) le reste de la division euclidienne de \(a\) par \(b \neq 0\). Alors \(a\wedge b = b\wedge r\).

Démonstration

Théorème : Algorithme d'Euclide

On considère deux entiers \(a,b\in \mathbb{Z}\) tels que \(a>b\geq 0\), et la suite \((r_n)_{n\in \mathbb{N}} \in \mathbb{N}^\mathbb{N}\) définie par \(r_0 = a, r_1 = b\) et par, pour tout entier \(n\geq 1\),

• si \(r_n = 0\) alors \(r_{n+1} = 0\),

• si \(r_n \neq 0\) alors \(r_{n+1}\) est le reste de la division euclidienne de \(r_{n-1}\) par \(r_n\).

Alors il existe un premier rang \(n_0 \in \mathbb{N}^*\) tel que \(r_{n_0} = 0\) et

\[a\wedge b = r_{n_0 - 1}.\]

Démonstration

Exemples

Le PGCD entre \(21\) et \(13\) est \(1\) car

\[21 = 13 + 8, \quad 13 = 8 + 5, \quad 8 = 5 + 3, \quad 5 = 3 + 2, \quad 3 = 2 + 1, \quad 2 = 1\times 2 + 0.\]

Remarque

On peut étendre ce résultat à deux entiers \(a,b\in \mathbb{Z}\) non tous nuls. Si \(b>a\) alors on intervertit les rôles des entiers \(a\) et \(b\). Si \(a \leq 0\) (ou \(b\leq 0\)) alors on considère \(-a\geq 0\) (ou \(-b\geq 0\)) à la place car \((-a)\wedge b = a\wedge b\).

Exemple

Le PGCD entre \(-21\) et \(-13\) est également \(1\).

Corollaire

On considère deux entiers \(a,b\in \mathbb{Z}\) non tous nuls. Alors \(D_{a,b} = D_{a\wedge b}\).

Démonstration

Exemple

\[D_{10,16} = \{-2, -1, 1, 2\} = D_2 = D_{10 \wedge 16}.\]

Corollaire

On considère deux entiers \(a,b \in \mathbb{Z}\) non tous nuls et un entier \(c\in \mathbb{Z}\). Alors le PGCD \(a\wedge b\) est le plus grand commun diviseur aux entiers \(a\) et \(b\) au sens de la divisibilité.

Démonstration

Exemple

Proposition

On considère trois entiers \(a,b,k\in \mathbb{Z}\). Alors

\[(ka) \wedge (kb) = |k| (a\wedge b).\]

Démonstration

On note \(d = \(a\wedge b\) et \(D = (ka) \wedge (kb)\). Alors \(d\) divise \(a\) et \(b\), donc \(kd\) divise \(ka\) et \(kb\). Ainsi \(kd\) divise D\) : il existe \(q \in \mathbb{Z}\) tel que

\[(ka) \wedge (kb) = D = kd q.\]

Ainsi \(kdq\) divise \(ka\) et \(kb\), donc \(dq\) divise \(a\) et \(b\), d'où \(dq \mid d \mid dq\) i.e. \(|q| = 1\). Par conséquent

\[(ka) \wedge (kb) = D = |k| d = |k| a\wedge b.\]

Théorème : Relation/idendité de Bézout

On considère deux entiers \(a,b\in \mathbb{Z}\) non tous nuls. Alors il existe deux entiers \(u,v\in \mathbb{Z}\) tels que

\[au+bv = a\wedge b.\]

De plus s'il existe des entiers \(u,v,c\in \mathbb{Z}\) tels que \(au+bv = c\) alors \(a\wedge b \mid c\).

Démonstration

• D'après la proposition suivante il existe \(u,v \in \mathbb{Z}\) tel que \(au+bv = a\wedge b\).

• On suppose qu'il existe \(u,v,c\in \mathbb{Z}\) tels que \(au+bv = c\). Or \(a\wedge b \mid a\) et \(a\wedge b \mid b\) donc

\[a\wedge b \mid au + bv = c.\]

Exemples

Proposition : Algorithme d'Euclide étendu

On considère deux entiers \(a,b \in \mathbb{Z}\) tels que \(a\geq b>0\), et les suites \((r_n)_{n\in \mathbb{N}}, (u_n)_{n\in \mathbb{N}}, (v_n)_{n\in \mathbb{N}} \in \mathbb{N}^\mathbb{N}\) définies par

\[r_0 = a, r_1 = b, \quad u_0 = 1, u_1 = 0, \quad v_0 = 0, v_1 = 1,\]

et par, pour tout entier \(n \in \mathbb{N}^*\),

• si \(r_n = 0\) alors \(r_{n+1} = 0, u_{n+1} = u_n, v_{n+1} = v_n\),

• si \(r_n \neq 0\) alors \(r_{n+1}\) est le reste de la division euclidienne de \(r_{n-1}\) par \(r_n\), et \(u_{n+1}, v_{n+1}\) sont les entiers définis par

\[u_{n+1} = u_{n-1} - q_{n+1} u_n, \quad v_{n+1} = v_{n-1} - q_{n+1} v_n,\]

avec \(q_{n+1}\) le quotient dans la division euclidienne de \(r_{n-1}\) par \(r_n\).

Alors, pour tout \(n\in \{0,..., n_0-1\}\), nous avons

\[r_n = au_n + bv_n.\]

En particulier

\[a\wedge b = r_{n_0-1} = au_{n_0-1} + bv_{n_0-1}.\]

Démonstration

Procédons par récurrence double.

• Pour \(n = 0\) et \(n= 1\) nous avons

\[au_0 + bv_0 = a \times 1 + b\times 0 = a = r_0, \quad au_1 + bv_1 = a\times 0 + b \times 1 = b = r_1.\]

• On suppose le résultat vrai au rangs \(n\in \{1, ..., n_0 - 2\}\) et \(n-1\) :

\[a u_{n-1} + bv_{n-1} = r_{n-1}, \quad au_n + bv_n = r_n.\]

Puis \(r_{n+1}\) est le reste de la division euclidienne de \(r_{n-1}\) par \(r_n\) :

\[r_{n-1} = r_n q_{n+1} + r_{n+1}.\]

Ainsi

\[au_{n+1} + bv_{n+1} = au_{n-1} - a q_{n+1} u_n + b v_{n-1} - b q_{n+1} v_n = r_{n-1} - q_{n+1} r_n = r_{n+1}.\]

• Le théorème de récurrence double permet de conclure.

Exemples

Exemple 1Exemple 2

On considère les entiers 20 et 12. Alors l'algorithme d'Euclide étendu donne le tableau suivant.

\[\begin{array}{|c|c|c|c|c|} \hline n & q_n & r_n & u_n & v_n \\ \hline 0 & \cdot & 20 & 1 & 0 \\ \hline 1 & \cdot & 12 & 0 & 1 \\ \hline 2 & 1 & 8 & 1 & -1 \\ \hline 3 & 1 & 4 & -1 & 2 \\ \hline 4 & 2 & 0 & \cdot & \cdot \\ \hline \end{array}\]

Donc \(20 \wedge 12 = 4\) et une relation de Bézout est

\[4 = (-1) \times 20 + 2 \times 12.\]

Remarque

En pratique pour déterminer une relation de Bézout on ne calcule pas les \(u_n,v_n\) de cette manière. On remonte les calculs effectués lors des divisions euclidiennes.

Exemple

Nous effectuons les divisions euclidiennes successives pour déterminer le PGCD entre \(22\) et \(8\) :

\[22 = 8 \times 2 + 6, \quad 8 = 6 \times 1 + 2, \quad 6 = 2 \times 3 + 0.\]

Donc \(22 \wedge 8 = 2\) et nous remontons les divisions euclidiennes pour déterminer une relation de Bézout :

\[2 = 8 - 6 = 8 - (22 - 8 \times 2) = 8 \times 3 + 22 \times (-1).\]

Définition : PGCD d'une famille d'entiers

On considère des entiers \(a_1, ..., a_n \in \mathbb{Z}\) non tous nuls. Alors le plus grand commun diviseur (PGCD) entre ces entiers \(a_1, ..., a_n\) est la majorant de l'ensemble majoré non vide \(D_{a_1, ..., a_n} = D_{a_1} \cap ... \cap D_{a_n}\). On le note \(a_1 \wedge ... \wedge a_n\).

Exemple

\[D_{10,16, 3} = \{-1, 1\}.\]

Remarque

Nous avons encore la convention \(0 \wedge ... \wedge 0 = 0\).

Proposition : Associativité du PGCD

On considère des entiers \(a, b, c \in \mathbb{Z}\). Alors

\[a\wedge b \wedge c = (a\wedge b) \wedge c = a \wedge (b\wedge c).\]

Démonstration

Théorème : Relation de Bézout

On considère des entiers \(a_1, ..., a_n \in \mathbb{Z}\). Alors il existe des entiers \(u_1, ..., u_n \in \mathbb{Z}\) tels que

\[\sum_{k=1}^n a_k u_k = a_1 u_1 + ... + a_n u_n = a_1 \wedge ... \wedge a_n.\]

Démonstration

Remarque

Pour obtenir le PGCD (respectivement une relation de Bézout) entre \(n\) entiers il suffit d'appliquer récursivement l'algorithme d'Euclide (respectivement l'algorithme d'Euclide étendu) en utilisant l'associativité du PGCD.

Exemple

Algorithme d'EuclideAlgorithme d'Euclide étendu

On condière les entiers 10, 15 et 24. Alors :

• On détermine \(10 \wedge 15\) par l'algorithme d'Euclide : \(15 = 1\times 10 + 5\) puis \(10 = 2\times 5 + 0\) donc \(10\wedge 15 = 5\).

• Nous avons par associtivité \(10\wedge 15 \wedge 24 = 5 \wedge 24\).

• On détermine \(5\wedge 24\) par l'algorithme d'Euclide : \(24 = 4\times 5+4\) puis \(5 = 1\times 4 +1\) puis \(4 = 4\times 1 + 0\) donc \(5\wedge 24 = 1\).

• On conclut que \(10\wedge 15 \wedge 24 = 1\).

On considère les mêmes entiers que précédemment. Alors :

• On détermine une relation de Bézout entre 10 et 15 par l'algorithme d'Euclide étendu :

\[\begin{array}{|c|c|c|c|c|} \hline 0 & \cdot & 15 & 1 & 0 \\ \hline 1 & \cdot & 10 & 0 & 1 \\ \hline 2 & 1 & 5 & 1 & -1 \\ \hline 3 & 2 & 0 & \cdot & \cdot \\ \hline \end{array}.\]

Nous avons donc

\[5 = 10 \wedge 15 = 1\times 15 + (-1) \times 10 = 15 - 10.\]

• Nous avons par associativité \(10\wedge 15 \wedge 24 = 5 \wedge 24\).

• On détermine une relation de Bézout entre 5 et 24 par l'algorithme d'Euclide étendu :

\[\begin{array}{|c|c|c|c|c|} \hline 0 & \cdot & 24 & 1 & 0 \\ \hline 1 & \cdot & 5 & 0 & 1 \\ \hline 2 & 4 & 4 & 1 & -4 \\ \hline 3 & 1 & 1 & -1 & 5 \\ \hline 4 & 4 & 0 & \cdot & \cdot \\ \hline \end{array}.\]

Nous avons donc

\[1 = 5\wedge 24 = (-1) \times 24 + 5 \times 5.\]

• Par conséquent

\[1 = 10 \wedge 15 \wedge 24 = 5 \wedge 24 = 5\times 5 - 24 = 5 \times (15-10) - 24 = 5\times 15 - 5 \times 10 - 24.\]

Définition : PPCM

On considère deux entiers \(a,b\in \mathbb{Z}\) non nuls. Alors le plus petit commun multiple (PPCM) entre les entiers \(a\) et \(b\) est l'unique entier \(m\in \mathbb{N}^*\) tel que \(a\mid m, b\mid m\) et

\[\forall c \in \mathbb{Z}, \quad a\mid c, b\mid c \quad \Longrightarrow \quad m \leq c.\]

On le note alors \(a\vee b = m\).

Exemples

Le PPCM entre \(5\) et \(12\) est \(60\). Celui entre \(12\) et \(15\) est \(60\).

Remarque

Autrement dit il s'agit du minorant de l'ensemble \(a\mathbb{Z} \cap b\mathbb{Z} \cap \mathbb{N}^*\) qui est non vide (\(ab \in a\mathbb{Z} \cap b\mathbb{Z} \cap \mathbb{N}^*\)) et minoré (par 1).

Remarque

Par convention nous avons également \(a\vee 0 = 0\).

Proposition

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors les multiples communs à \(a\) et \(b\) sont exactement les multiples de \(a\vee b\) :

\[a\mathbb{Z} \cap b \mathbb{Z} = (a\vee b) \mathbb{Z}.\]

Démonstration

Proposition

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors leur PPCM est le plus petit élement de \(a\mathbb{Z}\cap b\mathbb{Z} \cap \mathbb{N}^*\) au sens de la divisibilité.

Démonstration

Proposition

On considère trois entiers \(a,b,m\in \mathbb{Z}^*\). Si \(a \mid m\) et \(b\mid m\) alors \(a\vee b \mid m\).

Démonstration

Théorème

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors

\[(a\wedge b) (a\vee b) = |ab|.\]

Démonstration

Exemple

III. Entiers premiers entre eux

Définition : Entiers premiers entre eux

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors on dit que les entiers \(a\) et \(b\) sont premiers entre eux si \(a\wedge b = 1\).

Exemple

Proposition : Fraction irréductible

On considère deux entiers \(a\in \mathbb{Z}\) et \(b\in \mathbb{N}_*\). Alors il existe deux entiers \(a'\in \mathbb{Z}\) et \(b'\in \mathbb{N}^*\) premiers entre eux tel que \(\dfrac{a}{b} = \dfrac{a'}{b'}\). On dit alors que la fracion \(\dfrac{a'}{b'}\) est irréductible.

Démonstration

Exemple

Théorème de Bézout

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors les entiers \(a\) et \(b\) sont premiers entre eux si et seulement s'il existe deux entiers \(u,v\in \mathbb{Z}\) tels que

\[au + bv = 1.\]

Démonstration

Exemple

Théorème : Lemme de Gauss

On considère des entiers \(a,b,c\in \mathbb{Z}\). Si les entiers \(a\) et \(b\) sont premiers entre eux et si \(a\mid bc\) alors \(a\mid c\).

Démonstration

Exemple

Proposition

On considère des entiers \(a,b,c \in \mathbb{Z}\).

• Si les entiers \(a\) et \(b\) sont premiers entre eux et divisent l'entier \(c\) alors \(ab \mid c\) :

\[[a\wedge b = 1, a\mid c, b\mid c] \quad \Longrightarrow \quad ab\mid c.\]

• Si les entiers \(a\) et \(b\) sont premiers avec \(c\) alors l'entier \(ab\) est premier avec \(c\) :

\[[a\wedge c = 1, b\wedge c = 1] \quad \Longrightarrow \quad ab \wedge c = 1.\]

• Si les entiers \(a\) et \(b\) sont premiers entre eux alors les entiers \(a^k\) et \(b^k\) également pour tout \(k\in \mathbb{N}\) :

\[a\wedge b \quad \Longrightarrow \quad \forall k\in \mathbb{N}, a^k \wedge b^k = 1.\]

Démonstration

Exemples

Définitions : Nombres premiers dans leur ensemble ou deux à deux

On considère des entiers \(a_1, ..., a_n\in \mathbb{Z}\) non tous nuls. Alors on dit que les entiers \(a_1, ..., a_n\) sont :

• premiers dans leur ensemble si \(a_1 \wedge ... \wedge a_n = 1\),

• premiers deux à deux si pour tout \(i,j\in \{1, ..., n\}\) distincts, \(a_i \wedge a_j = 1\).

Exemples

Premiers dans leur ensemblePremiers deux à deux

Proposition

On considère des entiers \(a_1, ..., a_n\in \mathbb{Z}\) non tous nuls. Si les entiers \(a_1, ..., a_n\) sont premiers deux à deux alors ils le sont dans leur ensemble. Mais la réciproque n'est pas vérifiée.

Démonstration

Exemple

IV. Nombres premiers

Définition : Nombre premier

On considère un entier naturel \(p\in \mathbb{N}\). Alors on dit que l'entier \(p\) est premier s'il admet exactement deux diviseurs positifs distincts \(1\) et \(p\). On note \(\mathcal{P}\) l'ensemble des nombres premiers.

Exemple

Proposition

On considère un entier \(n\in \mathbb{N}\) et un nombre premier \(p\in \mathcal{P}\). Alors \(p\mid n\) ou \(p\wedge n = 1\).

Démonstration

Théorème : Lemme d'Euclide

On considère deux entiers \(a,b\in \mathbb{Z}\) et un nombre premier \(p\in \mathcal{P}\). Si \(p\mid ab\) alors \(p\mid a\) ou \(p\mid b\).

Démonstration

Proposition

On considère un entier \(n\geq 2\). Alors l'entier \(n\) admet un diviseur premier. De plus si l'entier \(n\) n'est pas premier alors il admet un diviseur premier \(p \leq \sqrt{n}\).

Démonstration

Remarque

Le crible d'Erathostène permet d'obtenir la liste des nombres premiers compris entre \(1\) et \(n\) pour tout \(n\in \mathbb{N}^*\).

L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même).

En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.

On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant.

On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment.

À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à \(n\).

(insérer une image)

Théorème

L'ensemble \(\mathcal{P}\) des nombres premiers est infini.

Démonstration

Théorème : Factorialité des entiers

On considère un entier non nul \(n \in \mathbb{Z}^*\). Alors il existe de façon unique (à l'ordre près) :

• un entier \(r\in \mathbb{N}\),

• une famille d'entiers premiers \(p_1, ..., p_r \in \mathcal{P}\)

• une famille d'entiers non nuls \(\alpha_1, ..., \alpha_r \in \mathbb{N}^*\),

• un entier \(\varepsilon \in \{-1,1\}\),

tels que

\[n = \varepsilon \prod_{i=1}^r p_i^{\alpha_i}.\]

Démonstration

Exemples

Définition

On considère un entier premier \(p\in \mathcal{P}\). Alors la valuation \(p\)-adique est l'application \(\nu_p : \mathbb{Z}^* \longrightarrow \mathbb{N}\) définie par, pour tout \(a\in \mathbb{Z}^*\),

\[\nu_p(a) = \max\{k\in \mathbb{N}, \quad p^k \mid a\}.\]

Exemple

Remarque

Par convention nous avons \(\nu_p(0) = +\infty\).

Proposition

On considère un entier \(n\in \mathbb{Z}\) et un nombre premier \(p\in \mathcal{P}\).

• Pour tout \(k\in \mathbb{N}, \nu_p(n) = k\) si et seulement s'il existe \(q\in \mathbb{Z}\) tel que \(n = p^k q\) et \(p\wedge q = 1\).

• \(\nu_p(n) \geq 1\) si et seulement si \(p\mid n\).

Démonstration

Proposition

On considère un entier non nul \(n\in \mathbb{Z}^*\) de décomposition \(n = \varepsilon \prod_{i=1}^r p_i^{\alpha_i}\). Alors

\[\forall i\in \{1, ..., r\}, \quad \alpha_i = \nu_{p_i}(n).\]

Démonstration

Exemple

Remarque

On peut alors noter la décomposition

\[n = \prod_{p\in \mathcal{P}} p^{\nu_p(n)}.\]

Ce produit a bien du sens même si \(\mathcal{P}\) est infini parce qu'il n'y a qu'un nombre fini de \(\nu_p(n)\) non nuls.

Proposition

On considère deux entiers non nuls \(a,b\in \mathbb{Z}^*\) et un nombre premier \(p\in \mathcal{P}\). Alors

\[\nu_p(ab) = \nu_p(a) \nu_p(b), \quad \nu_p(a+b) \geq \min(\nu_p(a),\nu_p(b)).\]

Démonstration

Exemple

Corollaire

On considère deux entiers \(a,b\in \mathbb{Z}\). Alors \(a\mid b\) si et seulement si \(\nu_p(a) \leq \nu_p(b)\) pour tout \(p\in \mathcal{P}\).

Démonstration

Proposition

On considère deux entiers non nuls \(a,b\in \mathbb{Z}^*\). Alors

\[a\wedge b = \prod_{p\in\mathcal{P}} p^{\min(\nu_p(a),\nu_p(b))}, \quad a\vee b = \prod_{p\in \mathcal{P}} p^{\max(\nu_p(a),\nu_p(b))}.\]

Démonstration

Exemple

V. Congruences

Définition

On considère un entier non nul \(n\in \mathbb{Z}^*\) et deux entiers \(a,b\in \mathbb{Z}\). Alors on dit que les entiers \(a\) et \(b\) sont congrus modulo \(n\) si \(n \mid a-b\) ce que l'on note \(a\equiv b[n]\).

Exemples

Proposition

On considère un entier non nul \(n\in \mathbb{Z}^*\) et des entiers \(a,b,c,d \in \mathbb{Z}\).

• Si \(a\equiv b[n]\) et \(c\equiv d[n]\) alors

\[a+c \equiv b+d[n], \quad ac \equiv bd[n], \quad \forall k\in \mathbb{N}, a^k \equiv b^k[n].\]

• Pour tout \(m\in \mathbb{Z}^*, a \equiv b[n]\) si et seulement si \(ma \equiv mb [mn]\).

• \(a\equiv 0[n] \Longleftrightarrow n\mid a\).

• Si \(r\) est le reste de la division euclidienne de \(a\) par \(n\) alors \(a\equiv r[n]\).

Démonstration

Exemples

Proposition

La relation de congruence modulo \(n\in \mathbb{Z}^*\) définit une relation d'équivalence sur \(\mathbb{Z}\).

Démonstration

Définition : Inverse modulaire

On considère un entier non nul \(n\in \mathbb{Z}^*\) et un entier \(a \in \mathbb{Z}\). Alors on dit que l'entier \(a\) admet un inverse modulo \(n\) s'il existe un entier \(b\in \mathbb{Z}\) tel que \(ab \equiv 1 [n]\).

Proposition

On considère un entier non nul \(n\in \mathbb{Z}^*\) et un entier \(a \in \mathbb{Z}\). Alors l'entier \(a\) admet un inverse modulo \(n\) si et seulement si les entiers \(a\) et \(n\) sont premiers entre eux.

Démonstration

Exemple

Proposition

On considère un entier non nul \(n\in \mathbb{Z}^*\) et un deux entiers \(a,b\in \mathbb{Z}\). Si l'entier \(a\) admet un inverse modulo \(n\), que l'on note \(a^{-1}\), alors l'équation

\[ax = b [n]\]

admet une unique solution modulo \(n\) donnée par

\[x = a^{-1} b [n],\]

autrement dit les solutions sont exactement de la forme

\[x_k = a^{-1} b + kn.\]

Démonstration

Exemple

Proposition

On considère deux entiers \(a,b\in \mathbb{Z}\) et un nombre premier \(p\in \mathcal{P}\). Alors

\[(a+b)^p \equiv a^p + b^p [p].\]

Démonstration

On montre d'abord que, pour tout \(k\in \{1, ..., p-1\}\), le coefficient binomial \(\binom{p}{k}\) est un multiple de \(p\) grâce à l'égalité

\[\binom{p}{k} = \dfrac{p}{k} \binom{p-1}{k-1}.\]

Remarque

La proposition précédente sert à montrer que l'application \(\varphi : a \longmapsto a^p\) est un morphisme d'anneau modulo \(p\), appelé morphisme de Frobenius.

Théorème : Petit théorème de Fermat

On considère un entier premier \(p\in \mathcal{P}\) et un entier \(a \in \mathbb{Z}\). Alors \(a^p \equiv a [p]\). De plus si l'entier \(a\) n'est pas divisible par le nombre premier \(p\) alors \(a^{p-1} \equiv 1 [p]\).

Démonstration

Exemple