Exercices corrigés — Arithmétique & structures

On cherche $(q,r)$ avec $2024=17q+r$ et $0\le r<17$.

$17\times100=1700$, $17\times119=2023$.

En déduire $r$.

👉 La condition sur $r$ n'est pas un détail de présentation : c'est elle qui rend le couple $(q,r)$ UNIQUE. Sans elle on pourrait écrire $2024=17\times 100+324$, $2024=17\times 118+18$, et une infinité d'autres décompositions.

Le quotient se trouve en divisant, puis en prenant la partie entière par DÉFAUT :

⚠️ Ne jamais arrondir : ici $119{,}06$ arrondi donnerait $119$, ce qui est juste par chance, mais un quotient comme $2035/17\approx 119{,}71$ arrondirait à $120$ et donnerait un reste négatif ($2035-17\times 120=-5$). C'est toujours la partie entière inférieure.

Calculons $17\times 119$ proprement :

👉 Passer par $17\times 120$ est plus sûr que la multiplication posée — c'est un réflexe qui évite beaucoup d'erreurs de calcul.

Les DEUX contrôles à faire systématiquement :

⚠️ Le second est celui qu'on oublie, et c'est pourtant lui qui distingue une vraie division euclidienne d'une simple égalité. Un reste de $18$ satisferait la première ligne et pas la seconde.

👉 Un reste de $1$ n'est pas anodin : il dit que $2024$ et $17$ sont premiers entre eux.

En effet, tout diviseur commun à $2024$ et $17$ divise aussi $r=2024-17\times 119=1$, donc vaut $1$.

⚠️ Ici c'était prévisible : $17$ est premier, donc son seul diviseur autre que $1$ est $17$ lui-même — et $17\nmid 2024$ précisément parce que le reste n'est pas nul.

👉 Traduction en congruences (B3, B4) :

ce qui rend immédiat le calcul de $2024^k\bmod 17$ pour n'importe quel $k$ : c'est toujours $1$.

ℹ️ Le reste est ce qui compte en arithmétique modulaire — le quotient, lui, est presque toujours jeté. Toute la suite du chapitre travaille sur les restes.

👉 La condition $0\leq r<\lvert b\rvert$ vaut aussi pour $a<0$, et c'est là qu'on se trompe (voir E1).

👉 Il n'y a qu'un seul couple valide, et l'unicité se démontre : si $bq+r=bq'+r'$ avec deux restes dans $[0,b[$, alors $b(q-q')=r'-r$, donc $b$ divise $r'-r$. Or $\lvert r'-r\rvert<b$, ce qui force $r'-r=0$, puis $q=q'$.

👉 Une conséquence pratique immédiate : le reste de la division par $b$ classe les entiers en $b$ familles — les classes de congruence modulo $b$. Pour $b=17$, il y en a exactement $17$, indexées par $r\in\{0,1,\dots,16\}$.

ℹ️ C'est cette partition qui donne naissance à $\mathbb{Z}/17\mathbb{Z}$ (D4), et le fait que $17$ soit premier en fera un corps.

$\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$ où $r$ est le reste de $a$ par $b$.

Itérer : $252=198\cdot1+54$, puis $198$ par $54$…

S'arrêter au reste nul ; le PGCD est le dernier reste non nul.

👉 L'idée tient en une seule égalité :

Pourquoi c'est vrai. Si $a=bq+r$, alors tout diviseur commun à $a$ et $b$ divise $r=a-bq$ ; et réciproquement tout diviseur commun à $b$ et $r$ divise $a=bq+r$. Les deux couples ont donc exactement les mêmes diviseurs communs, donc le même plus grand.

👉 Et l'algorithme TERMINE, ce qui n'est pas une évidence : les restes forment une suite d'entiers positifs strictement décroissante

donc elle atteint $0$ en un nombre fini d'étapes. Le pgcd est alors le dernier reste non nul.

ℹ️ La terminaison est rapide : le nombre d'étapes est majoré par environ $5$ fois le nombre de chiffres du plus petit des deux — un résultat dû à Lamé, et le pire cas est atteint par les nombres de Fibonacci.

👉 Le pgcd est le DERNIER RESTE NON NUL, c'est-à-dire $18$ — surtout pas $0$, qui n'est que le signal d'arrêt.

Comment lire chaque ligne. À chaque étape, le dividende et le diviseur de la ligne suivante sont le diviseur et le reste de la ligne courante : $(252,198)\to(198,54)\to(54,36)\to(36,18)$.

⚠️ Erreur classique : recopier le dividende au lieu du diviseur. Le contrôle est que le premier nombre de chaque ligne est le second de la ligne précédente.

1. Divisibilité. $18$ doit diviser les deux nombres de départ :

2. Les quotients doivent être premiers entre eux. $14=2\times 7$ et $11$ premier : aucun facteur commun ✓

👉 C'est le contrôle le plus fort, et il est souvent oublié : si les quotients avaient un facteur commun, on n'aurait pas pris le plus grand diviseur. Par exemple $\operatorname{pgcd}=9$ donnerait $252/9=28$ et $198/9=22$, tous deux pairs — la preuve qu'on peut faire mieux.

3. Par factorisation (méthode de A4, indépendante d'Euclide) :

👉 Deux méthodes indépendantes, même résultat : c'est le meilleur contrôle qui soit.

👉 Sur $252$ et $198$, la factorisation est plus rapide. Sur de grands nombres, elle est IMPOSSIBLE.

👉 Et c'est exactement là-dessus que repose RSA (D5) : on sait calculer un pgcd sur des nombres de $600$ chiffres en une fraction de seconde, et personne ne sait les factoriser.

Exemple pour fixer l'ordre de grandeur : $\operatorname{pgcd}(252,198)$ demande 4 divisions. Le pire cas pour des nombres de cette taille serait atteint par deux Fibonacci consécutifs, $233$ et $144$, qui demandent $11$ étapes.

ℹ️ Euclide donne plus que le pgcd : en remontant les égalités, il fournit les coefficients de Bézout $u,v$ tels que $252u+198v=18$ (B1). Aucune méthode par factorisation ne les donne, et ce sont eux qui permettent d'inverser modulo $n$ (C1) — donc de faire fonctionner RSA.

$\operatorname{pgcd}\times\operatorname{ppcm}=|ab|$.

$\operatorname{ppcm}=\dfrac{252\times198}{18}$.

Simplifier.

👉 Pourquoi c'est vrai, en une ligne, avec les factorisations. Pour chaque premier $p$ :

où $\alpha,\beta$ sont les exposants de $p$ dans $a$ et $b$. En effet, $\min$ et $\max$ ne font qu'échanger les deux nombres : leur somme est inchangée.

⚠️ La formule ne s'étend PAS à trois nombres. Sur $a=b=c=2$ :

👉 C'est la première chose à vérifier avant de généraliser une formule d'arithmétique — ici, $\min+\max=\alpha+\beta$ n'a d'analogue à trois termes que par inclusion-exclusion.

On sait que $\operatorname{pgcd}(252,198)=18$ (A2). Donc

👉 Le bon geste : SIMPLIFIER AVANT de multiplier. Calculer $252\times 198=49\,896$ puis diviser est possible, mais c'est se donner du travail et des occasions d'erreur.

👉 On aurait pu simplifier de l'autre côté : $198/18=11$, puis $252\times 11=2772$. Les deux marchent — prendre celle qui tombe juste.

1. Divisibilité par les deux.

👉 Remarquer que les quotients sont exactement les deux nombres croisés $252/18=14$ et $198/18=11$ : c'est une conséquence directe de la formule, et un bon moyen de vérifier sans calculer.

2. La relation fondamentale, vérifiée dans les deux sens :

3. Par factorisation (A4) :

👉 Trois voies, trois fois $2772$.

👉 Le ppcm est ce qui répond aux questions de SYNCHRONISATION, et c'est là qu'il faut le reconnaître :

Exemple concret. Deux feux clignotent, l'un toutes les $252$ secondes, l'autre toutes les $198$. Ils viennent de clignoter ensemble : ils recommenceront dans $2772$ secondes, soit 46 minutes et 12 secondes.

⚠️ Erreur fréquente : répondre $252\times 198$. C'est bien un instant de coïncidence, mais pas le premier — il est $18$ fois trop tard.

👉 Le pgcd, lui, répond aux questions de DÉCOUPAGE : « quel est le plus grand carreau qui pave exactement un rectangle $252\times 198$ ? » — un carré de côté $18$, et il en faut $14\times 11=154$.

ℹ️ Les deux notions sont duales : le pgcd est le plus grand qui divise, le ppcm le plus petit qui est divisé. Leur produit rend le produit des nombres, ce qui est exactement le §1.

Factoriser chaque nombre.

PGCD : $\min$ des exposants ; PPCM : $\max$ des exposants.

$360=2^3\cdot3^2\cdot5$, $84=2^2\cdot3\cdot7$.

👉 Méthode : diviser par les premiers dans l'ordre, $2$, puis $3$, puis $5$, $7$… en épuisant chacun avant de passer au suivant.

Pour $360$ :

Pour $84$ :

Contrôles : $8\times 9\times 5=360$ ✓ et $4\times 3\times 7=84$ ✓

ℹ️ Cette écriture est UNIQUE (théorème fondamental de l'arithmétique), à l'ordre des facteurs près. C'est ce qui rend légitimes les formules du bloc suivant.

👉 Le bon geste : aligner les deux factorisations sur TOUS les premiers en jeu, en mettant l'exposant $0$ là où le facteur manque. C'est ce qui évite les oublis.

⚠️ Les deux zéros sont le piège de l'exercice. $5$ n'apparaît pas dans $84$ et $7$ pas dans $360$ : leur exposant y vaut $0$, donc leur minimum vaut $0$ et ils sont absents du pgcd — mais leur maximum ne l'est pas, et ils sont présents dans le ppcm.

PGCD — les minimums :

PPCM — les maximums :

Les trois contrôles :

👉 Contrôle par Euclide (A2), méthode indépendante : $360=84\times 4+24$ ; $84=24\times 3+12$ ; $24=12\times 2+0$ → pgcd $=12$ ✓ en trois étapes.

👉 Aucune ne domine l'autre, et c'est pourquoi les deux figurent au programme. Euclide est l'outil de calcul ; la factorisation est l'outil de structure.

👉 La factorisation répond à des questions qu'Euclide ne peut pas atteindre :

• combien $360$ a-t-il de diviseurs ? — $\ (3+1)(2+1)(1+1)=24$ (A5) ;
• $360$ est-il un carré parfait ? — non, l'exposant de $2$ et celui de $5$ sont impairs ;
• quel est le plus petit $k$ tel que $360k$ soit un carré ? — $k=2\times 5=10$, pour rendre tous les exposants pairs.

ℹ️ En pratique, on factorise quand les nombres sont petits ou déjà factorisés, et on emploie Euclide dans tous les autres cas — c'est-à-dire presque toujours en informatique.

Nombre de diviseurs : $\prod(\alpha_i+1)$.

Somme : $\prod\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}=\prod(1+p_i+\dots+p_i^{\alpha_i})$.

$1+2+4+8=15$, $1+3+9=13$, $1+5=6$.

Si $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ est la factorisation de $n$ :

👉 D'où vient le $(\alpha_i+1)$ : un diviseur de $n$ s'écrit $p_1^{\beta_1}\cdots p_k^{\beta_k}$ avec $0\leq\beta_i\leq\alpha_i$. Il y a donc $\alpha_i+1$ choix pour chaque exposant — de $0$ à $\alpha_i$ inclus — et les choix sont indépendants.

⚠️ Le $+1$ compte l'exposant ZÉRO, c'est-à-dire le cas où le premier est absent du diviseur. L'oublier est l'erreur la plus fréquente.

👉 Et la somme des diviseurs vient du DÉVELOPPEMENT d'un produit :

En développant, on obtient exactement une fois chaque diviseur. Chaque parenthèse est une somme géométrique, d'où la formule fermée.

👉 Vérification par énumération, et il vaut la peine de la faire une fois :

On en compte bien 24 ✓

👉 Remarquer l'appariement : les diviseurs vont par paires de produit $360$ — $(1,360)$, $(2,180)$, $(3,120)$… C'est pourquoi $d(n)$ est impair si et seulement si $n$ est un carré parfait, le seul cas où un diviseur est apparié avec lui-même.

Calculons :

👉 Contrôle par la formule géométrique, qui doit donner les mêmes parenthèses :

👉 Second contrôle, très parlant : la somme des diviseurs stricts (tous sauf $n$) vaut

$360$ est donc un nombre abondant — ses diviseurs stricts somment à plus que lui-même.

👉 Les nombres se classent selon $\sigma(n)$ comparé à $2n$ :

👉 $360$ est très abondant, et ce n'est pas un hasard : c'est un nombre hautement composé — aucun entier inférieur n'a autant de diviseurs. C'est pour cette raison qu'il compte $360$ degrés dans un cercle et $60$ minutes dans une heure : on peut diviser en $2,3,4,5,6,8,9,10,12\dots$ parts égales.

⚠️ $d$ et $\sigma$ sont MULTIPLICATIVES mais pas complètement : $d(mn)=d(m)d(n)$ seulement si $\operatorname{pgcd}(m,n)=1$.

👉 C'est la même condition que pour l'indicatrice d'Euler (C3), et pour la même raison : la factorisation de $mn$ ne « colle » les exposants que si les deux nombres n'ont aucun premier en commun.

ℹ️ Les nombres parfaits pairs sont entièrement connus — ils sont de la forme $2^{k-1}(2^k-1)$ avec $2^k-1$ premier (nombres de Mersenne). On n'en connaît que $52$. Et l'on ignore toujours s'il existe un nombre parfait IMPAIR : c'est l'un des plus vieux problèmes ouverts des mathématiques.

Tester la divisibilité par les premiers $\le\sqrt n$.

$\sqrt{211}\approx14{,}5$ : tester $2,3,5,7,11,13$.

Pour $221$, chercher un diviseur évident.

👉 Pourquoi la racine suffit, et c'est l'argument qui rend le test praticable. Si $n=ab$ avec $1<a\leq b<n$, alors

Autrement dit : si $n$ a un diviseur, il en a forcément un qui ne dépasse pas $\sqrt n$. Tester au-delà est inutile — on retrouverait les mêmes couples dans l'autre sens.

👉 Et il suffit de tester les PREMIERS, pas tous les entiers : si $n$ est divisible par $6$, il l'est déjà par $2$.

⚠️ Le gain est énorme : pour $n=211$, on teste $6$ nombres au lieu de $209$.

👉 Les trois premiers tests se font de tête, par les critères de divisibilité (B4) : parité, somme des chiffres, chiffre des unités. Seuls $7$, $11$ et $13$ demandent une division.

⚠️ Ne pas s'arrêter trop tôt. $\sqrt{211}\approx 14{,}53$ : il faut aller jusqu'à $13$ inclus. S'arrêter à $11$ laisserait un cas non testé.

Même racine, mêmes candidats : $\sqrt{221}\approx 14{,}87$, donc $2,3,5,7,11,13$.

⚠️⚠️ $221$ est le piège classique, et pour trois raisons qui se cumulent :

• il paraît premier — impair, pas divisible par $3$ ni $5$ ;
• son plus petit facteur est $13$, le dernier candidat à tester ;
• ses deux facteurs $13$ et $17$ sont proches de $\sqrt{221}\approx 14{,}87$.

👉 C'est exactement la structure d'une clé RSA (D5) : le produit de deux premiers voisins de $\sqrt n$ est le cas le plus difficile à factoriser. En miniature, $221$ illustre pourquoi RSA tient.

👉 Pour lister tous les premiers jusqu'à $N$, le crible d'Ératosthène est bien plus efficace que de tester un par un : on écrit les entiers de $2$ à $N$, on garde $2$ et on barre ses multiples, on garde le premier non barré ($3$) et on barre ses multiples, etc.

⚠️ Il n'est même pas nécessaire de barrer au-delà de $\sqrt N$ — pour la même raison qu'au §1.

👉 Les faits à connaître :

La démonstration d'Euclide tient en trois lignes : si $p_1,\dots,p_k$ étaient tous les premiers, alors $N=p_1\cdots p_k+1$ ne serait divisible par aucun d'eux (reste $1$ à chaque fois), donc son plus petit facteur premier serait un premier nouveau.

ℹ️ Tester la primalité est BEAUCOUP plus facile que factoriser : on sait dire en une fraction de seconde qu'un nombre de $600$ chiffres est premier (test de Miller-Rabin, ou AKS en temps polynomial depuis 2002), et personne ne sait factoriser le produit de deux tels premiers. Toute la sécurité de RSA tient dans cet écart (D5).

Reprendre les divisions de l'algorithme d'Euclide (A2).

Remonter en exprimant $18$ à partir des restes successifs.

$18=54-36$, puis $36=198-54\cdot3$, puis $54=252-198$.

👉 L'algorithme d'Euclide ne donne pas seulement le pgcd : il donne AUSSI $u$ et $v$, en remontant les divisions. C'est ce qui le rend irremplaçable — aucune méthode par factorisation ne les fournit.

⚠️ Le couple $(u,v)$ n'est PAS unique : si $au+bv=d$, alors pour tout $k$

👉 Il y a donc une infinité de couples de Bézout, et l'on cherche seulement à en exhiber un.

On reprend les divisions de A2, en isolant chaque reste — c'est le geste qui prépare la remontée :

👉 On ne garde que les lignes à reste non nul, et on part de la dernière, celle qui exhibe le pgcd.

Départ — la dernière ligne :

Substituons $36=198-54\times 3$ :

⚠️ Ne pas développer $54$ tout de suite : on le garde groupé, car c'est lui qu'on va remplacer à l'étape suivante. C'est le point où l'on se trompe le plus.

Substituons $54=252-198$ :

Contrôle, à ne jamais sauter :

👉 Un coefficient est toujours négatif quand $a$ et $b$ sont positifs — sinon $au+bv$ dépasserait largement le pgcd. C'est un contrôle de plausibilité immédiat.

👉 Trois usages, et ce sont eux qui portent tout le reste du chapitre :

👉 Le corollaire le plus utilisé — le théorème de Bézout proprement dit :

Le sens $\Leftarrow$ est immédiat : tout diviseur commun à $a$ et $b$ divise $au+bv=1$, donc vaut $1$.

👉 C'est de ce corollaire que découle le théorème de Gauss (B2), et de proche en proche toute l'arithmétique modulaire — jusqu'à RSA (D5), dont la clé privée est un coefficient de Bézout.

ℹ️ Ici $\operatorname{pgcd}=18\neq 1$ : $252$ et $198$ ne sont donc pas premiers entre eux, et $252$ n'est pas inversible modulo $198$.

$15\mid 7n$ et on connaît $\operatorname{pgcd}(7,15)$.

Gauss : si $a\mid bc$ et $\operatorname{pgcd}(a,b)=1$, alors $a\mid c$.

Ici $a=15$, $b=7$, $c=n$.

⚠️⚠️ L'hypothèse « premiers entre eux » n'est pas décorative — sans elle, l'énoncé est faux :

👉 Ici $\operatorname{pgcd}(6,4)=2\neq 1$ : le facteur $2$ de $6$ se loge dans $4$ et le facteur $3$ dans $3$. Le diviseur se « répartit » entre les deux, au lieu de tomber entier dans l'un.

👉 La démonstration, par Bézout (B1). Comme $\operatorname{pgcd}(a,b)=1$, il existe $u,v$ avec $au+bv=1$. Multiplions par $c$ :

$a$ divise $acu$ (visiblement) et $a$ divise $bcv$ (puisque $a\mid bc$). Donc $a$ divise leur somme, c'est-à-dire $c$. $\blacksquare$

Étape 1 — vérifier l'hypothèse. $15=3\times 5$ et $7$ est premier, donc

👉 C'est la seule chose à vérifier, et c'est elle qui autorise Gauss.

Étape 2 — appliquer. $15\mid 7\times n$ avec $15$ premier avec $7$, donc

Contrôle sur trois valeurs :