Chapitres Maths en MPSI, PCSI, MP2I, PTSI

Cours en ligne Maths en Maths Sup

Chapitres Maths en MPSI, PCSI, MP2I, PTSI

Cours : Arithmétique en Maths Sup en MPSI, PCSI et PTSI

Résumé de cours Exercices et corrigés

Cours en ligne de Maths en Maths Sup

Résumé de cours et méthodes – Maths sup Arithmétique

Plan :

1. Divisibilité
2. PGCD de deux éléments
3. Nombres premiers entre eux
4. PPCM
5. Nombres premiers
6. Relation de congruence
7. Synthèse des méthodes

On suppose dans tout ce chapitre sauf indication contraire que $\mathbb{K}= \mathbb{R}$ ou $\mathbb{C}$ .

Si vous rencontrez des difficultés lors de votre entraînement sur l’arithmétique, n’hésitez pas à consulter nos profs de maths à domicile.

1. Divisibilité

1.1. Diviseurs et multiples
$\bullet$ Si $a$ et $b \in \mathbb{Z}$ , il y a équivalence entre :
$\; \; \ast$ $a$ divise $b$ ou $a$ est un diviseur de $b$
$\; \; \ast$ $b$ est un multiple de $a$
$\; \; \ast$ il existe $k \in \mathbb{Z}$ tel que $b = a \, k$ .
On note $a \, \vert \, b$ .

Tout entier divise $0$ .
$0$ ne divise que lui-même.

$\bullet$ Si $a \in \mathbb{Z}$ ,
$\ast$ l’ensemble des multiples de $a$ est $\quad \quad \quad a \, \mathbb{Z} = \{ a\, k \, / \, k \in \mathbb{Z} \}$ .
$\ast$ Il n’y a pas de notation consacrée pour les diviseurs de $a$ .
J’utiliserai $\mathcal{D}(a)$ pour noter l’ensemble des diviseurs de $a$ .
$\ast$ $\mathcal{D}(0) = \mathbb{Z}$
$\ast$ si $n \in \mathbb{Z}$ et $\vert n \vert \geq 2$ ,
$\quad \quad \quad \{ \pm 1 , \, \pm n \} \subset \mathcal{D}(n)$ .

1.2. Propriétés
$\bullet$ la relation « $a \, \vert \, b$ » est une relation d’ordre sur $\mathbb{N}$ mais n’est pas une relation d’ordre sur $\mathbb{Z}$ .

$\bullet$ Si $a,b,c , d \in \mathbb{Z}$ ,
$\ast$ $d \, \vert \, a$ et $d \, \vert \, b$ $\quad \quad \Rightarrow$ $\forall\, (u ,\, v) \in \mathbb{Z}^2, \, d \, \vert \, a\, u + b \, v$ .
$\ast$ $a \, \vert \,b$ et $c \, \vert \, d$ $\Rightarrow$ $a \, c \, \vert \, b \, d$
$\ast$ si $k \in \mathbb{N}^*$ et $a \, \vert \, b$ , $a ^k \, \vert \, b ^k$ .

1.3. Diviseurs et multiples communs
Si $a_1\, ,\cdots ,\, a_n$ sont des éléments de $\mathbb{Z}$ , on appelle
$\ast$ diviseur commun de $a_1\, ,\cdots ,\, a_n$ tout $d \in \mathbb{Z}$ tel que $\forall\, k \in [\![1 , \, n]\! ], \, d \, \vert \, a_k \,$ .
$\pm 1$ sont des diviseurs communs à toute famille finie d’éléments de $\mathbb{Z}$ .

$\ast$ multiple commun de $a_1\, ,\cdots ,\, a_n$ tout $m\in \mathbb{Z}$ tel que $\forall\, k \in [\![1 , \, n]\! ], \, a_k \, \vert m$ .
$a_1 \, \cdots \, a_n$ est un multiple commun de la famille $a_1\, ,\cdots ,\, a_n\,$ .

1.4. Division euclidienne
$\bullet$ Théorème de division euclidienne
Si $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ , il existe un unique couple $(q ,\, r) \in \mathbb{Z}\times \mathbb{N}$ tel que $\quad \quad a = b \, q + r$ où $0 \leq r \leq b - 1$
$q$ est le dividende de $a$ par $b$
$r$ est le reste de la division euclidienne de $a$ par $b$ .

Remarque : $\displaystyle q = \left \lfloor \frac a b \right \rfloor$ et $a \equiv r \;\; [b]$ .

PROF DE MATHS PARTICULIER

Des cours de qualité et enseignants aguerris

Préparer des concours ou s'exercer

Avis Google France ★★★★★ 4,9 sur 5

2. PGCD de deux éléments

2.1. Définition et propriétés du PGCD
$\bullet$ Soient $a$ et $b$ deux éléments de $\mathbb{Z}$ .
On appelle PGCD de $a$ et $b$ et on note $a \wedge b$ l’entier naturel défini par
$\ast$ si $(a , b) = (0 , 0), \, a \wedge b = 0$
$\ast$ si $(a , b) \neq (0 , 0)$ , $\quad a \wedge b = \max \{ d \in \mathbb{N}\, /\, d \, \vert \, a \textrm{ et } d \, \vert \, b \}$ .

Propriétés
$\ast$ Si $a$ et $b$ sont deux éléments de $\mathbb{Z}$ ,
$\quad \quad a \wedge b = \vert a \vert \wedge \vert b \vert$
$\quad \quad a \wedge b = b \wedge a$
$\ast$ Si $a \in \mathbb{N} , \, a \wedge 0 = a$ .
$\ast$ Si $(a , b) \in \mathbb{Z}^2,\, a \wedge b = (a - b) \wedge b$ .
$\ast$ Si $k \in \mathbb{Z}$ , $(k \, a) \wedge (k \, b) = \vert k \vert \, (a \wedge b)$ .
$\ast$ Si $r$ est le reste de la division euclidienne de $a \in \mathbb{Z}$ par $b \in \mathbb{N}^*$ , $\quad \quad \quad \quad \quad a \wedge b = b \wedge r$ .
$\ast$ si $a$ , $b$ et $c$ sont dans $\mathbb{Z}$
$\quad \quad \quad (a \wedge b) \wedge c = a \wedge (b \wedge c)$

Relation de Bezout : soient $a$ et $b$ deux éléments de $\mathbb{Z }$ , il existe $u$ et $v$ dans $\mathbb{Z}$ tels que $a \wedge b = a \, u + b \, v$
$u$ et $v$ ne sont pas uniques !
Si $(u_0 ,\, v_0)$ est solution, pour tout $k \in \mathbb{Z}$ , $(u_0 + k \, b, v_0 - k \, a)$ est solution.

2.2. Algorithme d’Euclide
$\bullet$ Algorithme d’Euclide
Soient $a$ et $b$ dans $\mathbb{N}$ tels que $0 < b \leq a$
$\ast$ On note $r_0 = a, \, r _ 1 = b$ .
$\ast$ Par récurrence :
si $r _{k + 1} \neq 0$ , on note $r_{k + 2}$ le reste de la division euclidienne de $r_k$ par $r_{k + 1}\,$ .
$\ast$ Si $r_{N - 1}$ est le dernier reste non nul (et donc $r_N = 0$ ), $a \wedge b = r_{N - 1}$ .

$\bullet$ Ces calculs permettent de trouver une relation de Bezout par une méthode appelée remontée de l’algorithme d’Euclide :
On part de la relation
$\quad \quad r _ {N - 3} = q_{N - 2} \, r_{N - 2} + r_{N - 1}$
écrite sous la forme
$\quad \quad r_{N - 1} = r _ {N - 3} - q_{N - 2} \, r_{N - 2}$
et on remplace $r_{N - 2}$ en fonction de $r_{N-3}$ et $r_{N - 4}\,$ , ce qui permet d’exprimer $r_{N - 1}$ en fonction de $r_{N-3}$ et $r_{N - 4}\,$ .
Et on réitère jusqu’à exprimer $r_{N - 1}$ en fonction de $r_0$ et $r_1$ donc en fonction de $a$ et $b$ . On obtient une identité de Bezout.

2.3. Algorithme d’Euclide étendu
On se ramène au cas où $a$ et $b$ sont dans $\mathbb{N}$ avec $0 < b \leq a$
On note $r_0 = a$ , $r_ 1 = b$ .
On note $r_N$ le premier reste nul dans la suite des divisions euclidiennes.
Plus précisément si $k\in [\![0 , N - 2]\!]$ , on écrit : $r_{k } = r_{k + 1} \, q_{k + 1} + r_{k + 2}$ avec $0 \leq r_{k + 2} < r_{k + 1}\,$ .
On suppose $r_{N - 1} \neq 0$ et $r_N = 0$ .

Alors les familles définies par
$\ast$ $u_0 = 1$ , $u_ 1 = 0$
$\ast$ $v_ 0 = 0$ , $v_1 = 1$
$\ast$ $\forall\, k\in [\![0 , N - 2]\!]$
$\quad \left \{ \begin{matrix} u_{k + 2}&=& u_k - q_{k + 2} \, u_{k + 1} \\ v_{k + 2}&=& v_k - q_{k + 2}\, v_{k + 1} \end{matrix} \right.$
sont telles que $\quad \forall\, k \in [\![0 , N]\!], \, r _ k = a \, u_k + b \, v_k$
et on retient que
$\quad \quad a \wedge b =a \, u_{N - 1} + b \, v_{N - 1}$ .

On peut mener les calculs en tableau :
initialisation
$\quad \quad \left \vert \begin{matrix}0 & a & &... & & 1 & 0 \\ 1 &b & &...& & 0 &1 \end{matrix} \right \vert$

Calcul de la ligne $k + 2$ si l’on connaît les lignes $k$ et $k + 1$ si $k + 2 \leq N - 1$
$\left \vert \begin{matrix}k & r_k & q_k&u_k & v_k \\ k + 1 &r_{k + 1} & q_{k + 1} &u_{k + 1} & v_{k + 1}\\ k + 2 & & & & \end{matrix} \right \vert$
$\ast$ par division euclidienne de $r_k$ et $r_{k + 1} \,$ , on calcule le quotient placé en $q_{k + 2}$ et le reste placé en $r_{k + 2} \,$ .

$\left \vert \begin{matrix}k & r_k & q_k&u_k & v_k \\ k + 1 &r_{k + 1} & q_{k + 1} &u_{k + 1} & v_{k + 1}\\ k + 2 &r_{k + 2} & q_{k + 2} & & \end{matrix} \right \vert$
$\ast$ on calcule $u_{k + 2} = u_k - u_{k + 1 } \, q_{k + 2}$
et on calcule de même $v_{k + 2} \,$ ce qui permet de compléter la ligne $k + 2$ :
$\left \vert \begin{matrix}k & r_k & q_k&u_k & v_k \\ k + 1 &r_{k + 1} & q_{k + 1} &u_{k + 1} & v_{k + 1}\\ k + 2 &r_{k + 2} & q_{k + 2} &u_{k + 2} & v_{k + 2} \end{matrix} \right \vert$

On termine en ayant :
$\left \vert \begin{matrix}N - 2 & r_{N - 2} & q_{N - 2} &u_{N - 2} & v_{N - 2} \\ N - 1 &r_{N - 1} & q_{N - 1} &u_{N - 1} & v_{N - 1}\\ N &0 & & & \end{matrix} \right \vert$
Les calculs de $u_N$ et $v_N$ sont inutiles.

$\ast$ sur la ligne $N - 1$ donnant le dernier reste non nul, on obtient $a \wedge b = r_{N - 1}\,$ , $u_{N - 1}$ et $v _{N - 1}$

cette méthode est la méthode à utiliser en Python pour programmer le calcul du pgcd et de la relation de Bezout.

Exemple : relation de Bezout pour $a = 151$ et $b = 77$ par la remontée de l’algorithme et par l’algorithme d’Euclide étendu.

Correction : $\bullet$ Algorithme d’Euclide.
Les divisions successives donnent :
$151 = 1 \times 77 + 74$
$77 = 1 \times 74 + 3$
$74 = 24 \times 3 + 2$
$3 = 1 \times 2 + 1$
le reste suivant est nul
Le dernier reste non nul est égal à 1, donc $a \wedge b = 1$ .

$\bullet$ Bezout par remontée de l’algorithme d’Euclide
$1 = 3 - 1 \times 2$
$1 = 3 - (74 - 24 \times 3) = 3 \times 25 - 74$
$1 = (77 - 74) \times 25 - 74$
$1 = 77 \times 25 - 74 \times 26$
$1 = 77 \times 25 - (151 - 77) \times 26$
$1 = 77 \times 51 - 151 \times 26$

$\bullet$ Par l’algorithme d’Euclide étendu
$\left \vert \begin{matrix}0 & 151 &\cdots &1 & 0 \\ 1 &77 &\cdots &0 & 1\\ 2 &74 & 1 &1 & - 1 \\ 3 &3 & 1 &-1 & 2 \\ 4 &2&24 &2 5 & - 49 \\ 5 &1&1 & -26 & 51 \\ 6&0& & & \end{matrix} \right \vert$

Dans les deux cas, $51 \times a - 26 \times b = 1$ .

3. Nombres premiers entre eux

3.1. Deux nombres premiers entre eux
Définition :
Soient $a$ et $b$ deux éléments de $\mathbb{Z}^*$ . On dit que $a$ et $b$ sont premiers entre eux lorsque $a \wedge b = 1$ .

$a \wedge b = 1$ ssi $\pm 1$ sont les seuls diviseurs communs de $a$ et $b$ .

Propriétés
$\bullet$ Théorème de Bezout
Soient $a$ et $b$ deux éléments de $\mathbb{Z }$ .
$a \wedge b = 1$ ssi il existe $u$ et $v$ dans $\mathbb{Z}$ tels que $a \, u + b \, v = 1$ .

$\bullet$ Soient $(a,b,c) \in \mathbb{Z}^3$ ,
$c \wedge a = 1$ et $c \wedge b = 1$ $\Rightarrow c \wedge a \, b = 1$ .

$\bullet$ Théorème de Gauss
Soient $a$ , $b$ et $c$ dans $\mathbb{Z}$ .
$a \wedge b = 1$ et $a \,\vert \, b \, c$ $\Rightarrow$ $a \, \vert \, c$ .

$\bullet$ Soient $a$ , $b$ et $c$ dans $\mathbb{Z}$ .
$a$ divise $c$ , $b$ divise $c$ et $a \wedge b = 1$
$\quad \quad \quad \Rightarrow$ $a \, b$ divise $c$ .

$\bullet$ Soient $a$ et $b$ deux éléments de $\mathbb{Z }^*$ et $d = a \wedge b$ ,
alors $a = d \, a'$ et $b = d \,b'$
$\quad \quad$ où $(a', b') \in \mathbb{Z}^2$ et $a' \wedge b' = 1$ .

$\bullet$ Pour tout $r \in \mathbb{Q}^*$ , il existe un unique couple $(p , \,q) \in \mathbb{Z} ^* \times \mathbb{N}^*$ tels que $r = \displaystyle \frac p q$ avec $p \wedge q = 1$ .
On dit que $\displaystyle \frac p q$ est la forme irréductible du rationnel $r$ .

3.2. Généralisation au cas de $r \geq 3$ entiers
$\bullet$ Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \, , \cdots \,, a_r) \in \mathbb{Z}^r$ ,
on appelle PGCD de $(a_1 \, , \cdots \,, a_r)$ et on note $a_1 \wedge \cdots \wedge a_r$ l’entier naturel défini par
$\ast$ si $(a_1 \, , \cdots \, , a_r) = (0 , \, \cdots \, ,0)$ ,
$\quad \quad \quad a_1 \wedge \cdots \wedge a_r = 0$
$\ast$ si $(a_1 \, , \cdots \, , a_r) \neq (0 , \, \cdots \, ,0)$ ,
$a_1 \wedge \cdots \wedge a_r =$ $\quad \quad \max \{ d \in \mathbb{N}\, /\, \forall \, k \in [\![1 , r]\!],\, d \, \vert \, a_k \}$

$\bullet$ Identité de Bezout
Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \, ,\cdots \, ,a_r) \in \mathbb{Z}^r$ ,
Il existe $(u_1 ,\, \cdots \, , u_r) \in \mathbb{Z}^r$ tel que
$\quad a_1 \wedge \cdots \wedge a_r = \displaystyle \sum _{k = 1} ^r a_k \, u_k \,$ .

$\bullet$ Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \, ,\cdots \, ,a_r) \in \mathbb{Z}^r$ ,
$a_1 \wedge \cdots \wedge a_r = (a_1 \wedge \cdots \wedge a_{r - 1} ) \wedge a_r\,$ .

$\bullet$ Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \,, \cdots \, , a_r) \in \mathbb{Z}^r$ , on dit que :
$\ast$ $(a_1 \, , \cdots \, , a_r)$ sont premiers dans leur ensemble si $a_1 \wedge \cdots \wedge a_r = 1$
$\ast$ $(a_1 \, , \cdots \, , a_r)$ sont premiers 2 à 2 si $\forall \, i \neq j ,\, a_i \wedge a_j = 1$ .

$\bullet$ Théorème de Bezout
Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \, ,\cdots \, ,a_r) \in \mathbb{Z}^r$ ,
$(a_1 \, ,\cdots \, ,a_r)$ sont premiers dans leur ensemble ssi $\exists \, (u_1 ,\, \cdots \, , u_r) \in \mathbb{Z}^r$ , $\displaystyle \sum _{k = 1} ^r a_k \, u_k = 1$ .

4. PPCM

$\bullet$ Soient $a$ et $b$ deux éléments de $\mathbb{Z}$ .
On appelle PPCM de $a$ et $b$ et on note $a \vee b$ l’entier naturel défini par
$\ast$ $a \vee 0 = 0 \vee a = 0$
$\ast$ si $a \, b \neq 0$ , $a \vee b = \min \{ m \in \mathbb{N}\, /\, a \, \vert \, m \textrm{ et } b \, \vert \, m \}$

Propriétés :
Soient $a$ et $b$ de $\mathbb{Z}^*$
$\ast$ $a \, \mathbb{Z} \, \cap \, b \, \mathbb{Z} = (a \vee b) \, \mathbb{Z}$
$\ast$ $(a \wedge b) \, (a \vee b) = \vert a \, b \vert$
$\ast$ si $k \in \mathbb{Z}^*$ , $(k \, a ) \vee (k \, b) = \vert k \vert \, (a \vee b)$

$\bullet$ Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \,, \cdots \, , a_r) \in \mathbb{Z}^r$ ,
on définit le PPCM de $(a_1 \, , \cdots \, , a_r)$ par
$\ast$ si $\displaystyle \prod_{i = 1} ^r a_i = 0$ , $a_1 \vee \, \cdots \, \vee a_r = 0$
$\ast$ si $\displaystyle \prod_{i = 1} ^r a_i \neq 0$ ,
$a_1 \vee \, \cdots \, \vee a_r$ est le plus petit $m \in \mathbb{N}^*$ tel que $\forall\, i \in [\![1 , \, r]\!], \, a_i \, \vert \, m$ .

$\bullet$ Si $r\in \mathbb{N}$ , $r \geq 3$ et $(a_1 \, ,\cdots \, ,a_r) \in \mathbb{Z}^r$ ,
$a_1 \vee \cdots \vee a_r =(a_1 \vee \cdots \vee a_{r - 1} ) \vee a_r\,$ .

AVOIR LES MEILLEURS PROFS DE MATHS

C'est gagner en autonomie

5. Nombres premiers

5.1. Ensemble $\mathbb{P}$
$\bullet$ $p \in \mathbb{N} \setminus \{0 , \, 1 \}$ est premier lorsque les seuls diviseurs positifs de $p$ sont $1$ et $p$ .
On note $\mathbb{P}$ l’ensemble des nombres premiers.

$\bullet$ $\mathbb{P}$ est un ensemble infini.

$\bullet$ Si $n \geq 2$ , $n$ n’est pas premier ssi $n$ admet un diviseur premier inférieur ou égal à $\sqrt{n}$ .

$\bullet$ Crible d’Eratosthène
Soit $N \in \mathbb{N}$ , $N \geq 2$ . Pour obtenir la liste des nombres premiers inférieurs ou égaux à $N ^2$ ,
$\ast$ on écrit la liste $L$ des entiers entre $2$ et $N^2$ .
$\ast$ pour tout $k \in [\![2 ,\, N]\!]$ , si $k$ n’a pas été supprimé par le passage précédent, on supprime dans la liste $L$ les multiples de $k$ strictement supérieurs à $k$ qui n’ont pas encore été supprimés lors des étapes précédentes.

La liste obtenue après le dernier passage est la liste des nombres premiers entre $2$ et $N ^2$ .

Correction : Dans la liste des entiers de $2$ à $100$ ,
$\ast$ on barre les nombres pairs entre $4$ et 100
$\ast$ on barre les multiples stricts de 3 non encore barrés soit $9 , \, 15 , \, \cdots \, , 99$
$\ast$ on barre les multiples stricts de 5 soit $25, 35 , 55, 65, 85, 95$ multiples de $5$ qui n’avaient pas encore été barrés
$\ast$ on barre les entiers $49 , 77 , 91$ multiples de $7$ qui n’avaient pas encore été barrés.
Les entiers premiers inférieurs à 100 sont donc $2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43$ $47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 91 , 97$ .

5.2. Valuation $p$ -adique
$\bullet$ Si $p \in \mathbb{P}$ et $n \in \mathbb{Z}^*$ ,
la valuation $p$ –adique de $n$ est $\quad \quad v_p(n) = \max \{k \in \mathbb{N}\, / \, p^k \, \vert \, n \}$ .

$\bullet$ Si $p \in \mathbb{P}$ et $(a , b) \in {\mathbb{Z}^*}^2$
$\quad \ast$ $v_p( a) = v_p (\vert a \vert )$
$\quad \ast$ $v_p( a \, b ) = v_p ( a ) +v_p ( b )$ .

$\bullet$ Si $a \in \mathbb{Z}^*$ , l’ensemble des $p \in \mathbb{P},$ tels que $v_p(a) \neq 0$ est fini.
On dit que la famille $(v_p(a))_{p \in \mathbb{P}}$ est une famille d’entiers presque nuls.

5.3. Décomposition primaire
$\bullet$ Soit $(\alpha_p) _ {p \in \mathbb{P}}$ une famille d’entiers presque nulle (c’est à dire $\alpha _ p = 0$ sauf éventuellement pour un nombre fini d’entiers )
$\ast$ si $\forall\, p \in \mathbb{P}, \alpha _ p = 0$ , on note $\quad \quad \quad \displaystyle \prod_ {p \in \mathbb{P} } p ^{\alpha_p} = 1$
$\ast$ si $\{ p \in \mathbb{P} \, / \, \alpha _ p\neq 0 \}= \{p_1 , \, \cdots \, , p_k\}$ , on note $\displaystyle \prod_ {p \in \mathbb{P} } p ^{\alpha_p} = \prod_{i = 1}^k {p_i} ^{\alpha _{p_i}}$

$\bullet$ Tout entier $n \in \mathbb{N}^*$ s’écrit d’une et d’une seule façon sous la forme
$\quad \quad \quad n = \displaystyle \prod _{p \in \mathbb{P}} p ^{v_p(n)}$ .
Cette décomposition est appelée décomposition primaire de $n$ .

$\bullet$ Soient $a$ et $b$ deux éléments de $\mathbb{Z}^*$
$\ast$ $a$ divise $b$ ssi $\forall\, p \in \mathbb{P}$ , $v_p(a) \leq v_p(b)$
$\ast$ $a \wedge b = \displaystyle \prod _{p \in \mathbb{P}} p ^{\min (v_p(a), \, v_p(b))}$
$\ast$ $a \vee b = \displaystyle \prod _{p \in \mathbb{P}} p ^{\max (v_p(a),\, v_p(b))}$ .

6. Relation de congruence

6.1. Rappels
$\bullet$ Si $n \in \mathbb{N}^*$ , $(x , y) \in \mathbb{Z}^2$ ,
$x \equiv y\;\;[n]$ $\Leftrightarrow n \, \vert \, x - y$
$\Leftrightarrow \exists \, p \in \mathbb{Z} , \ x- y = n \, p$
définit une relation d’équivalence sur $\mathbb{Z}$ appelée relation de congruence modulo $n$ .

$\bullet$ Pour la relation de congruence modu- lo $n$ , il y a $n$ classes d’équivalence :
$\forall\, r \in [\![0 , \, n - 1]\!]$ , $\dot r = \{r + n\, p \,/ \, p \in \mathbb{Z}\}$ .

6.2. Propriétés
$\bullet$ la relation de congruence modulo $n$ est une relation d’équivalence sur $\mathbb{Z}$ vérifiant si $x \equiv y \;\; [n]$ et $z \equiv u \;\; [n]$ ,
$\ast$ $x + z\equiv y + u \;\; [n]$
$\ast$ $x\, z \equiv y \, u \;\; [n]$
$\ast$ si $k \in \mathbb{N}$ , $x ^k \equiv y ^k \;\;[n]$
$\ast$ si $m \in \mathbb{N}^*$ , $m \, x \equiv m\, y \;\; [m \, n]$

$\bullet$ Soient $(n,\, r) \in {\mathbb{N}^{*} } ^2$ et $(a , \, b) \in \mathbb{Z}^2$ .
$n \wedge r = 1$ et $r \, a \equiv r\, b \; \; [n]$ $\Rightarrow a \equiv b \; \; [n]$ .

$\bullet$ Petit théorème de Fermat
Soit $p$ un nombre premier.
$\; \; \ast$ pour tout $a \in \mathbb{Z}$ , $a ^p \equiv a \; \; [p]$
$\; \; \ast$ si $p$ ne divise pas $a$ , $a ^{p - 1} \equiv 1 \; \; [p]$ .

7. Synthèse de méthodes

7.1. Déterminer le pgcd de $a$ et $b$ si $a \, b\neq 0$
Se ramener si nécessaire au cas $a \in \mathbb{N}^*$ et $b \in \mathbb{N}^*$ puisque $\quad \quad \quad a \wedge b = \vert a \vert \wedge \vert b \vert$ .
$\bullet$ Utiliser l’algorithme d’Euclide.
$\bullet$ Utiliser la décomposition primaire de $a$ et $b$ .

7.2. Montrer que $a \wedge b = 1$ si $(a ,\, b) \in \mathbb{N}^{*2}$
$\bullet$ Utiliser l’algorithme d’ Euclide.
$\bullet$ Introduire $d \in \mathbb{N}^*$ diviseur de $a$ et $b$ et montrer que $d = 1$ .
$\bullet$ Utiliser la décomposition primaire de $a$ et $b$ .
$\bullet$ Supposer qu’il existe $p \in \mathbb{P}^*$ qui divise $a$ et $b$ et démontrer que l’on arrive à une contradiction.
$\bullet$ Trouver $u$ et $v$ dans $\mathbb{Z}$ tels que $a \, u + b \, v = 1$ .

7.3. Utiliser $a \wedge b = 1$ si $(a ,\, b) \in \mathbb{N}^{*2}$
$\bullet$ $\forall\, p \in \mathbb{P}^*, \, v_p(a) \, v_p(b) = 0$ .
$\bullet$ Si $d \in \mathbb{N}^*$ divise $a$ et $b$ , $d = 1$ .
$\bullet$ Introduire $u$ et $v$ dans $\mathbb{Z}$ tels que $a \, u + b \, v = 1$ .
$\bullet$ Si de plus $a$ divise $b \, c$ , $a$ divise $c$ (théorème de Gauss).

7.4. Démontrer que $b \in \mathbb{N}^*$ divise $a \in \mathbb{Z}$
$\bullet$ Trouver $k \in \mathbb{Z}$ tel que $a = b \, k$ .
$\bullet$ Montrer que le reste de la division euclidienne de $a$ par $b$ est nul.
$\bullet$ Montrer que $a \equiv 0 \; \; [b]$ .
$\bullet$ Montrer que $\forall\, p \in \mathbb{P}, \, v_p(b) \leq v_p(a)$ .
$\bullet$ Écrire $b = x_1 \, \cdots \, x_r$ où $( x_1 \,, \cdots \,, x_r ) \in \mathbb{N}^{*r}$ sont premiers deux à deux et montrer que $\forall\, i \in [\![1, \, r]\!]$ , $x_i$ divise $a$ .
$\bullet$ Montrer que $( x_1 \,, \cdots \,, x_r ) \in \mathbb{N}^{*r}$ vérifie $\forall\, i \in [\![1, \, r]\!]$ , $x_i$ divise $a$ et que $b = x_1\, \vee\, \cdots \,\vee \, x_r \,$ .
$\bullet$ Appliquer le théorème de Fermat :
$\quad \ast$ montrer que $b$ est premier et que $a = n ^ b - n$ avec $n \in \mathbb{Z}$
$\quad\ast$ montrer que $b$ est premier et que $a = n ^{b - 1} - 1$ avec $n \wedge b = 1$ .

7.5. Démontrer que $n \in \mathbb{N}^*$ n’est pas premier
$\ast$ Trouver $d$ diviseur de $n$ tel que $1 < d < n$ .
$\ast$ Trouver un entier $p$ premier tel que $p$ divise $n$ .
(on rappelle qu’un nombre $n \in \mathbb{N}^*$ non premier admet un diviseur premier $d$ tel que $d \leq \sqrt{n}$ ).

Complétez vos révisions et vos entraînements en maths au programme de Maths Sup, avec les autres cours en ligne de MPSI, PCSI et PTSI disponibles gratuitement :