Arithmétique dans ℤ — Résumé de cours

1ère Année Collège — Atlasmaths.ma

Cours complet

Contenu du cours

I. Divisibilité dans $Z$

Définition

Soient $a, b \in Z$ avec $b \neq = 0$ . On dit que b divise a, noté $b ∣ a$ , s'il existe $k \in Z$ tel que $a = k \cdot b$ .

On dit aussi que a est un multiple de b, ou que b est un diviseur de a.

Propriétés

$1 ∣ a$ et $a ∣ a$ pour tout $a \in Z^{*}$ .
Si $a ∣ b$ et $b ∣ c$ , alors $a ∣ c$ (transitivité).
Si $a ∣ b$ et $a ∣ c$ , alors $a ∣ (α b + β c)$ pour tous $α, β \in Z$ (combinaison linéaire).
Si $a ∣ b$ et $b ∣ a$ (a, b non nuls), alors $∣ a ∣ = ∣ b ∣$ , soit $a = \pm b$ .
Si $a ∣ b$ et $b \neq = 0$ , alors $∣ a ∣ \leq ∣ b ∣$ .

II. Division euclidienne dans $Z$

Théorème

Pour tous $a \in Z$ et $b \in N^{*}$ , il existe un unique couple $(q, r) \in Z \times N$ tel que :

$a = b q + r$ avec $0 \leq r < b$

q est le quotient et r le reste de la division euclidienne de a par b.

Exemple

Pour $a = - 17$ et $b = 5$ : $- 17 = 5 \cdot (- 4) + 3$ avec $0 \leq 3 < 5$ . Donc $q = - 4$ et $r = 3$ .

III. Congruences modulo n

Définition

Soit $n \in N^{*}$ . On dit que a et b sont congrus modulo n, noté $a \equiv b (mod n)$ , si n divise $(a - b)$ , c'est-à-dire si a et b ont le même reste dans la division euclidienne par n.

Propriétés des congruences

Soient $a, b, c, d \in Z$ et $n \in N^{*}$ . Si $a \equiv b (mod n)$ et $c \equiv d (mod n)$ , alors :

$a + c \equiv b + d (mod n)$ (somme)
$a - c \equiv b - d (mod n)$ (différence)
$a \cdot c \equiv b \cdot d (mod n)$ (produit)
$a^{k} \equiv b^{k} (mod n)$ pour tout $k \in N$ (puissance)

Attention : on ne peut pas toujours diviser les congruences. $a \cdot c \equiv b \cdot c (mod n)$ n'implique pas $a \equiv b (mod n)$ .

Applications

Reste d'une puissance : calcul efficace de $a^{n} mod p$ .
Critères de divisibilité : par 3 (somme des chiffres), par 9, par 11, etc.
Équations diophantiennes : résolution modulo un nombre bien choisi.

IV. PGCD (plus grand commun diviseur)

Définition

Soient $a, b \in Z$ non tous deux nuls. Le PGCD de a et b, noté $g cd (a, b)$ ou $a \land b$ , est le plus grand entier positif qui divise à la fois a et b.

Algorithme d'Euclide

Si $a = b q + r$ avec $0 \leq r < b$ , alors $g cd (a, b) = g cd (b, r)$ .

On itère jusqu'à obtenir un reste nul : le dernier reste non nul est le pgcd.

Exemple — $g cd (84, 30)$

$84 = 30 \cdot 2 + 24$ $\Rightarrow$ $g cd (84, 30) = g cd (30, 24)$
$30 = 24 \cdot 1 + 6$ $\Rightarrow$ $g cd (30, 24) = g cd (24, 6)$
$24 = 6 \cdot 4 + 0$ $\Rightarrow$ $g cd (24, 6) = 6$
Donc $g cd (84, 30) = 6$ .

Propriétés

$g cd (a, b) = g cd (∣ a ∣, ∣ b ∣)$
$g cd (k a, k b) = ∣ k ∣ \cdot g cd (a, b)$ pour $k \in Z^{*}$
$g cd (a, 0) = ∣ a ∣$
$g cd (a, b) \cdot lcm (a, b) = ∣ a \cdot b ∣$

V. Théorème de Bézout

Identité de Bézout

Pour tous $a, b \in Z$ non tous deux nuls, il existe $u, v \in Z$ tels que :

$a u + b v = g cd (a, b)$

Théorème de Bézout (forme caractéristique)

Deux entiers a et b sont premiers entre eux ( $g cd (a, b) = 1$ ) si et seulement si il existe $u, v \in Z$ tels que $a u + b v = 1$ .

Algorithme d'Euclide étendu

Pour déterminer u et v explicitement, on « remonte » les divisions successives.

VI. Théorème de Gauss

Théorème

Soient $a, b, c \in Z$ . Si $a ∣ b c$ et $g cd (a, b) = 1$ , alors $a ∣ c$ .

Corollaires

Si $g cd (a, b) = 1$ et $a ∣ n$ , $b ∣ n$ , alors $ab ∣ n$ .
Si $a ∣ c$ , $b ∣ c$ et $g cd (a, b) = 1$ , alors $ab ∣ c$ .

VII. PPCM (plus petit commun multiple)

Définition

Le PPCM de a et b (non nuls), noté $lcm (a, b)$ ou $a \lor b$ , est le plus petit entier strictement positif multiple à la fois de a et de b.

Relation fondamentale

$g cd (a, b) \times lcm (a, b) = ∣ a \times b ∣$

VIII. Nombres premiers

Définition

Un entier $p \geq 2$ est premier s'il n'admet que deux diviseurs positifs : 1 et lui-même.

Exemples : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Lemme d'Euclide

Si p est premier et $p ∣ ab$ , alors $p ∣ a$ ou $p ∣ b$ .

Théorème fondamental de l'arithmétique

Tout entier $n \geq 2$ s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers :

$n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot \dots \cdot p_{k}^{α_{k}}$

Théorème (Euclide)

L'ensemble des nombres premiers est infini.

Test de primalité

Pour vérifier que n est premier, il suffit de vérifier qu'il n'est divisible par aucun nombre premier $p \leq n$ .

Exemple : pour tester 97, on vérifie les premiers $p \leq 97 \approx 9.8$ : 2, 3, 5, 7. Aucun ne divise 97 $\Rightarrow$ 97 est premier.

IX. Équations diophantiennes ax + by = c

Critère de résolubilité

L'équation $a x + b y = c$ ( $a, b, c \in Z$ , $(a, b) \neq = (0, 0)$ ) admet des solutions entières si et seulement si $g cd (a, b) ∣ c$ .

Méthode de résolution

Calculer $d = g cd (a, b)$ . Si d ne divise pas c : pas de solution.
Sinon, diviser toute l'équation par d pour se ramener à $a^{'} x + b^{'} y = c^{'}$ avec $g cd (a^{'}, b^{'}) = 1$ .
Trouver une solution particulière $(x_{0}, y_{0})$ par Bézout.
Solution générale : $(x, y) = (x_{0} + b^{'} k; y_{0} - a^{'} k)$ pour $k \in Z$ .

🔑 Formules clés à retenir

Division euclidienne : a = bq + r avec 0 ≤ r < b (unique)
Congruence : a ≡ b [n] ⇔ n | (a−b)
Opérations : les congruences respectent +, −, ×, puissance
Algorithme d'Euclide : pgcd(a, b) = pgcd(b, a mod b)
Bézout : pgcd(a, b) = 1 ⇔ ∃ u, v ∈ ℤ : au + bv = 1
Gauss : a | bc et pgcd(a,b) = 1 ⇒ a | c
PGCD × PPCM : pgcd(a, b) · ppcm(a, b) = |ab|
Décomposition unique en facteurs premiers
ax + by = c a des solutions ⇔ pgcd(a, b) | c

⚠️

Astuces & Pièges à éviter

Les erreurs classiques — à lire avant les exercices !

🔴 Pièges classiques

❌

Congruence et division : $a \equiv 0 (mod n)$ signifie que $n ∣ a$ . Mais $a \equiv b (mod n)$ ne signifie PAS $a / n = b$ — ça signifie que $a$ et $b$ ont le même reste dans la division par $n$ .

❌

Théorème de Gauss mal appliqué : pour conclure $a ∣ c$ depuis $a ∣ b c$ , il faut ABSOLUMENT que $pgcd (a, b) = 1$ . Si $pgcd (a, b) \neq = 1$ , la conclusion peut être fausse.

❌

Équation diophantienne : trouver la solution générale : après avoir trouvé une solution particulière $(x_{0}, y_{0})$ , la solution générale est $(x_{0} + b^{'} k, y_{0} - a^{'} k)$ avec $k \in Z$ (après division par pgcd). Ne pas oublier le $k$ !

🟢 Astuces de pros

✅

Congruences pour les derniers chiffres : le dernier chiffre de $a^{n}$ dépend uniquement de $a mod 10$ . Les puissances de 2 : $2, 4, 8, 6, 2, 4, 8, 6...$ (période 4). Très utile pour les calculs modulaires !

✅

Algorithme d'Euclide étendu pour Bézout : remonte les étapes de l'algorithme d'Euclide pour exprimer $pgcd (a, b)$ comme combinaison linéaire de $a$ et $b$ . Pratique pour trouver une solution particulière.

💡

Preuve de primalité : pour montrer qu'un nombre $n$ est premier, il suffit de vérifier qu'il n'est divisible par aucun nombre premier $\leq n$ . Si $100 = 10$ , tester seulement 2, 3, 5, 7.

🧭

Méthodes types

Pour chaque type de question : la démarche à suivre, étape par étape.

Méthodes types — Arithmétique dans ℤ

Type 1 : Montrer une divisibilité

Quand ? On demande de prouver que $a ∣ b$ (a divise b) ou qu'un entier divise une expression.

Reviens à la définition : $a ∣ b$ signifie qu'il existe $k \in Z$ tel que $b = ak$ .
Factorise l'expression ou écris-la sous la forme $a \times (entier)$ .
Pour une expression dépendant de $n$ , essaie un raisonnement par récurrence ou les congruences.
Conclus en exhibant le facteur entier.

Exemple éclair : $n^{2} - n = n (n - 1)$ est divisible par $2$ car produit de deux entiers consécutifs.

Type 2 : Effectuer et utiliser la division euclidienne

Quand ? On demande le quotient et le reste, ou de discuter selon le reste de $n$ modulo $p$ .

Écris $a = b q + r$ avec $0 ⩽ r < b$ (unicité de $q$ et $r$ ).
Pour discuter, pose $n = pq + r$ avec $r \in {0, 1, \dots, p - 1}$ .
Traite chaque valeur possible du reste $r$ séparément.
Regroupe les cas pour conclure.

Exemple éclair : Tout entier $n$ s'écrit $3 q$ , $3 q + 1$ ou $3 q + 2$ ; on étudie $n^{2}$ dans chaque cas.

Type 3 : Calculer avec les congruences

Quand ? On veut un reste de division (ex : reste de $7^{100}$ par $5$ ) ou prouver une divisibilité par les congruences.

Réduis la base modulo $n$ : par exemple $7 \equiv 2 [5]$ .
Calcule les puissances successives pour trouver un cycle : $2^{1}, 2^{2}, \dots$ modulo $n$ .
Utilise la périodicité pour ramener l'exposant.
Conclus sur le reste cherché.

Exemple éclair : $2^{4} \equiv 1 [5]$ donc $7^{100} \equiv 2^{100} = (2^{4})^{25} \equiv 1 [5]$ .

Type 4 : Déterminer le PGCD (algorithme d'Euclide)

Quand ? On demande $pgcd (a, b)$ de deux entiers, ou de montrer que deux nombres sont premiers entre eux.

Applique l'algorithme d'Euclide : remplace $(a, b)$ par $(b, r)$ où $r$ est le reste de $a$ par $b$ .
Répète jusqu'à obtenir un reste nul.
Le dernier reste non nul est le $pgcd (a, b)$ .
Si $pgcd (a, b) = 1$ , les nombres sont premiers entre eux.

Exemple éclair : $pgcd (48, 18)$ : $48 = 2 \times 18 + 12$ , $18 = 1 \times 12 + 6$ , $12 = 2 \times 6 + 0$ donc $pgcd = 6$ .

Type 5 : Résoudre une équation de Bézout $a u + b v = c$

Quand ? On cherche des entiers $u, v$ tels que $a u + b v = c$ , ou une identité de Bézout.

Calcule $d = pgcd (a, b)$ par l'algorithme d'Euclide.
L'équation a des solutions si et seulement si $d ∣ c$ .
Remonte l'algorithme d'Euclide pour obtenir $a u_{0} + b v_{0} = d$ .
Multiplie par $\frac{c}{d}$ pour obtenir une solution particulière de $a u + b v = c$ .

Exemple éclair : $pgcd (5, 3) = 1$ et $5 \times 2 + 3 \times (- 3) = 1$ , donc $u = 2, v = - 3$ vérifient $5 u + 3 v = 1$ .

Type 6 : Appliquer le théorème de Gauss

Quand ? On a $a ∣ b c$ et on veut conclure que $a ∣ c$ .

Vérifie l'hypothèse $a ∣ b c$ .
Montre que $pgcd (a, b) = 1$ (a et b premiers entre eux).
Applique Gauss : alors $a ∣ c$ .
Rédige clairement les deux hypothèses avant la conclusion.

Exemple éclair : $7 ∣ 3 n$ et $pgcd (7, 3) = 1$ donc, par Gauss, $7 ∣ n$ .

Type 7 : Calculer le PPCM et utiliser la relation avec le PGCD

Quand ? On demande $ppcm (a, b)$ ou on relie PGCD et PPCM.

Calcule $d = pgcd (a, b)$ .
Applique la relation $pgcd (a, b) \times ppcm (a, b) = ∣ ab ∣$ .
Déduis $ppcm (a, b) = \frac{∣ ab ∣}{d}$ .
Vérifie que le résultat est bien multiple de $a$ et de $b$ .

Exemple éclair : $pgcd (48, 18) = 6$ donc $ppcm (48, 18) = \frac{48 \times 18}{6} = 144$ .

Type 8 : Résoudre une congruence linéaire $a x \equiv b [n]$

Quand ? On cherche tous les entiers $x$ vérifiant $a x \equiv b [n]$ .

Calcule $d = pgcd (a, n)$ ; il y a des solutions si et seulement si $d ∣ b$ .
Si $pgcd (a, n) = 1$ , trouve l'inverse de $a$ modulo $n$ par Bézout.
Multiplie par cet inverse : $x \equiv a^{- 1} b [n]$ .
Donne l'ensemble des solutions sous forme $x = x_{0} + k n$ , $k \in Z$ .

Exemple éclair : $3 x \equiv 1 [7]$ : l'inverse de $3$ est $5$ (car $3 \times 5 = 15 \equiv 1$ ), donc $x \equiv 5 [7]$ .

Arithmétique dans ℤ — Fiche d'exercices

1ère Année Collège — Atlasmaths.ma | Écris tes réponses dans les espaces prévus

Exercices interactifs

74 exercices • Lis l'énoncé, écris ta réponse, puis vérifie la correction

Ma progression 0 / 74 corrigés

Exercices Faciles

23 exercices

Division euclidienne

Facile

Énoncé

Effectuer la division euclidienne :

de 257 par 12
de −257 par 12
de 1000 par 37
de 2025 par 45

Ma réponse

Arithmétique dans ℤ

Arithmétique dans ℤ — Résumé de cours

Cours complet

Contenu du cours

I. Divisibilité dans Z

Définition

Propriétés

II. Division euclidienne dans Z

Théorème

Exemple

III. Congruences modulo n

Définition

Propriétés des congruences

Applications

IV. PGCD (plus grand commun diviseur)

Définition

Algorithme d'Euclide

Exemple — gcd(84,30)

Propriétés

V. Théorème de Bézout

Identité de Bézout

Théorème de Bézout (forme caractéristique)

Algorithme d'Euclide étendu

VI. Théorème de Gauss

Théorème

Corollaires

VII. PPCM (plus petit commun multiple)

Définition

Relation fondamentale

VIII. Nombres premiers

Définition

Lemme d'Euclide

Théorème fondamental de l'arithmétique

Théorème (Euclide)

Test de primalité

IX. Équations diophantiennes ax + by = c

Critère de résolubilité

Méthode de résolution

🔑 Formules clés à retenir

Astuces & Pièges à éviter

🔴 Pièges classiques

🟢 Astuces de pros

Méthodes types

Méthodes types — Arithmétique dans ℤ

Type 1 : Montrer une divisibilité

Type 2 : Effectuer et utiliser la division euclidienne

Type 3 : Calculer avec les congruences

Type 4 : Déterminer le PGCD (algorithme d'Euclide)

Type 5 : Résoudre une équation de Bézout au+bv=c

Type 6 : Appliquer le théorème de Gauss

Type 7 : Calculer le PPCM et utiliser la relation avec le PGCD

Type 8 : Résoudre une congruence linéaire ax≡b[n]

Arithmétique dans ℤ — Fiche d'exercices

Exercices interactifs

Exercices Faciles

Division euclidienne

PGCD par algorithme d'Euclide

Congruences de base

Décomposition en facteurs premiers

PGCD par Euclide et simplification de fraction

Décomposition de 1080 et nombre de diviseurs

Divisibilité et entiers relatifs

Énoncé

Reste modulo et puissances congruentes

Énoncé

Divisibilité simple

Divisibilité simple

Diviseur commun

Multiples

Combinaison linéaire

Multiples et diviseurs

Divisibilité simple

Multiples d'un nombre

Diviseur commun

Reste de la division

Division euclidienne

Divisibilité simple

Multiples et diviseurs

Vérification de la divisibilité

Divisibilité avec des nombres négatifs

I. Divisibilité dans $Z$

II. Division euclidienne dans $Z$

Exemple — $g cd (84, 30)$

Type 5 : Résoudre une équation de Bézout $a u + b v = c$

Type 8 : Résoudre une congruence linéaire $a x \equiv b [n]$