Lernzettel: Arithmétique dans les entiers

📋 Plan du Cours

1. Divisibilité dans les entiers
2. Division euclidienne
3. Congruences modulo un entier
4. Classes modulo n
5. PGCD et algorithme d’Euclide
6. Bézout et théorème de Gauss
7. Équations diophantiennes
8. PPCM de plusieurs entiers
9. Nombres premiers et factorisation
10. Fermat et systèmes de numération
11. Systèmes de numération
12. Critères de divisibilité décimaux
13. PGCD et divisibilité
14. Puissances quatrièmes modulo 16
15. Résolution par factorisation
16. Congruences et suites périodiques
17. Nombre formé de chiffres 1

📖 1. Divisibilité dans les entiers

🔑 Notions clés & Définitions

• Divisibilité : Deux entiers relatifs a et b vérifient que a divise b s’il existe un entier relatif k tel que b = ka.

★ À maîtriser

• Un nombre pair s’écrit 2k et un nombre impair s’écrit 2k + 1, avec k entier relatif.

📌 Si a divise b et b divise c, alors a divise c.

📌 Si c divise a et b, alors c divise toute combinaison linéaire ma + nb avec m et n entiers relatifs.

Compléments

• Si un entier relatif N divise n et n + 1, alors N divise 1, donc N vaut 1 ou −1.

💡 Astuce mémo

Diviseur → combinaison linéaire → nouveau diviseur

📖 2. Division euclidienne

🔑 Notions clés & Définitions

• Division euclidienne : Pour a entier naturel et b entier naturel non nul, il existe un unique couple d’entiers (q,r) tel que a = bq + r avec 0 ≤ r < b.

★ À maîtriser

📌 Tout entier relatif s’écrit sous l’une des formes bq, bq + 1, bq + 2, jusqu’à bq + (b − 1), pour b ≥ 2.

Compléments

• Dans la division euclidienne de 41 par 5, on a 41 = 5 × 8 + 1, donc le quotient est 8 et le reste est 1.

• La division euclidienne de −5000 par 17 s’écrit −5000 = 17 × (−295) + 15, avec quotient −295 et reste 15.

💡 Astuce mémo

Dividende = diviseur × quotient + reste

📖 3. Congruences modulo un entier

🔑 Notions clés & Définitions

• Congruence modulo n : Deux entiers a et b sont congrus modulo n, avec n entier naturel non nul, lorsque a − b est divisible par n.

★ À maîtriser

📌 Deux entiers sont congrus modulo n si et seulement si leurs divisions euclidiennes par n ont le même reste.

📌 L’addition, la soustraction, la multiplication et les puissances entières naturelles sont compatibles avec les congruences modulo n.

Compléments

• De 12 ≡ 18 [6], on ne peut pas déduire que 12 : 3 ≡ 18 : 3 [6], car la division n’est pas toujours compatible avec les congruences.

💡 Astuce mémo

Même reste, différence divisible

📖 4. Classes modulo n

🔑 Notions clés & Définitions

• Classe d’équivalence : La classe d’équivalence de a modulo n est l’ensemble des entiers x tels que x ≡ a [n], soit l’ensemble {a + kn ; k ∈ ℤ}.
• Opérations sur les classes : Dans ℤ/nℤ, on définit x̅ + y̅ = (x + y)̅ et x̅ × y̅ = (xy)̅.

📝 Points essentiels

• Dans ℤ/2ℤ, il existe exactement deux classes : la classe des entiers pairs 0̅ et la classe des entiers impairs 1̅.

📌 Tout entier appartient à une unique classe parmi 0̅, 1̅, ..., n − 1̅, et ℤ/ nℤ contient exactement ces n classes.

💡 Astuce mémo

Les entiers rangés dans n classes périodiques

📖 5. PGCD et algorithme d’Euclide

🔑 Notions clés & Définitions

• PGCD : Le PGCD de deux entiers naturels non nuls est leur plus grand diviseur commun, noté PGCD(a ; b) ou a ∧ b.

★ À maîtriser

• L’algorithme d’Euclide calcule le PGCD en remplaçant successivement le couple (a,b) par (b,r), où r est le reste de la division de a par b, jusqu’au dernier reste non nul.

Compléments

• L’algorithme d’Euclide donne PGCD(252 ; 360) = 36, car 360 = 252 × 1 + 108, 252 = 108 × 2 + 36 et 108 = 36 × 3 + 0.

📐 Formule — Pour k entier naturel non nul, $\operatorname{PGCD}(ka,kb)=k\operatorname{PGCD}(a,b)$.

💡 Astuce mémo

Diviser, remplacer par le reste, recommencer

📖 6. Bézout et théorème de Gauss

🔑 Notions clés & Définitions

• Nombres premiers entre eux : Deux entiers relatifs non nuls sont premiers entre eux lorsque leur PGCD est égal à 1.

★ À maîtriser

📌 Si d est le PGCD de a et b, alors il existe des entiers relatifs u et v tels que au + bv = d.

📌 Deux entiers naturels 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.

Compléments

📌 Si a et b sont premiers entre eux et divisent tous deux c, alors ab divise c.

💡 Astuce mémo

PGCD égal à 1 → combinaison de Bézout → divisibilité

📖 7. Équations diophantiennes

★ À maîtriser

📌 L’équation ax + by = c possède une solution entière si et seulement si PGCD(a ; b) divise c.

• Lorsque l’équation ax + by = c est résoluble, toutes ses solutions entières s’obtiennent à partir d’une solution particulière en ajoutant les solutions de l’équation homogène.

• Les solutions entières de l’équation $7x+13y=119$ sont obtenues en posant y=7k puis x=17−13k, avec k entier.

Compléments

• Les solutions de 5x + 7y = 1 sont x = 7k − 4 et y = 3 − 5k, avec k entier relatif.

• Dans l’égalité de numération donnée, la solution est a=4, b=7 et c=5.

💡 Astuce mémo

Congruence → paramétrage → solutions entières

📖 8. PPCM de plusieurs entiers

🔑 Notions clés & Définitions

• PPCM : Le PPCM de deux entiers relatifs non nuls est le plus petit multiple commun strictement positif, noté PPCM(a ; b) ou a ∨ b.
• PGCD de plusieurs entiers : Le PGCD de plusieurs entiers est le plus grand entier positif qui divise chacun d’eux.

★ À maîtriser

📐 Formule — Pour deux entiers non nuls a et b, $\operatorname{PGCD}(a,b)\operatorname{PPCM}(a,b)=|ab|$.

Compléments

📌 Si a et b sont premiers entre eux, alors leur PPCM est égal à |ab|.

💡 Astuce mémo

PGCD : diviseurs communs ; PPCM : multiples communs

📖 9. Nombres premiers et factorisation

🔑 Notions clés & Définitions

• Nombre premier : Un entier naturel est premier s’il possède exactement deux diviseurs positifs distincts : 1 et lui-même.
• Décomposition en facteurs premiers : Tout entier naturel strictement supérieur à 1 se décompose de manière unique, à l’ordre près, en produit de facteurs premiers.

★ À maîtriser

📌 Tout entier naturel strictement supérieur à 1 et non premier possède un diviseur premier p tel que p ≤ √n.

📐 Formule — Si $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$, alors le nombre de diviseurs positifs de n est $\prod_{i=1}^{r}(\alpha_i+1)$.

Compléments

• Si a et b ont les mêmes facteurs premiers, le PGCD utilise l’infimum des exposants et le PPCM utilise le supremum des exposants.

💡 Astuce mémo

Chaque entier se construit comme un produit de briques premières

📖 10. Fermat et systèmes de numération

🔑 Notions clés & Définitions

• Système de numération : Dans une base b, le nombre représenté par aₙaₙ₋₁…a₁a₀ s’écrit N = aₙbⁿ + aₙ₋₁bⁿ⁻¹ + ⋯ + a₁b + a₀, avec des chiffres strictement inférieurs à b.

★ À maîtriser

📌 Si p est premier, alors pour tout entier relatif a, $a^p\equiv a\ [p]$.

📌 Si p est premier et ne divise pas a, alors $a^{p-1}\equiv 1\ [p]$.

Compléments

• L’écriture 1101 en base 2 représente 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 13 en base 10.

📖 11. Systèmes de numération

🔑 Notions clés & Définitions

• Système de position : Dans un système de position de base b, le nombre représenté par \overline{a_na_{n-1}\ldots a_1a_0}_{(b)} s’écrit de manière unique comme $N=a_n b^n+a_{n-1}b^{n-1}+\cdots+a_1b+a_0$, où chaque chiffre est strictement inférieur à b.

📝 Points essentiels

• En base 2, $\overline{1101}_{(2)}=1\times2^3+1\times2^2+0\times2+1=13$, tandis qu’en base 6, $\overline{223}_{(6)}=2\times6^2+2\times6+3=79$.

💡 Astuce mémo

Chaque chiffre occupe une place et pèse selon une puissance de la base

📖 12. Critères de divisibilité décimaux

📝 Points essentiels

📌 Pour un entier décimal x dont les chiffres sont a_n\ldots a_0, x est divisible par 5 si et seulement si a_0 vaut 0 ou 5.

📌 Un entier décimal x est divisible par 25 si et seulement si ses deux derniers chiffres appartiennent à {00, 25, 50, 75}.

📌 Un entier décimal x est divisible par 4 si et seulement si le nombre formé par ses deux derniers chiffres est divisible par 4.

📌 Un entier décimal x est divisible par 3, respectivement par 9, si et seulement si la somme de ses chiffres est divisible par 3, respectivement par 9.

📌 Un entier décimal x est divisible par 11 si et seulement si la somme alternée de ses chiffres vérifie $\sum_{i=0}^{n}(-1)^i a_i\equiv0\pmod{11}$.

💡 Astuce mémo

Derniers chiffres, somme, alternance : 5-25-4, 3-9, 11

📖 13. PGCD et divisibilité

📝 Points essentiels

📌 Pour tout entier naturel n non nul, $\gcd(n,2n+1)=1$ et $\gcd(n^2{,}2n+1)=1$.

• Pour tout entier naturel n, si a=4n+3 et b=3n+1, alors $\gcd(a,b)=\gcd(n+2{,}5)$.

📌 Avec a=4n+3 et b=3n+1, on a $\gcd(a,b)=5$ si et seulement si $n\equiv3\pmod5$, c’est-à-dire n=5k+3 avec k naturel.

💡 Astuce mémo

Une combinaison linéaire conserve les diviseurs communs, donc simplifie le PGCD

📖 14. Puissances quatrièmes modulo 16

📝 Points essentiels

📌 Pour tout entier x, x⁴≡0 modulo 16 si x est pair et x⁴≡1 modulo 16 si x est impair.

• Si a et b sont premiers entre eux et c=a⁴+b⁴, alors c≡1 modulo 16 ou c≡2 modulo 16.

💡 Astuce mémo

Entier pair → 0 modulo 16 ; entier impair → 1 modulo 16

📖 15. Résolution par factorisation

📝 Points essentiels

• L’équation $x^2-y^2=12$ équivaut à $(x-y)(x+y)=12$, et ses solutions entières sont (4,2), (4,−2), (−4,−2) et (−4,2).

• Les solutions entières de $4x^2-9y^2=432$ sont (12,4), (12,−4), (−12,−4) et (−12,4).

💡 Astuce mémo

Différence de carrés → diviseurs de 12 → parité → couples

📖 16. Congruences et suites périodiques

★ À maîtriser

📌 Les puissances de 2 modulo 5 sont périodiques de période 4 : si n≡0,1,2,3 modulo 4, alors respectivement $2^n\equiv1{,}2{,}4{,}3\pmod5$.

Compléments

📌 Pour a=4n+3 et b=3n+1, la congruence $2a+3b\equiv0\pmod5$ est équivalente à $2a+b\equiv4\pmod5$.

• Le plus petit entier naturel supérieur à 20 satisfaisant les conditions données est 38.

💡 Astuce mémo

Les puissances de 2 modulo 5 suivent le cycle 1, 2, 4, 3

📖 17. Nombre formé de chiffres 1

🔑 Notions clés & Définitions

• Nombre N : L’entier décimal formé de 2010 chiffres 1 consécutifs.

📝 Points essentiels

• Le nombre N est divisible par 11, car sa somme alternée comporte 1005 couples (1−1) et vaut donc 0 modulo 11.

📐 Formule — La relation entre N et sa forme géométrique est $10^{2010}-1=9N$.

• 2011 est un nombre premier et, par le théorème de Fermat, $10^{2010}\equiv1\pmod{2011}$, donc 2011 divise 9N puis N.

• Le nombre N est divisible par 22121, car $22121=11\times2011$ et 11 et 2011 sont premiers entre eux.

💡 Astuce mémo

Alternance modulo 11 et théorème de Fermat → divisibilité par 11, 2011 puis 22121

📊 Tableaux de synthèse

Comparaison PGCD et PPCM

Notion	Définition	Relation
PGCD	Plus grand diviseur commun	Divise a et b
PPCM	Plus petit multiple commun positif	Est multiple de a et b

Critères de divisibilité

Diviseur	Critère	Élément observé
5	Dernier chiffre égal à 0 ou 5	a₀
25	Deux derniers chiffres dans {00, 25, 50, 75}	a₁a₀
3 ou 9	Somme des chiffres divisible par 3 ou 9	Σaᵢ
11	Somme alternée divisible par 11	Σ(−1)ⁱaᵢ