Revision sheet: Cours sur la Théorie des Nombres

📋 Plan du Cours

1. Divisibilité et multiples
2. Division euclidienne
3. Congruence modulo n
4. Petit théorème de Fermat
5. PGCD et algorithme d’Euclide
6. Nombres premiers
7. Nombres premiers entre eux
8. PPCM et inverses modulo n
9. Identité de Bézout et équations diophantiennes

📖 1. Divisibilité et multiples

🔑 Notions clés & Définitions

• Division dans Z : On dit que b divise a s’il existe un entier relatif q tel que a = bq.
• Notation b|a : La notation b|a signifie que b divise a, donc que a s’écrit comme un multiple de b.
• Multiple d’un entier : Un entier a est un multiple de b quand il existe un entier q tel que a = bq.
• Diviseur : Un entier b est un diviseur de a s’il existe un entier q tel que a = bq.

📝 Points essentiels

• Si a n’est pas un multiple de b alors b ne divise pas a.
• Tout entier a est divisible par 1 et par −1.
• Si b|a alors b|a^k pour tout k ∈ Z et b|a^n pour tout n ∈ N*.
• Si a|b et b|a alors a = ±b.
• Si c|a et c|b alors c divise au + bv quels que soient u et v entiers relatifs.

📖 2. Division euclidienne

🔑 Notions clés & Définitions

• Division euclidienne dans Z : Pour a ∈ Z et b ∈ Z*, on écrit a = bq + r avec 0 ≤ r < |b|, où q est le quotient et r le reste.
• Quotient : Le quotient q est l’entier de la division euclidienne qui permet d’obtenir a = bq + r.
• Reste euclidien : Le reste r est l’entier vérifiant 0 ≤ r < |b| dans l’égalité a = bq + r.

📝 Points essentiels

• Le couple (q,r) de la division euclidienne avec 0 ≤ r < |b| est unique.
• Si b > 0 alors q = E(a/b), où E désigne la partie entière.
• Si b < 0 alors q = −E(−a/b).

📖 3. Congruence modulo n

🔑 Notions clés & Définitions

• Congruence modulo n : On a a ≡ b (mod n) quand a − b est un multiple de n, avec n entier naturel non nul.
• Écriture a ≡ 0 (mod n) : L’écriture a ≡ 0 (mod n) signifie que n divise a.
• Reste modulo n : Pour tout a, il existe un unique r ∈ {0,1,...,n−1} tel que a ≡ r (mod n), et r est le reste modulo n.

📝 Points essentiels

• a ≡ b (mod n) ⇔ n divise a − b.
• Si d divise n et a ≡ b (mod n), alors a ≡ b (mod d).
• Si a ≡ r (mod n) avec 0 ≤ r < n, alors r est le reste de la division euclidienne de a par n.
• La congruence est compatible avec addition et multiplication : si a ≡ b (mod n) et a' ≡ b' (mod n) alors a+a' ≡ b+b' (mod n) et aa' ≡ bb' (mod n).
• Si a ≡ b (mod n) alors a^k ≡ b^k (mod n) pour tout entier naturel k non nul.

📖 4. Petit théorème de Fermat

🔑 Notions clés & Définitions

• Petit théorème de Fermat : Pour p premier et a non divisible par p, on a a^{p−1} ≡ 1 (mod p).
• Condition p premier avec a : Le texte relie le fait que p ne divise pas a à l’appartenance de p et a dans la condition du théorème.
• Corollaire a^p ≡ a (mod p) : Le corollaire affirme une congruence valable pour tout entier naturel a quand p est premier.

📝 Points essentiels

• Si p est premier et p ∤ a alors a^{p−1} ≡ 1 (mod p).
• p ∤ a équivaut à dire que a est premier avec p.
• Corollaire : pour p premier et tout a ∈ N, on a a^p ≡ a (mod p).

📖 5. PGCD et algorithme d’Euclide

🔑 Notions clés & Définitions

• PGCD : Le plus grand commun diviseur de a et b est l’entier naturel d noté pgcd(a,b) ou a ∧ b qui divise a et b et dont tout diviseur commun divise aussi d.
• Notation a ∧ b : La notation a ∧ b désigne le pgcd de a et b.
• Suite des divisions euclidiennes : Dans l’algorithme d’Euclide, on obtient une suite de restes successifs et le dernier reste non nul est le pgcd.
• Propriété pgcd(a,b)=pgcd(b,r) : Dans une division a = bq + r, le pgcd de a et b coïncide avec le pgcd de b et r.

📝 Points essentiels

• Si a = bq + r alors pgcd(a,b) = pgcd(b,r).
• Si b divise a alors pgcd(a,b) = |b|.
• Le pgcd est symétrique : pgcd(a,b)=pgcd(b,a).
• Pour tout entier non nul k, pgcd(ka,kb)=|k|·pgcd(a,b).
• Le pgcd(a,b) est le dernier reste non nul de la succession des divisions euclidiennes de a par b.

📖 6. Nombres premiers

🔑 Notions clés & Définitions

• Nombre premier : Un entier naturel p est premier s’il admet exactement deux diviseurs entiers naturels distincts.
• Infinité des nombres premiers : Le cours affirme que l’ensemble des nombres premiers n’est pas fini.
• Décomposition en facteurs premiers : Tout entier n ≥ 2 se décompose de façon unique en un produit de puissances de nombres premiers.

📝 Points essentiels

• Pour n ≥ 2, n admet au moins un diviseur premier.
• Si n n’est pas premier, il existe un diviseur premier p de n tel que p ≤ √n.
• Contraposée : si n n’est divisible par aucun nombre premier ≤ √n, alors n est premier.
• L’ensemble des nombres premiers P est infini.
• Décomposition unique : n = p1^{α1}·p2^{α2}····pm^{αm} avec p1 < p2 < ... < pm et αi entiers naturels non nuls.

📖 7. Nombres premiers entre eux

🔑 Notions clés & Définitions

• Premiers entre eux : Deux entiers a et b sont premiers entre eux si leur pgcd vaut 1.
• Lemme de Gauss : Le lemme de Gauss relie une divisibilité par produit à une divisibilité par un facteur quand les facteurs sont premiers entre eux.
• Conséquence produit sous congruences : Quand n et m sont premiers entre eux, les congruences modulo n et modulo m se combinent en une congruence modulo n·m.
• Propriété pgcd(a,b)=d : Le cours donne une caractérisation de pgcd via l’écriture a = da' et b = db' avec pgcd(a',b')=1.

📝 Points essentiels

• pgcd(a,b)=d ⇔ il existe a',b' tels que a=da' et b=db' avec pgcd(a',b')=1.
• Si a est premier et a ne divise pas b, alors a et b sont premiers entre eux.
• Lemme de Gauss : si a|bc et pgcd(a,b)=1 alors a|c.
• Théorème : si pgcd(a,b)=1 et a|n et b|n alors ab|n.
• Conséquence : si pgcd(n,m)=1, alors x ≡ x' (mod n) et x ≡ x' (mod m) ⇔ x ≡ x' (mod m·n).

📖 8. PPCM et inverses modulo n

🔑 Notions clés & Définitions

• PPCM : Le plus petit commun multiple M de a et b est le seul entier naturel non nul tel que M soit multiple de a et de b et que tout multiple commun de a et b soit multiple de M.
• Notation a ∨ b : Le cours note a ∨ b le ppcm de a et b.
• Inverse modulo b : Un entier u est un inverse de a modulo b s’il vérifie au ≡ 1 (mod b) avec u dans {1,...,b−1}.

📝 Points essentiels

• Le ppcm vérifie a ∨ b = |a| ∨ |b| et (a ∨ b)(a ∧ b)=|ab|.
• Si b|a alors a ∧ b = |a| (donc le pgcd s’évalue directement dans ce cas).
• Pour tout k non nul, (ka) ∨ (kb) = |k|·(a ∨ b).
• Si pgcd(a,b)=1 et b ≥ 2, alors il existe un unique u ∈ {1,...,b−1} tel que au ≡ 1 (mod b).
• Exemple donné : 3 est un inverse de 5 modulo 7.

📖 9. Identité de Bézout et équations diophantiennes

🔑 Notions clés & Définitions

• Identité de Bézout : Deux entiers non nuls a et b sont premiers entre eux si et seulement s’il existe des entiers u et v tels que au + bv = 1.
• Équation diophantienne : Une équation diophantienne est une équation de la forme ax + by = c où a,b,c sont entiers et x,y sont des entiers relatifs.
• Condition d’existence des solutions : Pour l’équation ax + by = c, l’existence de solutions dans Z^2 dépend du partage de c par le pgcd de a et b.
• Remontée dans l’algorithme d’Euclide : La méthode consiste à exprimer le pgcd via les restes successifs puis à remonter pour obtenir une combinaison donnant c.

📝 Points essentiels

• Si a ∧ b = 1 alors au + bv = 1 pour certains u et v entiers.
• Application : si a ∧ b = 1 et a ∧ c = 1 alors a ∧ (bc) = 1.
• Si a ∧ b = 1 alors a ∧ b^2 = 1.
• Équation diophantienne : ax + by = c admet des solutions dans Z^2 ⇔ pgcd(a,b) divise c.
• Exemple : 616x + 585y = 12 admet une solution particulière (x,y)=(1812,−1908).

⚠️ Pièges & confusions fréquents

1. Confondre b|a avec a|b : l’ordre compte et change la condition.
2. Croire que a ≡ b (mod n) impose a=b : la congruence permet des écarts multiples de n.
3. Oublier la forme du reste euclidien : le reste r vérifie 0 ≤ r < |b|.
4. Appliquer le petit théorème de Fermat quand p divise a : la congruence a^{p−1} ≡ 1 (mod p) n’est valable que si p ∤ a.
5. Penser que “équations diophantiennes” demandent une solution si et seulement si c=1 : la condition réelle est que pgcd(a,b) divise c.
6. Croire que la réciproque de Bézout “au + bv = 1 ⇒ a ∧ b = 1” est immédiate dans l’autre sens : le cours précise seulement l’équivalence dans le cadre “premiers entre eux”.
7. Mélanger pgcd et ppcm : le cours utilise a ∧ b pour le pgcd et a ∨ b pour le ppcm, avec des relations différentes.

✅ Checklist Examen

1. Savoir donner la définition de la divisibilité b|a dans Z et en déduire ce que signifie “multiple” et “diviseur”.
2. Utiliser les propriétés : si b|a alors b divise les puissances de a, et reconnaître le cas a|b et b|a ⇒ a=±b.
3. Savoir énoncer le résultat de la division euclidienne a=bq+r avec 0≤r<|b| et l’unicité du couple (q,r).
4. Calculer le quotient q via la formule avec la partie entière E selon le signe de b.
5. Passer entre a ≡ b (mod n) et n|(a−b), puis entre a ≡ 0 (mod n) et n|a.
6. Décrire l’existence et l’unicité du reste modulo n dans {0,...,n−1} et le lien avec la division euclidienne.
7. Appliquer le petit théorème de Fermat : identifier quand p ∤ a, puis écrire a^{p−1} ≡ 1 (mod p) et le corollaire a^p ≡ a (mod p).
8. Calculer ou caractériser le pgcd avec les propriétés : pgcd(a,b)=pgcd(b,r) dans a=bq+r et dernier reste non nul de l’algorithme d’Euclide.
9. Utiliser la définition de nombre premier (exactement deux diviseurs) et les résultats de divisibilité par un premier ≤ √n.
10. Reconnaître quand deux entiers sont premiers entre eux (pgcd=1) et utiliser le lemme de Gauss et la règle “si a|n et b|n et pgcd(a,b)=1 alors ab|n”.
11. Décrire le ppcm a ∨ b (plus petit multiple commun) et utiliser la relation (a ∨ b)(a ∧ b)=|ab|.
12. Appliquer l’existence/unicité de l’inverse modulo b pour pgcd(a,b)=1 et b≥2, y compris l’intervalle de u.
13. Résoudre une équation diophantienne ax+by=c : vérifier la condition pgcd(a,b)|c puis obtenir une solution particulière par remontée avec Euclide (comme dans l’exemple).