Exercices corrigés d'arithmétique en Seconde : division euclidienne, restes et nombres premiers

a) On cherche le plus grand multiple de $7$ inférieur ou égal à $253$. Comme $7\times 36=252$ et $7\times 37=259$, c'est $252$. Donc $253=7\times 36+1$ : le quotient vaut $q=36$ et le reste $r=1$. Vérification obligatoire, et elle prend trois secondes : on recalcule $7\times 36+1=253$, et l'on contrôle que $0\leqslant 1<7$. Un reste supérieur ou égal au diviseur signifie qu'on s'est arrêté trop tôt, et c'est l'erreur la plus fréquente quand on pose la division à la main.

b) L'encadrement s'écrit $7\times 36\leqslant 253<7\times 37$, c'est-à-dire $252\leqslant 253<259$. Le quotient est le coefficient du multiple de GAUCHE : c'est la définition même, et c'est ce que montre la figure. On peut aussi l'écrire $36\leqslant\dfrac{253}{7}<37$, ce qui dit que le quotient euclidien est la partie entière du quotient décimal, ici $\dfrac{253}{7}\approx 36{,}14$. Cette lecture est la plus rapide à la calculatrice, mais elle cesse d'être vraie pour un dividende négatif, ce que montre la question suivante.

c) Il faut $-17=5q+r$ avec $0\leqslant r<5$. Le réflexe faux est d'écrire $-17=5\times(-3)-2$ : le reste vaudrait $-2$, ce qui est INTERDIT. On descend donc d'un cran, jusqu'au plus grand multiple de $5$ inférieur ou égal à $-17$, qui est $5\times(-4)=-20$. Alors $-17=-20+3$, c'est-à-dire $-17=5\times(-4)+3$, avec $q=-4$ et $r=3$, et la condition $0\leqslant 3<5$ est respectée. Le quotient n'est donc PAS la troncature de $-3{,}4$, mais son arrondi par défaut. L'erreur coûte toute la question, et elle se propage partout où l'on travaille sur les restes.

d) Supposons $a=bq+r=bq'+r'$ avec les deux restes dans $[0\,;b[$. En soustrayant, $b(q-q')=r'-r$. Le membre de gauche est un multiple de $b$. Le membre de droite est une différence de deux nombres de $[0\,;b[$, donc $|r'-r|<b$ : c'est un multiple de $b$ dont la valeur absolue est strictement inférieure à $b$, il ne peut être que $0$. Donc $r=r'$, puis $b(q-q')=0$ et, comme $b\neq 0$, $q=q'$. Le couple est bien unique. Retenez l'argument, il resservira : « un multiple de $b$ strictement plus petit que $b$ en valeur absolue est nul » est l'outil de démonstration numéro un de tout le chapitre.

a) $2\,025$ se termine par $5$, donc c'est un multiple de $5$ : $2\,025=5\times 405$. Alors $2\,026=5\times 405+1$, reste $1$, et $2\,027=5\times 405+2$, reste $2$. Pour une division par $5$, le reste ne dépend que du chiffre des unités, ce qui rend la lecture immédiate.

b) Écrivons $2\,026=5k+1$ et $2\,027=5k+2$ avec $k=405$. La somme vaut $5k+1+5k+2=5(2k)+3$ : le reste est $3$, puisque $0\leqslant 3<5$. Vérification : $2\,026+2\,027=4\,053$, et $4\,053=5\times 810+3$. La règle générale est que le reste d'une somme est le reste de la somme des restes. Attention : si la somme des restes atteint ou dépasse $n$, il faut encore réduire. Par exemple $3+4=7$ modulo $5$ donne $2$, pas $7$, et oublier cette dernière réduction est l'erreur classique.

c) Avec les mêmes écritures, $2\,026\times 2\,027=(5k+1)(5k+2)=25k^{2}+15k+2=5(5k^{2}+3k)+2$ : le reste est $2$. Le produit lui-même vaut $4\,106\,702$, mais on ne l'a pas calculé, et c'est tout l'intérêt : seuls les restes $1$ et $2$ ont servi, et $1\times 2=2$. Le contrôle à la main est immédiat, le produit se termine par $2$ donc son reste par $5$ vaut bien $2$. Ce raccourci est ce qui permettra, à l'exercice 3, de traiter une puissance de plus de mille chiffres.

d) Pour $9$, le reste se lit sur la somme des chiffres, ce que l'exercice 4 démontrera : $2+0+2+6=10$, puis $1+0=1$, donc $2\,026$ a pour reste $1$ par $9$. En écrivant $2\,026=9m+1$, le carré vaut $(9m+1)^{2}=81m^{2}+18m+1=9(9m^{2}+2m)+1$ : le reste est encore $1$. Contrôle : $2\,026^{2}=4\,104\,676$, dont la somme des chiffres est $4+1+0+4+6+7+6=28$, puis $2+8=10$, puis $1$. Un nombre de sept chiffres traité par deux additions de tête.

a) $7^{1}=7$, $7^{2}=49$, $7^{3}=343$, $7^{4}=2\,401$, $7^{5}=16\,807$. Les unités sont donc $7$, $9$, $3$, $1$, puis $7$ : le cycle a pour longueur $4$. On n'a pas besoin des nombres entiers pour l'obtenir, seulement des unités : $7\times 7$ finit par $9$, $9\times 7$ finit par $3$, $3\times 7$ finit par $1$, $1\times 7$ finit par $7$. C'est exactement la règle du produit de l'exercice 2, appliquée avec $n=10$.

b) Il faut placer $2\,026$ dans le cycle, donc calculer son reste par $4$ : $2\,026=4\times 506+2$, reste $2$. Le reste $2$ correspond à la DEUXIÈME position du cycle, celle de $7^{2}$, donc le chiffre des unités de $7^{2\,026}$ est $9$. Attention au piège de numérotation : un reste de $0$ ne signifie pas la première position mais la QUATRIÈME, celle de $7^{4}$, puisque $7^{4}$, $7^{8}$, $7^{12}$ ont tous un exposant multiple de $4$. Confondre les deux fait perdre toute la question, et c'est l'erreur la plus fréquente du chapitre.

c) Les unités de $3^{n}$ donnent $3$, $9$, $7$, $1$, puis $3$ : cycle de longueur $4$ là encore. Or $100=4\times 25$, reste $0$ : on est donc en quatrième position, celle de $3^{4}=81$, et le chiffre des unités de $3^{100}$ est $1$. C'est exactement le cas où le reste nul renvoie à la fin du cycle et non au début. Contrôle de bon sens : $3^{4}=81$ finit par $1$, donc $3^{100}=(3^{4})^{25}=81^{25}$ finit par $1$, puisqu'un produit de nombres finissant par $1$ finit par $1$.

d) Le chiffre des unités de $a^{n+1}$ ne dépend que du chiffre des unités de $a^{n}$, par la règle du produit : on multiplie ce chiffre par celui de $a$ et l'on garde les unités. La suite des unités est donc entièrement déterminée par son terme précédent. Or il n'y a que DIX valeurs possibles, de $0$ à $9$ : en onze termes au plus, une valeur s'est forcément répétée. Et dès qu'une valeur se répète, tout ce qui suit se répète à l'identique, puisque chaque terme est calculé de la même façon à partir du précédent. Le cycle est donc inévitable, et sa longueur vaut au plus $10$. Cet argument, appelé principe des tiroirs, vaut pour n'importe quel diviseur à la place de $10$.

a) $10=9\times 1+1$, $100=9\times 11+1$ et $1\,000=9\times 111+1$ : le reste vaut $1$ à chaque fois. La raison est visible : $10^{k}-1$ s'écrit avec $k$ chiffres $9$, donc $99\ldots 9$ est un multiple de $9$, et $10^{k}$ vaut ce multiple plus $1$. Toutes les puissances de $10$ ont donc pour reste $1$ par $9$, et c'est le seul fait dont le critère a besoin.

b) Écrivons $N-(a+b+c+d)=1\,000a-a+100b-b+10c-c+d-d=999a+99b+9c$. Chacun des trois termes est un multiple de $9$, puisque $999=9\times 111$, $99=9\times 11$ et $9=9\times 1$. Donc $N-(a+b+c+d)$ est un multiple de $9$, ce qui signifie exactement que $N$ et $a+b+c+d$ ont le même reste par $9$. En particulier, $N$ est divisible par $9$ si et seulement si la somme de ses chiffres l'est. La rédaction attendue est celle-ci : on montre que la DIFFÉRENCE est un multiple, jamais qu'on peut « remplacer » un nombre par un autre. Le même calcul avec $3$ à la place de $9$ donne le critère par $3$, puisque $999$, $99$ et $9$ sont aussi des multiples de $3$.

c) $10=11\times 0+10$, reste $10$ ; $100=11\times 9+1$, reste $1$ ; $1\,000=11\times 90+10$, reste $10$. L'alternance vient de ce que le reste $10$ peut s'écrire $-1$ : en effet $10=11-1$, donc $10$ et $-1$ diffèrent d'un multiple de $11$ et se comportent de la même façon dans tous les calculs de restes. Ainsi $10^{k}$ se comporte comme $(-1)^{k}$, valant $1$ pour $k$ pair et $-1$ pour $k$ impair. Un entier a donc le même reste par $11$ que la somme ALTERNÉE de ses chiffres, en partant du chiffre des unités avec un signe plus.

d) Pour $91\,927$, on part des unités : $7-2+9-1+9=22$. Comme $22=11\times 2$, la somme alternée est divisible par $11$, donc $91\,927$ aussi. Vérification : $91\,927=11\times 8\,357$. Pour $2\,026$ : $6-2+0-2=2$, donc le reste vaut $2$. Vérification : $11\times 184=2\,024$ et $2\,026=2\,024+2$. Le piège est de commencer l'alternance par la gauche : sur un nombre à nombre pair de chiffres, cela donne l'opposé, et le résultat n'est juste que par accident quand la somme est nulle.

a) Pour $360$ : $360=2\times 180=2^{2}\times 90=2^{3}\times 45=2^{3}\times 3^{2}\times 5$. Pour $1\,260$ : $1\,260=2\times 630=2^{2}\times 315=2^{2}\times 3\times 105=2^{2}\times 3^{2}\times 35=2^{2}\times 3^{2}\times 5\times 7$. Vérification en recalculant : $4\times 9\times 5\times 7=1\,260$. On s'arrête quand tous les facteurs sont premiers, et l'on écrit les exposants : une décomposition laissée sous forme $2\times 2\times 2\times 3\times 3\times 5$ n'est pas fausse, mais elle rend la suite illisible.

b) On a nécessairement $a=c$ et $b=d$. C'est exactement ce que dit l'UNICITÉ : un entier n'a qu'une seule décomposition, donc deux écritures du même entier en facteurs premiers ont les mêmes premiers avec les mêmes exposants. Sans ce théorème, l'égalité $2^{a}\times 3^{b}=2^{c}\times 3^{d}$ ne permettrait rien du tout. C'est l'argument qui sert chaque fois qu'on veut prouver qu'un entier n'est pas un carré, un cube, ou qu'une équation n'a pas de solution entière.

c) Un diviseur de $n=p^{\alpha}q^{\beta}$ ne peut contenir que les premiers $p$ et $q$, toujours par unicité, et avec des exposants au plus égaux à ceux de $n$. Il s'écrit donc $p^{i}q^{j}$ avec $0\leqslant i\leqslant\alpha$ et $0\leqslant j\leqslant\beta$. Il y a $\alpha+1$ choix pour $i$, en comptant $0$, et $\beta+1$ choix pour $j$, et deux choix différents donnent deux diviseurs différents, encore par unicité : d'où $(\alpha+1)(\beta+1)$ diviseurs. Le raisonnement s'étend à autant de premiers qu'on veut. Pour $360=2^{3}\times 3^{2}\times 5^{1}$ : $(3+1)(2+1)(1+1)=4\times 3\times 2=24$ diviseurs. Pour $1\,260=2^{2}\times 3^{2}\times 5\times 7$ : $3\times 3\times 2\times 2=36$. Le piège est d'oublier le « plus un », c'est-à-dire d'oublier l'exposant $0$, qui correspond au cas où le premier n'apparaît pas dans le diviseur.

d) On cherche à écrire $12$ comme un produit de facteurs $(\alpha+1)$, puis à répartir les exposants sur les plus petits premiers possibles, les GROS exposants allant aux PETITS premiers. Les découpages de $12$ sont $12$, $6\times 2$, $4\times 3$, $3\times 2\times 2$ et $2\times 2\times 3$. Ils donnent respectivement $2^{11}=2\,048$, $2^{5}\times 3=96$, $2^{3}\times 3^{2}=72$, $2^{2}\times 3\times 5=60$ et, pour le dernier, $2\times 3\times 5^{2}=150$, qu'on améliore en remettant le gros exposant devant : c'est encore $60$. Le plus petit est donc $60$. Vérification par la liste, qui doit contenir exactement douze nombres : $1$, $2$, $3$, $4$, $5$, $6$, $10$, $12$, $15$, $20$, $30$, $60$. Chercher au hasard prendrait un quart d'heure ; la décomposition répond en deux minutes, et c'est toute la différence entre la Troisième et la Seconde sur ce chapitre.

a) On divise par $2$ en notant chaque reste : $44=2\times 22+0$, $22=2\times 11+0$, $11=2\times 5+1$, $5=2\times 2+1$, $2=2\times 1+0$, $1=2\times 0+1$. Les restes obtenus, dans l'ordre d'apparition, sont $0$, $0$, $1$, $1$, $0$, $1$. On les lit DE BAS EN HAUT, c'est-à-dire du dernier au premier : $44$ s'écrit $101100$ en base $2$. L'erreur classique est de les recopier dans l'ordre d'apparition, ce qui donnerait $001101$, c'est-à-dire $13$ : ce n'est pas une petite imprécision, c'est un autre nombre. Le dernier reste obtenu est toujours le chiffre de POIDS FORT, celui de gauche.

b) On repart des puissances de $2$ : $101100$ signifie $1\times 32+0\times 16+1\times 8+1\times 4+0\times 2+0\times 1=32+8+4=44$. C'est bien la valeur de départ. Cette vérification est obligatoire et elle coûte dix secondes : elle attrape à la fois l'erreur de sens de lecture et l'oubli d'un zéro intermédiaire, les deux seules fautes possibles dans cet algorithme.

c) On divise par $5$ : $2\,026=5\times 405+1$, $405=5\times 81+0$, $81=5\times 16+1$, $16=5\times 3+1$, $3=5\times 0+3$. Les restes sont $1$, $0$, $1$, $1$, $3$, et la lecture de bas en haut donne $31101$. Vérification par les puissances de $5$, qui valent $1$, $5$, $25$, $125$, $625$ : $3\times 625+1\times 125+1\times 25+0\times 5+1\times 1=1\,875+125+25+0+1=2\,026$. Ici encore le renversement se voit : lire les restes dans l'ordre d'apparition donnerait $10113$, qui vaut $658$ et non $2\,026$.

d) À chaque étape, le nouveau nombre est le quotient de l'ancien par $b$. Comme $b\geqslant 2$, ce quotient vérifie $q\leqslant\dfrac{n}{2}<n$ dès que $n\geqslant 1$ : la suite des quotients est STRICTEMENT DÉCROISSANTE. Or ce sont des entiers naturels, donc toujours positifs ou nuls. Une suite d'entiers naturels strictement décroissante ne peut pas être infinie : elle atteint $0$ en un nombre fini d'étapes, et c'est là que l'algorithme s'arrête. C'est le même argument que pour l'algorithme d'Euclide, et c'est le modèle de toute preuve de terminaison : on exhibe une quantité entière positive qui décroît strictement.

a) $2\times 3\times 5\times 7=210$, donc $N=211$. Pour le tester, on s'arrête à $\sqrt{211}$, compris entre $14$ et $15$ puisque $14^{2}=196$ et $15^{2}=225$ : il suffit donc d'essayer les premiers jusqu'à $13$, c'est-à-dire $2$, $3$, $5$, $7$, $11$ et $13$. $211$ est impair, sa somme de chiffres vaut $4$ donc il n'est pas multiple de $3$, il ne se termine ni par $0$ ni par $5$, et $211=7\times 30+1$, $211=11\times 19+2$, $211=13\times 16+3$. Aucun ne divise : $211$ est PREMIER. Six divisions ont suffi là où la définition naïve en demanderait $209$.

b) $2\times 3\times 5\times 7\times 11\times 13=30\,030$, donc $M=30\,031$. Il n'est pas premier, puisque $30\,031=59\times 509$. Mais l'essentiel est ailleurs : ni $59$ ni $509$ ne figurent dans la liste $2$, $3$, $5$, $7$, $11$, $13$ dont on est parti. C'est normal, et c'est le cœur de l'argument : $M$ laisse le reste $1$ dans la division par chacun des six premiers de départ, donc aucun d'eux ne peut le diviser, donc ses facteurs premiers sont forcément NOUVEAUX. On retient que $N+1$ n'est pas toujours premier, contrairement à ce que l'exemple a) pourrait laisser croire.

c) Supposons qu'il n'y ait qu'un nombre fini de nombres premiers, disons $p_{1}$, $p_{2}$, ..., $p_{k}$, et posons $N=p_{1}\times p_{2}\times\cdots\times p_{k}+1$. Ce nombre $N$ est supérieur ou égal à $3$, donc il admet au moins un diviseur premier $p$. Or $p$ est l'un des $p_{i}$, par hypothèse, et la division de $N$ par ce $p_{i}$ donne le reste $1$ : $p_{i}$ ne divise donc pas $N$. Contradiction. L'hypothèse de départ est fausse : il existe une infinité de nombres premiers. Attention à la rédaction : on ne dit PAS que $N$ est premier, seulement qu'il possède un facteur premier absent de la liste, et la question b) montre que la nuance n'est pas un détail de style.

d) Si $n=ab$ avec $1<a\leqslant b$, alors en multipliant l'inégalité $a\leqslant b$ par $a$, qui est positif, on obtient $a^{2}\leqslant ab=n$, donc $a\leqslant\sqrt{n}$. Conséquence : si $n$ n'est pas premier, il possède un diviseur strictement compris entre $1$ et $n$, et le PLUS PETIT d'entre eux est inférieur ou égal à $\sqrt{n}$. Il suffit donc de tester les diviseurs jusqu'à $\sqrt{n}$ : si aucun ne convient, $n$ est premier. On peut même se limiter aux diviseurs PREMIERS, car tout diviseur autre que $1$ possède lui-même un facteur premier, qui serait détecté plus tôt. Pour $397$, on teste jusqu'à $19$, puisque $19^{2}=361$ et $20^{2}=400$ : huit premiers à essayer, et aucun ne divise, donc $397$ est premier. Pour $493$, le test tombe sur $17$ : $493=17\times 29$.

a) On effectue la division euclidienne de $1\,754$ par $24$. Comme $24\times 73=1\,752$ et $24\times 74=1\,776$, on a $1\,754=24\times 73+2$. Il y aura donc $73$ cartons PLEINS et $2$ pièces restantes. Le quotient compte les cartons pleins, le reste compte les pièces en trop : c'est le sens concret des deux nombres, et c'est ce qui rend la division euclidienne plus utile ici que la division décimale, qui donnerait $73{,}08$ et ne dirait rien sur les deux pièces.

b) Les $2$ pièces restantes doivent bien partir quelque part, donc il faut un carton de plus : $74$ cartons au total. C'est l'arrondi par EXCÈS du quotient, et il ne faut pas le confondre avec le quotient lui-même : la question « combien de cartons pleins » et la question « combien de cartons commander » n'ont pas la même réponse, et l'écart vaut exactement un dès que le reste n'est pas nul. Pour compléter ce dernier carton, il manque $24-2=22$ pièces.

c) On calcule les trois divisions. Avec $18$ : $18\times 97=1\,746$, donc $1\,754=18\times 97+8$, reste $8$. Avec $24$ : reste $2$, calculé en a). Avec $30$ : $30\times 58=1\,740$, donc $1\,754=30\times 58+14$, reste $14$. Le format $24$ est donc le meilleur des trois, avec seulement $2$ pièces perdues. On note au passage que le reste ne diminue pas quand le carton grossit : $30$ est le plus grand format et c'est lui qui laisse le plus gros reste. Le reste ne dépend pas de la taille du carton mais de la façon dont $1\,754$ se place entre deux multiples.

d) Un format sans reste serait un DIVISEUR de $1\,754$. Décomposons : $1\,754$ est pair, $1\,754=2\times 877$. Reste à savoir si $877$ est premier. On teste jusqu'à $\sqrt{877}$, compris entre $29$ et $30$ puisque $29^{2}=841$ et $30^{2}=900$ : on essaie donc $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$ et $29$. Le nombre est impair, sa somme de chiffres vaut $22$ donc il n'est pas multiple de $3$, il ne finit ni par $0$ ni par $5$, et aucune des autres divisions ne tombe juste. Donc $877$ est premier, et $1\,754=2\times 877$ est sa décomposition. Ses diviseurs sont alors, par la formule de l'exercice 5, au nombre de $2\times 2=4$ : ce sont $1$, $2$, $877$ et $1\,754$. Aucun ne tombe entre $10$ et $40$ : le format demandé n'existe pas, et le reste est inévitable. Voilà une question qu'on ne peut pas traiter en essayant les formats un par un, et que la décomposition règle en trois lignes.