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

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

Cours complet

Contenu du cours

I. Rappels : divisibilité et division euclidienne

Divisibilité

Pour $a \in Z$ , $b \in Z^{*}$ , on dit que b divise a ( $b ∣ a$ ) s'il existe $k \in Z$ tel que $a = bk$ .

Division euclidienne

Pour tout $a \in Z$ et $b \in N^{*}$ , il existe un unique $(q, r) \in Z \times N$ tel que $a = b q + r$ avec $0 \leq r < b$ .

II. Congruences modulo n (approfondissement)

Définition

Soit $n \in N^{*}$ . $a \equiv b [n]$ $\Leftrightarrow$ $n ∣ (a - b)$ $\Leftrightarrow$ a et b ont le même reste dans la division par n.

Opérations compatibles

Si $a \equiv a^{'} [n]$ et $b \equiv b^{'} [n]$ , alors :

$a + b \equiv a^{'} + b^{'} [n]$
$a \cdot b \equiv a^{'} \cdot b^{'} [n]$
$a^{k} \equiv a^{' k} [n]$ pour tout $k \in N$
$P (a) \equiv P (a^{'}) [n]$ pour tout polynôme P à coefficients entiers

Simplification dans une congruence

$a c \equiv b c [n]$ n'implique pas $a \equiv b [n]$ en général. Mais :

Si $g cd (c, n) = 1$ : $a c \equiv b c [n] \Rightarrow a \equiv b [n]$

III. PGCD, PPCM — rappels et approfondissements

Propriétés du PGCD

$g cd (a, b) = g cd (b, a - b q)$ pour tout $q \in Z$ (base de l'algorithme d'Euclide).
Tout diviseur commun de a et b divise $g cd (a, b)$ .
$g cd (k a, k b) = ∣ k ∣ \cdot g cd (a, b)$ .

Caractérisation du PGCD

$d = g cd (a, b)$ $\Leftrightarrow$ $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , et tout diviseur commun de a et b divise d.

Relation PGCD × PPCM

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

IV. 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)$

Forme caractéristique (nombres premiers entre eux)

$g cd (a, b) = 1$ $\Leftrightarrow$ $\exists u, v \in Z, a u + b v = 1$

Algorithme d'Euclide étendu

Les coefficients u, v s'obtiennent par remontée des divisions successives de l'algorithme d'Euclide.

V. Théorème de Gauss

Énoncé

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

Corollaires utiles

Si $a ∣ n$ , $b ∣ n$ et $g cd (a, b) = 1$ , alors $ab ∣ n$ .
Si $g cd (a, n) = 1$ et $g cd (b, n) = 1$ , alors $g cd (ab, n) = 1$ .
Si $g cd (a, b) = 1$ , alors $g cd (a^{k}, b^{m}) = 1$ pour tous $k, m \in N$ .

VI. Nombres premiers — approfondissement

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 $n \geq 2$ se décompose, de manière unique (à l'ordre près), en produit de facteurs premiers :

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

Nombre de diviseurs

Si $n = p_{1}^{α_{1}} \cdot \dots \cdot p_{k}^{α_{k}}$ , le nombre de diviseurs positifs de n est :

$τ (n) = (α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1)$

VII. Petit théorème de Fermat

Énoncé

Soit p un nombre premier et a un entier.

Si p ne divise pas a : $a^{p - 1} \equiv 1 [p]$
Pour tout a : $a^{p} \equiv a [p]$

Applications

Calcul rapide de restes de puissances élevées modulo un nombre premier.
Critères d'irréductibilité, tests de primalité (test de Fermat).
Résolution d'équations du type $a^{n} \equiv b [p]$ .

Exemple

Calculer $3^{2024} mod 7$ . Comme 7 est premier et $7 ∤ 3$ : $3^{6} \equiv 1 [7]$ . Or $2024 = 6 \cdot 337 + 2$ . Donc $3^{2024} = (3^{6})^{337} \cdot 3^{2} \equiv 1 \cdot 9 \equiv$ $2 [7]$ .

VIII. Équations diophantiennes ax + by = c

Critère d'existence de solutions

$a x + b y = c$ admet des solutions $(x, y) \in Z^{2}$ si et seulement si $g cd (a, b) ∣ c$ .

Méthode complète

Calculer $d = g cd (a, b)$ . Si $d ∤ c$ : pas de solution.
Diviser par d : $a^{'} x + b^{'} y = c^{'}$ avec $g cd (a^{'}, b^{'}) = 1$ .
Chercher une solution particulière $(x_{0}, y_{0})$ par Bézout.
Solution générale : $x = x_{0} + b^{'} \cdot k, y = y_{0} - a^{'} \cdot k$ pour $k \in Z$ .

IX. Systèmes de congruences — théorème chinois

Théorème chinois des restes

Soient $m, n \in N^{*}$ avec $g cd (m, n) = 1$ . Pour tous $a, b \in Z$ , le système :

${x \equiv a [m] et x \equiv b [n]}$

admet une unique solution modulo mn.

Résolution pratique

Écrire $x = a + mk$ pour un $k \in Z$ .
Reporter dans la deuxième : $a + mk \equiv b [n] \Rightarrow mk \equiv b - a [n]$ .
Comme $g cd (m, n) = 1$ , m est inversible modulo n : $k \equiv m^{- 1} (b - a) [n]$ .
Remonter : $x = a + mk = a + m \cdot [m^{- 1} (b - a) mod n] mod mn$ .

X. Critères de divisibilité (applications)

Par 3 ou 9 : un entier est divisible par 3 (resp. 9) ssi la somme de ses chiffres l'est. (Car $10 \equiv 1 [3]$ et $[9]$ .)
Par 11 : somme alternée des chiffres divisible par 11. (Car $10 \equiv - 1 [11]$ .)
Par 7 : le nombre formé en soustrayant $2 \times$ le dernier chiffre au nombre privé de son dernier chiffre est divisible par 7.
Par 4 : les 2 derniers chiffres forment un nombre divisible par 4.
Par 8 : les 3 derniers chiffres forment un multiple de 8.

🔑 Formules clés à retenir

Division euclidienne : a = bq + r, $0 \leq r < b$
Congruences : $a \equiv b (mod n)$ $\Leftrightarrow$ $n ∣ (a - b)$ · stable par +, $\times$ , $^{k}$
Algorithme d'Euclide : $g cd (a, b) = g cd (b, a mod b)$
Bézout : $g cd (a, b) = 1$ $\Leftrightarrow$ $\exists u, v : a u + b v = 1$
Gauss : $a ∣ b c$ et $g cd (a, b) = 1$ $\Rightarrow$ $a ∣ c$
Petit Fermat : p premier, $p ∤ a$ $\Rightarrow$ $a^{p - 1} \equiv 1 (mod p)$
Fermat (forme générale) : $a^{p} \equiv a (mod p)$
Chinois : $g cd (m, n) = 1$ $\Rightarrow$ ${x \equiv a (mod m), x \equiv b (mod n)}$ unique mod $mn$
ax + by = c : solutions $\Leftrightarrow$ $g cd (a, b) ∣ c$ · générale : $(x_{0} + b^{'} k, y_{0} - a^{'} k)$
τ(n) : si $n = \prod p_{i}^{α_{i}}$ , alors $τ (n) = \prod (α_{i} + 1)$

⚠️

Astuces & Pièges à éviter

Les erreurs classiques — à lire avant les exercices !

🔴 Pièges classiques

❌

Petit Fermat : p ne doit pas diviser a : le théorème dit $a^{p - 1} \equiv 1 (mod p)$ seulement si $g cd (a, p) = 1$ . Si $p ∣ a$ , alors $a \equiv 0 (mod p)$ et $a^{p - 1} \equiv 0 (mod p)$ , pas 1 !

❌

Congruences et division : on ne peut pas "diviser" des deux côtés d'une congruence sauf si le diviseur est premier avec le modulus. $6 \equiv 2 (mod 4)$ ne donne pas $3 \equiv 1 (mod 4)$ après division par 2 (car $g cd (2, 4) \neq = 1$ ) !

❌

Théorème chinois : vérifier $g cd (m, n) = 1$ : le théorème des restes chinois exige que m et n soient premiers entre eux. Si $g cd (m, n) > 1$ , le système peut ne pas avoir de solution.

🟢 Astuces de pros

✅

Calcul de $a^{n} mod p$ : utiliser le petit Fermat + décomposition de n en quotient-reste par $p - 1$ . Ex : $3^{100} mod 7$ : $3^{6} \equiv 1 (mod 7)$ (Fermat), $100 = 6 \times 16 + 4$ , donc $3^{100} \equiv 3^{4} = 81 \equiv 4 (mod 7)$ .

✅

Trouver $τ (n)$ rapidement : décompose $n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot \dots$ puis $τ (n) = (α_{1} + 1) (α_{2} + 1) \dots$ Ex : $τ (12) = τ (2^{2} \cdot 3) = 3 \times 2 = 6$ diviseurs (1, 2, 3, 4, 6, 12).

💡

Algorithme de Bézout : remonte les étapes d'Euclide pour exprimer $g cd (a, b) = u a + v b$ . Cette combinaison linéaire donne une solution particulière de l'équation diophantienne $a x + b y = g cd (a, b)$ .

🧭

Méthodes types

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

Méthodes types — Arithmétique dans $Z$

Type 1 : Divisibilité et division euclidienne

Quand ? On demande de montrer que $a$ divise $b$ , ou d'effectuer / utiliser la division euclidienne de $a$ par $b$ .

Pour la divisibilité : montrer $b = a \times k$ avec $k \in Z$ , soit $a ∣ b$ .
Pour la division euclidienne ( $b > 0$ ) : écrire $a = b q + r$ avec $0 \leq r < b$ , $q$ et $r$ uniques.
Utiliser les propriétés : $a ∣ b$ et $a ∣ c \Rightarrow a ∣ (b u + c v)$ pour tous $u, v \in Z$ .
Si $a ∣ b$ et $b ∣ a$ avec $a, b > 0$ , alors $a = b$ .

Exemple éclair : Division de $47$ par $5$ : $47 = 5 \times 9 + 2$ , donc $q = 9$ , $r = 2$ .

Type 2 : Calculs et raisonnements par congruences

Quand ? On étudie un reste modulo $n$ , le chiffre des unités, ou une grande puissance $a^{k}$ modulo $n$ .

Traduire : $a \equiv b [n] ⟺ n ∣ (a - b)$ .
Utiliser la compatibilité : si $a \equiv a^{'} [n]$ et $b \equiv b^{'} [n]$ , alors $a + b \equiv a^{'} + b^{'} [n]$ et $a \times b \equiv a^{'} \times b^{'} [n]$ .
Pour une puissance : chercher un cycle des restes de $a^{k} [n]$ , puis réduire l'exposant modulo la période.
Conclure sur le reste cherché (toujours dans ${0, \dots, n - 1}$ ).

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

Type 3 : Calculer un PGCD et un PPCM

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

Appliquer l'algorithme d'Euclide : $pgcd (a, b) = pgcd (b, r)$ où $r$ est le reste de $a$ par $b$ , jusqu'à un reste nul.
Le dernier reste non nul est $pgcd (a, b) = d$ .
$a$ et $b$ sont premiers entre eux $⟺ pgcd (a, b) = 1$ .
Utiliser la relation $pgcd (a, b) \times ppcm (a, b) = ∣ a \times b ∣$ .

Exemple éclair : $pgcd (48, 36)$ : $48 = 36 \times 1 + 12$ , $36 = 12 \times 3 + 0$ , donc $pgcd = 12$ et $ppcm = \frac{48 \times 36}{12} = 144$ .

Type 4 : Théorème de Bézout et coefficients

Quand ? On veut prouver que $pgcd (a, b) = 1$ via une combinaison, ou trouver $u, v$ tels que $a u + b v = d$ .

Théorème : $pgcd (a, b) = 1 ⟺ \exists (u, v) \in Z^{2}, a u + b v = 1$ .
Pour exhiber $(u, v)$ : remonter l'algorithme d'Euclide (substitutions successives des restes).
Plus généralement $a u + b v = pgcd (a, b)$ admet des solutions.
Si une relation $a u + b v = 1$ est trouvée, conclure directement $pgcd (a, b) = 1$ .

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

Type 5 : Théorème de Gauss et divisibilité

Quand ? On a $a ∣ b c$ et l'on veut conclure $a ∣ c$ , ou montrer un produit de divisibilités à partir d'entiers premiers entre eux.

Théorème de Gauss : si $a ∣ b c$ et $pgcd (a, b) = 1$ , alors $a ∣ c$ .
Corollaire : si $a ∣ c$ , $b ∣ c$ et $pgcd (a, b) = 1$ , alors $ab ∣ c$ .
Vérifier soigneusement l'hypothèse $pgcd = 1$ (souvent via Bézout, Type 4).
Conclure la divisibilité demandée.

Exemple éclair : $3 ∣ 5 n$ et $pgcd (3, 5) = 1$ donnent $3 ∣ n$ .

Type 6 : Résoudre une équation diophantienne $a x + b y = c$

Quand ? On cherche tous les couples d'entiers $(x, y)$ vérifiant $a x + b y = c$ .

Calculer $d = pgcd (a, b)$ : l'équation a des solutions $⟺ d ∣ c$ .
Trouver une solution particulière $(x_{0}, y_{0})$ (Bézout puis multiplication par $c / d$ ).
Écrire la solution générale : $x = x_{0} + \frac{b}{d} k$ , $y = y_{0} - \frac{a}{d} k$ , $k \in Z$ .
Vérifier en réinjectant et préciser les contraintes éventuelles (signes, bornes).

Exemple éclair : $5 x + 7 y = 1$ : solution particulière $(3, - 2)$ , d'où $x = 3 + 7 k$ , $y = - 2 - 5 k$ .

Type 7 : Nombres premiers et décomposition

Quand ? On teste la primalité d'un entier, on décompose en facteurs premiers, ou on dénombre les diviseurs.

Pour tester $n$ premier : vérifier qu'aucun premier $p$ avec $p \leq n$ ne divise $n$ .
Décomposer : $n = p_{1}^{α_{1}} \times \dots \times p_{r}^{α_{r}}$ (existence et unicité).
Nombre de diviseurs positifs : $(α_{1} + 1) \times \dots \times (α_{r} + 1)$ .
Utiliser : si $p$ premier et $p ∣ ab$ , alors $p ∣ a$ ou $p ∣ b$ .

Exemple éclair : $360 = 2^{3} \times 3^{2} \times 5$ possède $(3 + 1) (2 + 1) (1 + 1) = 24$ diviseurs.

Type 8 : Systèmes de congruences (type reste chinois)

Quand ? On cherche les entiers $x$ vérifiant simultanément $x \equiv a [m]$ et $x \equiv b [n]$ .

Exprimer la 1re congruence : $x = a + mk$ , $k \in Z$ .
Reporter dans la 2e : $a + mk \equiv b [n]$ , puis résoudre en $k$ (souvent via inverse de $m$ modulo $n$ ).
Si $pgcd (m, n) = 1$ , conclure $x \equiv x_{0} [mn]$ (solution unique modulo $mn$ ).
Décrire l'ensemble des solutions et vérifier sur les deux congruences.

Exemple éclair : $x \equiv 2 [3]$ et $x \equiv 3 [5]$ donnent $x \equiv 8 [15]$ .

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

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

Ma progression 0 / 173 corrigés

Exercices Faciles

40 exercices

Congruences et restes de puissances

Facile

Énoncé

Déterminer le reste de $7^{100}$ dans la division euclidienne par 10.
Déterminer le reste de $5^{2024}$ modulo 13.
Montrer que 11 divise $3^{10} - 1$ .

Ma réponse

Arithmétique dans ℤ

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

Cours complet

Contenu du cours

I. Rappels : divisibilité et division euclidienne

Divisibilité

Division euclidienne

II. Congruences modulo n (approfondissement)

Définition

Opérations compatibles

Simplification dans une congruence

III. PGCD, PPCM — rappels et approfondissements

Propriétés du PGCD

Caractérisation du PGCD

Relation PGCD × PPCM

IV. Théorème de Bézout

Identité de Bézout

Forme caractéristique (nombres premiers entre eux)

Algorithme d'Euclide étendu

V. Théorème de Gauss

Énoncé

Corollaires utiles

VI. Nombres premiers — approfondissement

Lemme d'Euclide

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

Nombre de diviseurs

VII. Petit théorème de Fermat

Énoncé

Applications

Exemple

VIII. Équations diophantiennes ax + by = c

Critère d'existence de solutions

Méthode complète

IX. Systèmes de congruences — théorème chinois

Théorème chinois des restes

Résolution pratique

X. Critères de divisibilité (applications)

🔑 Formules clés à retenir

Astuces & Pièges à éviter

🔴 Pièges classiques

🟢 Astuces de pros

Méthodes types

Méthodes types — Arithmétique dans Z

Type 1 : Divisibilité et division euclidienne

Type 2 : Calculs et raisonnements par congruences

Type 3 : Calculer un PGCD et un PPCM

Type 4 : Théorème de Bézout et coefficients

Type 5 : Théorème de Gauss et divisibilité

Type 6 : Résoudre une équation diophantienne ax+by=c

Type 7 : Nombres premiers et décomposition

Type 8 : Systèmes de congruences (type reste chinois)

Arithmétique dans ℤ — Fiche d'exercices

Exercices interactifs

Exercices Faciles

Congruences et restes de puissances

PGCD et Bézout

Nombre de diviseurs

Équation diophantienne simple

Division euclidienne et PGCD

Décomposition en facteurs premiers de 2520

Diviseurs de la forme 2n+5

Énoncé

Reste modulo 7 et chiffre des unités

Énoncé

Diviseurs et combinaisons linéaires

Énoncé

Non-divisibilité par 4 via congruences

Énoncé

Équation de Bézout et résolution dans Z

Équation diophantienne linéaire

GCD, solution particulière et résolution complète

Équation 143x−195y=52

Divisibilité et diviseurs d'une constante

Énoncé

Divisibilité de 60

Multiples de 7

Divisibilité par 5

Divisibilité de nombres

Reste de division

Vérification de la divisibilité

Méthodes types — Arithmétique dans $Z$

Type 6 : Résoudre une équation diophantienne $a x + b y = c$

Équation $143 x - 195 y = 52$

Étude d'une congruence modulo $65 = 5 \times 13$

Les nombres $a_{n} = n 33 \dots 3 1$

Divisibilité de $N = 2010 11 \dots 1$

Les nombres $u_{n} = n 44 \dots 4$