Fiche de révision : Arithmétique dans Z

📋 Plan du Cours

1. Divisibilité et multiples
2. Division euclidienne
3. PGCD et algorithme d’Euclide
4. Nombres premiers entre eux
5. Congruences et opérations
6. Puissances modulo un entier
7. Nombres premiers
8. Décomposition et PPCM
9. Identité et théorème de Bézout
10. Théorème de Gauss
11. Équations diophantiennes
12. Petit théorème de Fermat

📖 1. Divisibilité et multiples

🔑 Notions clés & Définitions

• Divisibilité : s’il existe un entier k tel que a = kb.

★ À maîtriser

📌 Si a divise b et c, alors a divise toute combinaison linéaire kb + k′c avec k et k′ entiers relatifs.

Compléments

• Pour tout entier a, 1 divise a, et tout entier non nul a divise 0.

• La somme de trois entiers consécutifs est divisible par 3, car ces entiers s’écrivent n − 1, n, n + 1 et leur somme vaut 3n.

💡 Astuce mémo

Diviseur → combinaison linéaire → nouveau multiple

📖 2. Division euclidienne

🔑 Notions clés & Définitions

• Division euclidienne : l’unique écriture a = bq + r avec 0 ≤ r < b.

★ À maîtriser

• Les restes possibles d’une division euclidienne par b sont les entiers de 0 à b − 1.

Compléments

• La division euclidienne de 38 367 par 251 donne le quotient 152 et le reste 215, car 38 367 = 251 × 152 + 215.

• Pour déterminer le reste de (n + 2)² dans la division par n + 4, on écrit (n + 2)² = n(n + 4) + 4, donc le reste vaut 4 lorsque n > 0.

💡 Astuce mémo

Dividende = diviseur × quotient + reste

📖 3. PGCD et algorithme d’Euclide

🔑 Notions clés & Définitions

• PGCD : leur plus grand diviseur commun, noté PGCD(a;b) ou a ∧ b.

★ À maîtriser

📌 Si a = bq + r avec r non nul, alors PGCD(a;b) = PGCD(b;r).

• L’algorithme d’Euclide consiste à effectuer des divisions successives en remplaçant chaque dividende par le diviseur précédent et chaque diviseur par le reste précédent, jusqu’à obtenir un reste nul.

Compléments

• L’algorithme d’Euclide donne PGCD(1636;1128) = 4.

💡 Astuce mémo

Diviser, remplacer par le reste, recommencer jusqu’à zéro

📖 4. Nombres premiers entre eux

🔑 Notions clés & Définitions

• Nombres premiers entre eux : leur PGCD est égal à 1.

★ À maîtriser

📐 Formule — Pour tout entier naturel non nul k, le PGCD vérifie $PGCD(ka,kb)=kPGCD(a,b)$.

Compléments

📌 Si d = PGCD(a;b), alors il existe des entiers k et k′ premiers entre eux tels que a = dk et b = dk′.

💡 Astuce mémo

PGCD égal à 1 : premiers entre eux ; PGCD supérieur à 1 : facteurs communs

📖 5. Congruences et opérations

🔑 Notions clés & Définitions

• Congruence : lorsqu’ils ont le même reste dans la division euclidienne par n, ce qui se note a ≡ b [n].

★ À maîtriser

📌 La congruence a ≡ b [n] équivaut à dire que a − b est un multiple de n.

📌 Si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n], ac ≡ bd [n] et a^p ≡ b^p [n] pour tout entier naturel p.

Compléments

• La congruence modulo n est une relation d’équivalence car elle est réflexive, symétrique et transitive.

💡 Astuce mémo

Même reste ↔ différence multiple du modulo

📖 6. Puissances modulo un entier

★ À maîtriser

• Pour calculer une puissance modulo un entier, on réduit d’abord la base, on cherche une puissance périodique congrue à 1, on réduit l’exposant selon cette période, puis on calcule le reste final.

Compléments

• Comme 23³ ≡ 1 [7] et 137 = 45 × 3 + 2, on obtient 23¹³⁷ ≡ 4 [7].

💡 Astuce mémo

Réduire la base, trouver une période, réduire l’exposant

📖 7. Nombres premiers

🔑 Notions clés & Définitions

• Nombre premier : lorsqu’il possède exactement deux diviseurs dans N : 1 et lui-même.

📝 Points essentiels

📌 Si un entier n > 2 n’est pas premier, il possède un diviseur premier p tel que 2 ≤ p ≤ √n.

• Il existe une infinité de nombres premiers.

💡 Astuce mémo

Premier : exactement deux diviseurs ; composé : davantage

📖 8. Décomposition et PPCM

🔑 Notions clés & Définitions

• PPCM : leur plus petit multiple strictement positif commun, noté PPCM(a;b) ou a ∨ b.

📝 Points essentiels

📌 Dans les décompositions en facteurs premiers, le PGCD utilise les facteurs communs avec leurs plus petits exposants, tandis que le PPCM utilise tous les facteurs avec leurs plus grands exposants.

📐 Formule — Pour deux entiers naturels non nuls, on a $ab=PGCD(a,b)\times PPCM(a,b)$.

💡 Astuce mémo

PGCD : petits exposants ; PPCM : grands exposants

📖 9. Identité et théorème de Bézout

📝 Points essentiels

📐 Formule — Si d = PGCD(a,b), il existe u et v entiers relatifs tels que $au+bv=d$.

📌 Deux entiers non nuls a et b sont premiers entre eux si et seulement s’il existe u et v entiers relatifs tels que au + bv = 1.

📌 L’équation ax + by = c possède des solutions entières si et seulement si c est un multiple de PGCD(a,b).

💡 Astuce mémo

PGCD égal à 1 → combinaison entière égale à 1

📖 10. Théorème de Gauss

★ À maîtriser

📌 Si a divise bc et si a est premier avec b, alors a divise c.

📌 Si un nombre premier p divise ab, alors p divise a ou p divise b.

Compléments

📌 Si b et c sont premiers entre eux et divisent a, alors bc divise a.

💡 Astuce mémo

Divisibilité d’un produit + coprimalité → divisibilité du second facteur

📖 11. Équations diophantiennes

🔑 Notions clés & Définitions

• Équation diophantienne : une équation linéaire ax + by = c à coefficients entiers dont on cherche les solutions entières.

★ À maîtriser

• Pour résoudre une équation diophantienne, on vérifie d’abord la divisibilité de c par PGCD(a,b), puis on trouve une solution particulière et on paramètre toutes les solutions avec un entier k.

Compléments

• Les solutions entières de 17x − 33y = 1 sont (x,y) = (33k + 2, 17k + 1) pour k entier.

💡 Astuce mémo

Vérifier le PGCD, trouver une solution, paramétrer toutes les solutions

📖 12. Petit théorème de Fermat

★ À maîtriser

📌 Si p est premier et si a n’est pas divisible par p, alors a^(p−1) ≡ 1 [p].

📌 Pour tout entier a et tout nombre premier p, on a a^p ≡ a [p].

Compléments

• Comme 7 est premier et ne divise pas 3, le petit théorème de Fermat donne 3^6 ≡ 1 [7], donc 3^(6n) − 1 est divisible par 7 pour tout entier naturel n. — Pierre de Fermat, 1640

💡 Astuce mémo

Modulo un nombre premier → les puissances se réduisent

📊 Tableaux de synthèse

PGCD et PPCM