Aller au contenu principal
MathExcellence
← Tous les cours
9

2ᵉ Bac · Sciences Maths · Chapitre 9

Arithmétique dans ℤ

L'arithmétique dans ℤ est l'une des signatures du programme de Sciences Mathématiques. Ce cours présente la division euclidienne, l'algorithme d'Euclide, le PGCD et le PPCM, les théorèmes de Bézout et de Gauss, les congruences et la résolution des équations diophantiennes. C'est un domaine où la démonstration l'emporte sur le calcul : on y attend un raisonnement d'une rigueur totale. Vous apprendrez notamment à traduire un problème de divisibilité en congruences modulo n, souvent le chemin le plus court vers la solution. Très présente dans les sujets d'examen national, l'arithmétique récompense la logique et la précision : ce cours vous en pose méthodiquement les bases.

1 · Résumé du cours

L'arithmétique est un chapitre emblématique de la filière Sciences Maths : elle demande moins de calcul que de raisonnement. Chaque théorème y a des conditions d'application précises, qu'il faut citer explicitement — c'est là que se gagnent (ou se perdent) les points.

1.1 Divisibilité & division euclidienne

Divisibilité aa divise bb (noté a∣ba\mid b) s'il existe k∈Zk\in\mathbb{Z} tel que b=kab=ka ; bb est alors un multiple de aa. Règles : a∣aa\mid a, 1∣a1\mid a, a∣0a\mid 0 ; transitivité (a∣ba\mid b et b∣c⇒a∣cb\mid c\Rightarrow a\mid c) ; a∣ba\mid b et a∣c⇒a∣(bu+cv)a\mid c\Rightarrow a\mid(bu+cv) ; a∣ba\mid b et b∣a⇒a=±bb\mid a\Rightarrow a=\pm b.
Division euclidienne Pour tout a∈Za\in\mathbb{Z} et tout b≠0b\neq0, il existe un unique couple (q,r)(q,r) tel que \boxed{\,a=bq+r,\ \ 0\le r<|b|\,}. qq est le quotient, rr le reste.
L'unicité est la clé Ce n'est pas l'existence qui rend la division euclidienne utile, mais l'unicité de (q,r)(q,r). C'est elle qui autorise à raisonner « le reste vaut nécessairement… » et qui fonde toute la théorie des congruences.

1.2 PGCD & algorithme d'Euclide

PGCD & premiers entre eux Le PGCD de a,ba,b (non tous deux nuls) est leur plus grand diviseur commun, noté pgcd⁡(a,b)\operatorname{pgcd}(a,b) ou a∧ba\wedge b. Ils sont premiers entre eux lorsque a∧b=1a\wedge b=1.
Algorithme d'Euclide Si rr est le reste de aa par b (b≠0)b\ (b\neq0), alors  pgcd⁡(a,b)=pgcd⁡(b,r) \boxed{\,\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)\,}. On répète jusqu'à un reste nul : le dernier reste non nul est le PGCD. Si d=a∧bd=a\wedge b, alors a=da′a=da', b=db′b=db' avec a′∧b′=1a'\wedge b'=1.
Exemple 252=2×105+42252=2\times105+42, 105=2×42+21105=2\times42+21, 42=2×21+042=2\times21+0. Dernier reste non nul : pgcd⁡(252,105)=21\operatorname{pgcd}(252,105)=21.

1.3 Le PPCM

PPCM Le PPCM de a,ba,b non nuls est le plus petit de leurs multiples communs strictement positifs, noté ppcm⁡(a,b)\operatorname{ppcm}(a,b) ou a∨ba\vee b.
Relation fondamentale & décompositions  pgcd⁡(a,b)×ppcm⁡(a,b)=∣ab∣ \boxed{\,\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|\,} (donc si a∧b=1a\wedge b=1, ppcm⁡=∣ab∣\operatorname{ppcm}=|ab|). Sur les décompositions : pgcd⁡=∏pimin⁡(αi,βi)\operatorname{pgcd}=\prod p_i^{\min(\alpha_i,\beta_i)}, ppcm⁡=∏pimax⁡(αi,βi)\operatorname{ppcm}=\prod p_i^{\max(\alpha_i,\beta_i)}. De plus mm est multiple commun   ⟺  ppcm⁡(a,b)∣m\iff\operatorname{ppcm}(a,b)\mid m.
min et max Le PGCD prend les plus petits exposants, le PPCM les plus grands. Comme min⁡(α,β)+max⁡(α,β)=α+β\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta, la relation pgcd⁡×ppcm⁡=∣ab∣\operatorname{pgcd}\times\operatorname{ppcm}=|ab| en découle. Exemple : ppcm⁡(252,105)=252×10521=1260\operatorname{ppcm}(252,105)=\frac{252\times105}{21}=1260.
Piège — plusieurs entiers Pour n≥3n\ge3 entiers : « premiers entre eux dans leur ensemble » (pgcd⁡(a1,…,an)=1\operatorname{pgcd}(a_1,\dots,a_n)=1) est plus faible que « deux à deux » (pgcd⁡(ai,aj)=1\operatorname{pgcd}(a_i,a_j)=1). Ex : 6,10,156,10,15 : pgcd⁡=1\operatorname{pgcd}=1 mais pgcd⁡(6,10)=2\operatorname{pgcd}(6,10)=2. PGCD/PPCM se calculent de proche en proche : pgcd⁡(a1,…,an)=pgcd⁡(pgcd⁡(a1,…,an−1),an)\operatorname{pgcd}(a_1,\dots,a_n)=\operatorname{pgcd}\big(\operatorname{pgcd}(a_1,\dots,a_{n-1}),a_n\big). La relation pgcd⁡×ppcm⁡=∣ab∣\operatorname{pgcd}\times\operatorname{ppcm}=|ab| ne se généralise PAS à trois entiers.

1.4 Bézout & Gauss

Identité de Bézout a∧b=1  ⟺  a\wedge b=1\iff il existe u,v∈Zu,v\in\mathbb{Z} tels que  au+bv=1 \boxed{\,au+bv=1\,}. Plus généralement, il existe toujours u,vu,v tels que au+bv=pgcd⁡(a,b)au+bv=\operatorname{pgcd}(a,b). Bézout généralisé : pgcd⁡(a1,…,an)=1  ⟺  ∃ ui, ∑aiui=1\operatorname{pgcd}(a_1,\dots,a_n)=1\iff\exists\,u_i,\ \sum a_i u_i=1.
Théorème de Gauss Si a∣bca\mid bc et a∧b=1a\wedge b=1, alors  a∣c \boxed{\,a\mid c\,}.
La condition oubliée (erreur nº1) Gauss n'est vrai qu'à condition que aa soit premier avec bb. Sans elle, faux : 6∣4×36\mid 4\times3 mais 66 ne divise ni 44 ni 33. Citez toujours cette condition.
Méthodes
  • Prouver a∧b=1a\wedge b=1 : exhiber une combinaison de Bézout au+bv=1au+bv=1 (plus rapide que calculer le PGCD).
  • Couple de Bézout : écrire les divisions d'Euclide, puis remonter en isolant le PGCD et en remplaçant les restes ligne après ligne.

1.5 Équations diophantiennes ax+by=cax+by=c

Existence & structure Soit d=a∧bd=a\wedge b. (E):ax+by=c(E):ax+by=c admet des solutions dans Z2\mathbb{Z}^{2}   ⟺   d∣c \iff\boxed{\,d\mid c\,}. Si (x0,y0)(x_0,y_0) est une solution particulière et a=da′a=da', b=db′b=db' (a′∧b′=1a'\wedge b'=1), l'ensemble des solutions est  {(x0+kb′, y0−ka′) : k∈Z} \boxed{\,\{(x_0+kb',\ y_0-ka')\ :\ k\in\mathbb{Z}\}\,}
Méthode — résoudre ax+by=cax+by=c ① Calculer d=a∧bd=a\wedge b, tester d∣cd\mid c (sinon aucune solution). ② Simplifier par dd : a′x+b′y=c′a'x+b'y=c', a′∧b′=1a'\wedge b'=1. ③ Solution particulière (à vue ou par remontée d'Euclide). ④ Solution générale (x0+kb′, y0−ka′)(x_0+kb',\,y_0-ka'). ⑤ Vérifier (les kk disparaissent).
Les deux fautes d'examen Oublier de tester d∣cd\mid c avant de calculer ; et intervertir a′a' et b′b' dans la solution générale. Retenez : le coefficient de kk dans xx est celui de l'autre inconnue (b′b'), avec changement de signe pour yy. La vérification lève tout doute.

1.6 Nombres premiers

Définition & décomposition p≥2p\ge2 est premier s'il n'a que deux diviseurs positifs : 11 et lui-même. Tout n≥2n\ge2 se décompose de manière unique (à l'ordre près) : n=p1α1⋯pkαkn=p_1^{\alpha_1}\cdots p_k^{\alpha_k}. Si pp premier et p∣abp\mid ab, alors p∣ap\mid a ou p∣bp\mid b. Pour tester nn, il suffit de vérifier qu'aucun premier p≤np\le\sqrt n ne le divise.
Nombre de diviseurs Si n=p1α1⋯pkαkn=p_1^{\alpha_1}\cdots p_k^{\alpha_k}, les diviseurs positifs sont les p1β1⋯pkβkp_1^{\beta_1}\cdots p_k^{\beta_k} avec 0≤βi≤αi0\le\beta_i\le\alpha_i, et leur nombre est  τ(n)=(α1+1)(α2+1)⋯(αk+1) \boxed{\,\tau(n)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\,}.
Pourquoi ce produit — & infinité des premiers Choisir un diviseur = choisir indépendamment chaque exposant βi\beta_i parmi αi+1\alpha_i+1 valeurs ; d'où le produit. Ex : 360=23×32×5360=2^{3}\times3^{2}\times5, τ(360)=4×3×2=24\tau(360)=4\times3\times2=24. — Il existe une infinité de premiers : sinon, N=p1⋯pk+1N=p_1\cdots p_k+1 aurait un diviseur premier pip_i qui diviserait NN et p1⋯pkp_1\cdots p_k, donc 11 : impossible.
Petit théorème de Fermat Soit pp premier. Si p∤ap\nmid a :  a p−1≡1 [p] \boxed{\,a^{\,p-1}\equiv1\ [p]\,}. Pour tout aa :  a p≡a [p] \boxed{\,a^{\,p}\equiv a\ [p]\,}.
Deux conditions à surveiller pp doit être premier, et la première forme exige p∤ap\nmid a. La seconde forme (ap≡aa^{p}\equiv a) est valable sans restriction — celle qu'on utilise quand on ignore si p∣ap\mid a.

1.7 Les congruences

Définition Pour n≥1n\ge1 : a≡b [n]a\equiv b\ [n] lorsque n∣(a−b)n\mid(a-b), c'est-à-dire lorsque aa et bb ont le même reste dans la division par nn.
Compatibilité avec les opérations Si a≡b [n]a\equiv b\ [n] et c≡d [n]c\equiv d\ [n], alors a+c≡b+da+c\equiv b+d, ac≡bdac\equiv bd, ak≡bk [n]a^{k}\equiv b^{k}\ [n].
À quoi servent les congruences Elles remplacent un nombre par son reste — souvent minuscule. Pour 21002^{100} modulo 77, on cherche un petit exposant où 2k≡12^{k}\equiv1, puis on exploite la périodicité. Des calculs gigantesques deviennent de l'arithmétique de poche.
Simplifier avec précaution ac≡bc [n]ac\equiv bc\ [n] et c∧n=1 ⇒ a≡b [n]c\wedge n=1\ \Rightarrow\ a\equiv b\ [n]. Sans c∧n=1c\wedge n=1, faux : 2×3≡2×0 [6]2\times3\equiv2\times0\ [6] mais 3≢0 [6]3\not\equiv0\ [6].
Critères de divisibilité (en 3 lignes) Avec N=∑ak10kN=\sum a_k 10^{k} : 10≡1 [9]⇒N≡∑ak10\equiv1\ [9]\Rightarrow N\equiv\sum a_k (div. par 99 ou 33   ⟺  \iff somme des chiffres) ; 10≡−1 [11]⇒N≡∑(−1)kak10\equiv-1\ [11]\Rightarrow N\equiv\sum(-1)^{k}a_k (div. par 1111   ⟺  \iff somme alternée) ; 10k≡0 [4]10^{k}\equiv0\ [4] si k≥2k\ge2 (div. par 44   ⟺  \iff deux derniers chiffres).

1.8 L'anneau Z/nZ\mathbb{Z}/n\mathbb{Z}

Classes de congruence La classe de aa modulo nn est aˉ={x∈Z:x≡a [n]}={a+kn:k∈Z}\bar a=\{x\in\mathbb{Z}:x\equiv a\ [n]\}=\{a+kn:k\in\mathbb{Z}\}. On a aˉ=bˉ  ⟺  a≡b [n]\bar a=\bar b\iff a\equiv b\ [n] : deux classes sont égales ou disjointes (elles partitionnent Z\mathbb{Z}). Il y a exactement nn classes :  Z/nZ={0ˉ,1ˉ,…,n−1‾} \boxed{\,\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}\,}.
Structure d'anneau On pose aˉ+bˉ=a+b‾\bar a+\bar b=\overline{a+b} et aˉ×bˉ=ab‾\bar a\times\bar b=\overline{ab}. Ces opérations sont bien définies (indépendantes des représentants — c'est la compatibilité des congruences), et (Z/nZ,+,×)(\mathbb{Z}/n\mathbb{Z},+,\times) est un anneau commutatif unitaire, de zéro 0ˉ\bar0, d'unité 1ˉ\bar1.
Table de Z/5Z\mathbb{Z}/5\mathbb{Z} (×) ×0ˉ1ˉ2ˉ3ˉ4ˉ0ˉ0ˉ0ˉ0ˉ0ˉ0ˉ1ˉ0ˉ1ˉ2ˉ3ˉ4ˉ2ˉ0ˉ2ˉ4ˉ1ˉ3ˉ3ˉ0ˉ3ˉ1ˉ4ˉ2ˉ4ˉ0ˉ4ˉ3ˉ2ˉ1ˉ\begin{array}{c|ccccc} \times & \bar0 & \bar1 & \bar2 & \bar3 & \bar4\\\hline \bar0 & \bar0 & \bar0 & \bar0 & \bar0 & \bar0\\ \bar1 & \bar0 & \bar1 & \bar2 & \bar3 & \bar4\\ \bar2 & \bar0 & \bar2 & \bar4 & \bar1 & \bar3\\ \bar3 & \bar0 & \bar3 & \bar1 & \bar4 & \bar2\\ \bar4 & \bar0 & \bar4 & \bar3 & \bar2 & \bar1 \end{array} Chaque ligne non nulle contient un 1ˉ\bar1 : tout élément non nul est inversible (ex. 2ˉ×3ˉ=1ˉ\bar2\times\bar3=\bar1, donc 2ˉ−1=3ˉ\bar2^{-1}=\bar3).
0 1 2 3 4 5 6 7 8 9 10 11
Z/12Z\mathbb{Z}/12\mathbb{Z} : les 1212 classes disposées en cercle. On « tourne en rond » : 12≡012\equiv0, 13≡113\equiv1, −1≡11-1\equiv11… C'est l'arithmétique de l'horloge, image concrète des congruences.
Inversibles & corps aˉ\bar a est inversible (pour ×\times)   ⟺   a∧n=1 \iff\boxed{\,a\wedge n=1\,} (Bézout : au+nv=1⇒aˉ−1=uˉau+nv=1\Rightarrow\bar a^{-1}=\bar u). Et (Z/nZ,+,×)(\mathbb{Z}/n\mathbb{Z},+,\times) est un corps   ⟺  n\iff n est premier : pour pp premier, tous les éléments non nuls de Z/pZ\mathbb{Z}/p\mathbb{Z} sont inversibles.
Corps   ⟺  \iff premier — le contraste Dans Z/6Z\mathbb{Z}/6\mathbb{Z} : 2ˉ×3ˉ=0ˉ\bar2\times\bar3=\bar0 avec 2ˉ,3ˉ≠0ˉ\bar2,\bar3\neq\bar0 — des diviseurs de zéro, donc pas un corps (66 non premier). Dans Z/5Z\mathbb{Z}/5\mathbb{Z} : aucun produit de non-nuls n'est nul, tout non-nul est inversible — un corps (55 premier). C'est l'exemple fondamental de corps fini, et il éclaire Fermat : les p−1p-1 classes non nulles forment un groupe multiplicatif, d'où aˉ p−1=1ˉ\bar a^{\,p-1}=\bar1.

1.9 Systèmes de numération

Écriture en base bb Soit b≥2b\ge2. Tout N≥1N\ge1 s'écrit de manière unique N=anbn+⋯+a1b+a0N=a_n b^{n}+\dots+a_1 b+a_0, 0\le a_i<b, an≠0a_n\neq0 ; on note N=an…a0‾ bN=\overline{a_n\dots a_0}^{\,b}. En base b>10b>10, on utilise A=10,…,F=15A=10,\dots,F=15 (hexadécimal, b=16b=16 ; binaire, b=2b=2).
Méthode — changer de base Base b→b\tobase 1010 : développer ∑aibi\sum a_i b^{i}. Base 10→10\tobase bb : divisions euclidiennes successives par bb ; les restes, lus du dernier au premier (de bas en haut), donnent les chiffres. Un entier est divisible par bb   ⟺  \iff son dernier chiffre est nul (N≡a0 [b]N\equiv a_0\ [b]).
Calculer en base bb On pose l'opération comme en base 1010, mais on retient dès que l'on atteint bb : à chaque colonne, si le total vaut ss, on écrit s mod bs\bmod b et on reporte ⌊s/b⌋\lfloor s/b\rfloor. Ex : 45=101101‾ 245=\overline{101101}^{\,2} (car 32+8+4+1=4532+8+4+1=45) ; 34‾ 5+23‾ 5=112‾ 5\overline{34}^{\,5}+\overline{23}^{\,5}=\overline{112}^{\,5} (car 19+13=3219+13=32).

2 · Feuille de route

L'ordre conseillé pour maîtriser le chapitre.

1

Division euclidienne

a=bq+ra=bq+r, 0\le r<|b| : unicité de (q,r)(q,r).

2

PGCD / PPCM

Euclide ; pgcd⁡×ppcm⁡=∣ab∣\operatorname{pgcd}\times\operatorname{ppcm}=|ab| (2 entiers).

3

Bézout & Gauss

au+bv=1au+bv=1 ; Gauss (condition a∧b=1a\wedge b=1).

4

Diophantiennes

ax+by=cax+by=c : d∣cd\mid c, puis (x0+kb′,y0−ka′)(x_0+kb',y_0-ka').

5

Premiers & Fermat

τ(n)=∏(αi+1)\tau(n)=\prod(\alpha_i+1) ; ap−1≡1 [p]a^{p-1}\equiv1\ [p].

6

Congruences

Remplacer par le reste ; périodicité ; critères.

7

Z/nZ\mathbb{Z}/n\mathbb{Z}

Anneau ; inversible   ⟺  a∧n=1\iff a\wedge n=1 ; corps   ⟺  n\iff n premier.

8

Bases

Divisions par bb, restes lus de bas en haut.

3 · Exercices choisis

Une sélection couvrant chaque compétence clé, avec correction guidée.

Bézout · premiers entre eux

Exercice 1

Montrer que pour tout entier nn, les entiers 2n+12n+1 et 3n+13n+1 sont premiers entre eux.

Voir la correction

On cherche une combinaison de Bézout : 3(2n+1)−2(3n+1)=6n+3−6n−2=13(2n+1)-2(3n+1)=6n+3-6n-2=1. On a donc (2n+1)×3+(3n+1)×(−2)=1(2n+1)\times3+(3n+1)\times(-2)=1. D'après Bézout, 2n+12n+1 et 3n+13n+1 sont premiers entre eux, et ce pour tout nn. ∎

Euclide · remontée de Bézout

Exercice 2

Déterminer pgcd⁡(252,105)\operatorname{pgcd}(252,105), puis un couple (u,v)(u,v) tel que 252u+105v=pgcd⁡(252,105)252u+105v=\operatorname{pgcd}(252,105).

Voir la correction

PGCD : Euclide donne 252=2×105+42252=2\times105+42, 105=2×42+21105=2\times42+21, 42=2×21+042=2\times21+0, donc pgcd⁡=21\operatorname{pgcd}=21.

Bézout (remontée) : ligne 2 : 21=105−2×4221=105-2\times42. Ligne 1 : 42=252−2×10542=252-2\times105. On remplace : 21=105−2(252−2×105)=5×105−2×252.21=105-2(252-2\times105)=5\times105-2\times252. Donc 252×(−2)+105×5=21252\times(-2)+105\times5=21, soit (u,v)=(−2,5)\boxed{(u,v)=(-2,5)}. ∎

Congruences · périodicité

Exercice 3

Déterminer le reste de la division de 21002^{100} par 77.

Voir la correction

Périodicité de 2k2^{k} modulo 77 : 21≡22^{1}\equiv2, 22≡42^{2}\equiv4, 23≡8≡1 [7]2^{3}\equiv8\equiv1\ [7]. Période 33. Or 100=3×33+1100=3\times33+1, donc 2100=(23)33×2≡133×2≡2 [7].2^{100}=\big(2^{3}\big)^{33}\times2\equiv1^{33}\times2\equiv2\ [7]. Le reste est 2\boxed{2}. ∎

Équation diophantienne

Exercice 4

Résoudre dans Z2\mathbb{Z}^{2} l'équation (E):24x+18y=30(E):24x+18y=30.

Voir la correction

① pgcd⁡(24,18)=6\operatorname{pgcd}(24,18)=6 et 6∣306\mid30 : il y a des solutions. ② On divise par 66 : 4x+3y=54x+3y=5, avec 4∧3=14\wedge3=1. ③ Solution particulière : 4×(−1)+3×3=54\times(-1)+3\times3=5, donc (x0,y0)=(−1,3)(x_0,y_0)=(-1,3). ④ Avec a′=4, b′=3a'=4,\ b'=3 : (x,y)=(−1+3k, 3−4k),k∈Z.\boxed{(x,y)=(-1+3k,\ 3-4k),\quad k\in\mathbb{Z}}. ⑤ Vérif. : 4(−1+3k)+3(3−4k)=−4+12k+9−12k=54(-1+3k)+3(3-4k)=-4+12k+9-12k=5 ✓ ∎

Fermat · grande puissance

Exercice 5

Déterminer le reste de 520265^{2026} modulo 1313.

Voir la correction

1313 est premier et 13∤513\nmid5, donc par Fermat 512≡1 [13]5^{12}\equiv1\ [13]. Or 2026=12×168+102026=12\times168+10, d'où 52026=(512)168×510≡510 [13].5^{2026}=\big(5^{12}\big)^{168}\times5^{10}\equiv5^{10}\ [13]. Puis 52=25≡−1 [13]5^{2}=25\equiv-1\ [13], donc 510=(52)5≡(−1)5=−1≡12 [13]5^{10}=\big(5^{2}\big)^{5}\equiv(-1)^{5}=-1\equiv12\ [13]. Le reste est 12\boxed{12}. ∎

Z/nZ\mathbb{Z}/n\mathbb{Z} · inverse & équation

Exercice 6

Dans Z/7Z\mathbb{Z}/7\mathbb{Z} : a) justifier que 4ˉ\bar4 est inversible et donner son inverse ; b) résoudre 4ˉ xˉ=5ˉ\bar4\,\bar x=\bar5.

Voir la correction

a) 77 est premier, donc Z/7Z\mathbb{Z}/7\mathbb{Z} est un corps et toute classe non nulle est inversible. Comme 4×2=8≡1 [7]4\times2=8\equiv1\ [7], on a 4ˉ−1=2ˉ\boxed{\bar4^{-1}=\bar2}.

b) On multiplie par 2ˉ\bar2 : 2ˉ×4ˉ xˉ=2ˉ×5ˉ⇒1ˉ xˉ=10‾=3ˉ\bar2\times\bar4\,\bar x=\bar2\times\bar5\Rightarrow\bar1\,\bar x=\overline{10}=\bar3. Donc xˉ=3ˉ\bar x=\bar3. Vérif. : 4ˉ×3ˉ=12‾=5ˉ\bar4\times\bar3=\overline{12}=\bar5 (car 12=7+512=7+5) ✓ ∎

Besoin de plus d'exercices sur un point précis ? Demande à ton professeur en cours.

4 · Astuces & pièges à éviter

Astuce La division euclidienne est unique : c'est ce qui fait marcher tout le reste.
Astuce « Premiers entre eux » se prouve en exhibant une combinaison au+bv=1au+bv=1.
Astuce Couple de Bézout : algorithme d'Euclide, puis remontée ligne par ligne.
Astuce Grandes puissances ⇒ congruences (périodicité) ou Fermat ap−1≡1 [p]a^{p-1}\equiv1\ [p].
Astuce τ(n)=∏(αi+1)\tau(n)=\prod(\alpha_i+1) pour le nombre de diviseurs.
Astuce Z/nZ\mathbb{Z}/n\mathbb{Z} corps   ⟺  n\iff n premier ; aˉ\bar a inversible   ⟺  a∧n=1\iff a\wedge n=1 (par Bézout).
Piège Gauss exige a∧b=1a\wedge b=1 : sans cette condition, a∣bca\mid bc n'entraîne pas a∣ca\mid c.
Piège Diophantienne : tester d∣cd\mid c avant tout, et ne pas intervertir a′a' et b′b'.
Piège Simplifier une congruence par cc n'est licite que si c∧n=1c\wedge n=1.
Piège pgcd⁡×ppcm⁡=∣ab∣\operatorname{pgcd}\times\operatorname{ppcm}=|ab| ne vaut que pour deux entiers, pas trois.
Piège « Premiers entre eux deux à deux » est plus fort que « dans leur ensemble ».

Formulaire à retenir

Divisibilité a∣b  ⟺  ∃k, b=kaa\mid b\iff\exists k,\ b=ka ; a∣b,c⇒a∣(bu+cv)a\mid b,c\Rightarrow a\mid(bu+cv)
Division euclidienne a=bq+ra=bq+r, 0\le r<|b|, couple (q,r)(q,r) unique
Algorithme d'Euclide pgcd⁡(a,b)=pgcd⁡(b,r)\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r) ; dernier reste non nul
Relation PGCD–PPCM pgcd⁡(a,b)×ppcm⁡(a,b)=∣ab∣\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab| (deux entiers)
Décompositions pgcd⁡=∏pimin⁡\operatorname{pgcd}=\prod p_i^{\min}, ppcm⁡=∏pimax⁡\operatorname{ppcm}=\prod p_i^{\max}
Proche en proche pgcd⁡(a1,…,an)=pgcd⁡(pgcd⁡(a1,…,an−1),an)\operatorname{pgcd}(a_1,\dots,a_n)=\operatorname{pgcd}(\operatorname{pgcd}(a_1,\dots,a_{n-1}),a_n)
Bézout a∧b=1  ⟺  ∃u,v, au+bv=1a\wedge b=1\iff\exists u,v,\ au+bv=1
Bézout généralisé pgcd⁡(a1,…,an)=1  ⟺  ∃ui, ∑aiui=1\operatorname{pgcd}(a_1,\dots,a_n)=1\iff\exists u_i,\ \sum a_i u_i=1
Gauss a∣bca\mid bc et a∧b=1⇒a∣ca\wedge b=1\Rightarrow a\mid c
Diophantienne — existence ax+by=cax+by=c a des solutions   ⟺  (a∧b)∣c\iff(a\wedge b)\mid c
Diophantienne — solutions (x0+kb′, y0−ka′)(x_0+kb',\,y_0-ka'), k∈Zk\in\mathbb{Z}, a=da′a=da', b=db′b=db'
Nombre de diviseurs n=∏piαi⇒τ(n)=∏(αi+1)n=\prod p_i^{\alpha_i}\Rightarrow\tau(n)=\prod(\alpha_i+1)
Test de primalité nn premier   ⟺  \iff aucun premier p≤np\le\sqrt n ne divise nn
Petit théorème de Fermat pp premier, p∤a⇒ap−1≡1 [p]p\nmid a\Rightarrow a^{p-1}\equiv1\ [p] ; ap≡a [p]a^{p}\equiv a\ [p]
Congruence a≡b [n]  ⟺  n∣(a−b)a\equiv b\ [n]\iff n\mid(a-b) (même reste)
Compatibilité a+c≡b+da+c\equiv b+d, ac≡bdac\equiv bd, ak≡bk [n]a^{k}\equiv b^{k}\ [n]
Simplification ac≡bc [n]ac\equiv bc\ [n] et c∧n=1⇒a≡b [n]c\wedge n=1\Rightarrow a\equiv b\ [n]
Critères 9,39,3 : somme des chiffres ; 1111 : somme alternée ; 44 : 2 derniers chiffres
Classes Z/nZ={0ˉ,1ˉ,…,n−1‾}\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}, aˉ+bˉ=a+b‾\bar a+\bar b=\overline{a+b}, aˉbˉ=ab‾\bar a\bar b=\overline{ab}
Inversibles aˉ\bar a inversible   ⟺  a∧n=1\iff a\wedge n=1 ; par Bézout aˉ−1=uˉ\bar a^{-1}=\bar u
Corps Z/nZ\mathbb{Z}/n\mathbb{Z} est un corps   ⟺  n\iff n premier
Base bb N=∑aibiN=\sum a_i b^{i}, 0\le a_i<b ; base 10→bb : divisions successives, restes de bas en haut
Fiche de révisionL’essentiel du chapitre en une page — formules, méthodes et astucesVoir la ficheQCM interactifTeste-toi sur ce chapitre — 22 questions auto-corrigéesCommencer le QCM

© Math Excellence · mathexce.com