Terminale maths expertes

Arithmétique : divisibilité et congruences — 20 exercices

Cette série développe la divisibilité dans les entiers et le calcul modulo un entier strictement positif. Chaque exercice comporte deux ou trois questions, suivies d'une solution explicitant les étapes et les conditions d'application. Les restes d'une division euclidienne sont toujours positifs ou nuls, même lorsque le dividende est négatif. Une congruence modulo m est une égalité de restes, et non une égalité d'entiers. Les exercices portant la mention « Approfondissement » prolongent les techniques fondamentales.

L'essentiel à retenir

Pour tout entier a et tout entier $b > 0$ , il existe un unique couple d'entiers (q,r) tel que $a=bq+r$ et $0\leq r<b$ .
Dire que d divise a signifie qu'il existe un entier k tel que $a=dk$ . Les diviseurs positifs d'un entier non nul forment un ensemble fini.
La congruence $a\equiv b\pmod m$ signifie que m divise a-b. Elle est compatible avec l'addition, la soustraction, la multiplication et les puissances entières positives.
On ne peut simplifier une congruence par un facteur qu'en contrôlant son PGCD avec le module. Si $d=\mathrm{PGCD}(c,m)$ , alors $cx\equiv cy\pmod m$ équivaut à $x\equiv y\pmod{m/d}$ .
L'équation $ax\equiv b\pmod m$ possède des solutions exactement lorsque $\mathrm{PGCD}(a,m)$ divise b. Dans ce cas, elle possède ce nombre de classes de solutions modulo m.
Pour établir une divisibilité par un produit de modules deux à deux premiers entre eux, on peut établir séparément les divisibilités correspondantes. Cette règle n'est pas valable sans la condition de coprimalité.
Un tableau de résidus doit être exhaustif pour constituer une preuve d'impossibilité. Pour les puissances, une période démontrée permet de réduire les exposants.
Le théorème chinois des restes donne une unique classe modulo le produit lorsque les modules sont deux à deux premiers entre eux. Avec des modules non premiers entre eux, une condition de compatibilité est nécessaire.

Exercice 1 — Divisions euclidiennes de nombres négatifs

Effectuer les divisions euclidiennes de -125 et de -43 par 7.
En déduire le reste de -125-3×(-43) dans la division par 7.
Expliquer pourquoi l'écriture -43=7×(-6)-1 n'est pas une division euclidienne.

Corrigé détaillé

On cherche un reste compris entre 0 et 6. Puisque $7\times(-18)=-126$ , on obtient $-125=7\times(-18)+1$ : le quotient est -18 et le reste 1. De même, $7\times(-7)=-49$ , donc $-43=7\times(-7)+6$ : le quotient est -7 et le reste 6. Le quotient n'est donc pas obtenu en tronquant simplement le quotient décimal vers zéro.
En calculant avec les restes, $-125-3(-43)\equiv1-3\times6=-17\equiv4\pmod7$ . Vérification directe : le nombre vaut $-125+129=4$ , dont le reste est bien 4.
L'égalité proposée est numériquement exacte, mais son reste -1 est négatif. Elle ne satisfait pas la condition $0\leq r<7$ . En diminuant le quotient de 1, on ajoute 7 au reste : $7(-6)-1=7(-7)+6$ . C'est cette seconde écriture qui est euclidienne.

Exercice 2 — Retrouver le diviseur à partir d'un reste

On divise 83 par un entier positif d et l'on obtient le reste 8.

Déterminer tous les diviseurs d possibles et les quotients correspondants.
Déterminer les valeurs de $d$ si l'on sait en outre que le quotient est strictement supérieur à 2.
Expliquer pourquoi $d=5$ doit être écarté bien qu'il divise 83-8.

Corrigé détaillé

L'égalité de division est $83=dq+8$ , avec $d>8$ . Elle entraîne $dq=75$ , donc d est un diviseur positif de 75. Comme $75=3\times5^2$ , ses diviseurs sont 1, 3, 5, 15, 25 et 75. La contrainte $d>8$ conserve seulement 15, 25 et 75. Les quotients associés sont respectivement $75/15=5$ , $75/25=3$ et $75/75=1$ . Les trois divisions sont donc $83=15\times5+8$ , $83=25\times3+8$ et $83=75\times1+8$ .
La condition $q>2$ conserve les deux premières possibilités : $d=15$ ou $d=25$ . Elle ne suffit pas à obtenir une réponse unique.
Pour $d=5$ , l'égalité $83=5\times15+8$ est vraie, mais le prétendu reste 8 est supérieur au diviseur. La division euclidienne réelle est $83=5\times16+3$ . La divisibilité de 75 par d est nécessaire, mais doit être accompagnée de $d>8$ .

Exercice 3 — Un produit de trois entiers consécutifs

Démontrer que $n(n+1)(n+2)$ est divisible par 6 pour tout entier n, y compris négatif.
Cette expression est-elle toujours divisible par 12 ?
Déterminer le reste de $1001\times1002\times1003$ modulo 12 sans calculer le produit complet.

Corrigé détaillé

Parmi deux entiers consécutifs, l'un est pair ; le produit contient donc un facteur divisible par 2. Parmi trois entiers consécutifs, l'un est divisible par 3 : cela se vérifie en considérant les trois restes possibles de n modulo 3. Le produit est divisible par 2 et par 3. Ces deux nombres étant premiers entre eux, il est divisible par 6. L'argument concerne les restes et reste donc valable pour n négatif ; si un facteur est nul, la conclusion est également vraie.
Non : pour $n=1$ , le produit vaut $1\times2\times3=6$ , non divisible par 12. Avoir un facteur pair ne garantit pas la présence de deux facteurs 2.
Modulo 12, les trois facteurs valent respectivement 5, 6 et 7. Leur produit est congru à $5\times6\times7=210$ , puis à $210-17\times12=6$ . Le reste demandé est donc 6. Ce cas illustre précisément la différence entre divisibilité par 6 et divisibilité par 12.

Exercice 4 — Tableau d'un cycle de puissances

Construire le tableau des restes de $3^k$ modulo 7 pour $k$ allant de $0$ à $6$ , puis justifier la période 6.
Calculer le reste de $3^{2025}$ modulo 7.
Déterminer le reste de $1+3+3^2+\cdots+3^{2025}$ modulo 7.

Corrigé détaillé

En multipliant chaque reste par 3, on obtient le tableau :

$k$	0	1	2	3	4	5	6
Reste de $3^k$ modulo $7$	1	3	2	6	4	5	1

En effet, 9 donne 2, 6 donne 6, 18 donne 4, 12 donne 5 et 15 donne 1. Puisque

3^6\equiv1\pmod7

, la suite recommence après six termes. Aucun des exposants 1 à 5 ne donne le reste 1 : la plus petite période positive est donc 6.

On écrit $2025=6\times337+3$ . Ainsi $3^{2025}\equiv3^3\equiv6\pmod7$ .
Les exposants de 0 à 2025 donnent 2026 termes. Or $2026=6\times337+4$ . Chaque bloc complet de six puissances a pour somme des restes $1+3+2+6+4+5=21$ , divisible par 7. Il reste quatre termes, de restes 1, 3, 2 et 6, dont la somme vaut 12. Le reste total est donc 5. On distingue bien ici le nombre de termes, 2026, du dernier exposant, 2025.

Exercice 5 — Corriger une simplification illicite

Un élève transforme

6x\equiv9\pmod{15}

2x\equiv3\pmod{15}

en divisant par 3.

Expliquer l'erreur et donner la transformation correcte.
Résoudre l'équation initiale modulo 15.
Donner une solution perdue par la méthode de l'élève.

Corrigé détaillé

L'équation initiale signifie que $15\mid(6x-9)$ , c'est-à-dire que $15\mid3(2x-3)$ . Cette condition équivaut à $5\mid(2x-3)$ , et non à $15\mid(2x-3)$ . En divisant le facteur commun 3, il faut aussi diviser le module par 3. La transformation correcte est donc $2x\equiv3\pmod5$ .
L'inverse de 2 modulo 5 est 3, car $2\times3=6\equiv1\pmod5$ . On obtient $x\equiv9\equiv4\pmod5$ . Les classes correspondantes modulo 15 sont $x\equiv4,9,14\pmod{15}$ . Elles sont toutes solutions : les valeurs de $6x-9$ sont respectivement 15, 45 et 75, toutes divisibles par 15.
Pour $x=4$ , l'équation initiale donne $24\equiv9\pmod{15}$ , ce qui est vrai. Mais la congruence de l'élève demanderait $8\equiv3\pmod{15}$ , ce qui est faux. La mauvaise simplification impose donc une condition trop forte et élimine des solutions.

Exercice 6 — Une équation à coefficient non inversible

Résoudre $14x\equiv8\pmod{30}$ en expliquant pourquoi 14 n'est pas inversible modulo 30.
Donner toutes les solutions comprises entre -20 et 40.
Comparer avec l'équation $14x\equiv9\pmod{30}$ .

Corrigé détaillé

On a $\mathrm{PGCD}(14,30)=2$ , donc 14 n'a pas d'inverse modulo 30. Comme 2 divise 8, on peut diviser la congruence et le module par 2 : $7x\equiv4\pmod{15}$ . L'inverse de 7 modulo 15 est 13, puisque $7\times13=91=6\times15+1$ . Il vient $x\equiv52\equiv7\pmod{15}$ . Toutes les solutions entières sont donc $x=7+15k$ , où k est entier ; modulo 30, cela donne les deux classes 7 et 22.
L'encadrement $-20\leq7+15k\leq40$ équivaut à $-27\leq15k\leq33$ , donc $k=-1$ ,0,1,2. Les solutions demandées sont -8, 7, 22 et 37.
Pour la seconde équation, 2 ne divise pas 9 : aucune solution n'existe. Plus directement, $14x-9$ est impair, alors que tout multiple de 30 est pair. La première opération n'est donc jamais de chercher un inverse inexistant, mais de vérifier la compatibilité avec le PGCD.

Exercice 7 — Une impossibilité par les carrés

Établir la liste des restes possibles d'un carré modulo 4.
Démontrer que l'équation $x^2+y^2=2023$ n'a pas de solution entière.
Expliquer pourquoi le même raisonnement ne permet pas de conclure à l'impossibilité pour 2025, puis donner une solution.

Corrigé détaillé

Un entier pair s'écrit 2k et son carré vaut $4k^2$ , de reste 0 modulo 4. Un entier impair s'écrit $2k+1$ et son carré vaut $4k(k+1)+1$ , de reste 1. Les seuls restes possibles sont donc 0 et 1.
La somme de deux tels restes appartient à {0,1,2}. Or $2023=4\times505+3$ , donc le membre de droite a pour reste 3. Aucun choix des parités de x et y ne permet cette égalité. Il n'existe donc aucune solution dans les entiers, positifs ou négatifs.
On a $2025\equiv1\pmod4$ , reste compatible avec une somme 0+1. Cette compatibilité ne prouve pas à elle seule l'existence d'une solution, mais elle empêche l'obstruction précédente de fonctionner. Ici, on peut exhiber $2025=45^2+0^2$ , donc (45,0) est solution. On dispose même d'une solution à deux coordonnées non nulles : $27^2+36^2=729+1296=2025$ . Une obstruction modulaire doit être distinguée d'une méthode de construction.

Exercice 8 — Trois conditions et un théorème chinois

Résoudre le système $x\equiv3\pmod7$ , $x\equiv4\pmod9$ , $x\equiv2\pmod5$ .
Donner la plus petite solution positive et toutes les solutions comprises entre 100 et 1000.
Justifier l'unicité modulo le produit des modules.

Corrigé détaillé

Écrivons $x=3+7a$ . La condition modulo 9 donne $7a\equiv1\pmod9$ . Comme $7\times4=28\equiv1\pmod9$ , on obtient $a\equiv4\pmod9$ , donc $a=4+9b$ . Ainsi $x=31+63b$ . Modulo 5, cette expression donne $1+3b\equiv2$ , soit $3b\equiv1\pmod5$ . L'inverse de 3 est 2, donc $b\equiv2\pmod5$ et $b=2+5k$ . Finalement, $x=157+315k$ .
La plus petite solution positive est 157, car 157-315 est négatif. Dans [100,1000], les paramètres possibles sont $k=0$ ,1,2 : les solutions sont 157, 472 et 787. Pour $k=3$ , on obtient 1102, hors intervalle.
Les modules 7, 9 et 5 sont deux à deux premiers entre eux. Si x et y satisfont le système, x-y est divisible par chacun d'eux, donc par leur produit 315. Réciproquement, ajouter 315 à une solution conserve toutes les conditions. On a donc exactement une classe de solutions modulo 315.

Exercice 9 — Tracer une exponentiation rapide

Calculer successivement les restes de $7^2$ , $7^4$ , $7^8$ , $7^{16}$ , $7^{32}$ , $7^{64}$ et $7^{128}$ modulo 13.
Utiliser la décomposition binaire de 222 pour déterminer $7^{222}$ modulo 13.
Préciser l'intérêt algorithmique de la méthode.

Corrigé détaillé

Les carrés successifs donnent : $7^2\equiv49\equiv10$ ; $7^4\equiv10^2\equiv9$ ; $7^8\equiv9^2\equiv3$ ; $7^{16}\equiv3^2\equiv9$ ; $7^{32}\equiv9^2\equiv3$ ; $7^{64}\equiv3^2\equiv9$ ; $7^{128}\equiv9^2\equiv3$ , toujours modulo 13. Chaque opération porte donc sur de petits restes.
On écrit $222=128+64+16+8+4+2$ . Le reste recherché est celui de $3\times9\times9\times3\times9\times10$ . En réduisant après chaque produit : $3\times9\equiv1$ , puis $1\times9\equiv9$ , puis $9\times3\equiv1$ , puis $1\times9\equiv9$ , et enfin $9\times10=90\equiv12$ . Ainsi $7^{222}\equiv12\pmod{13}$ .
Une méthode naïve multiplie 221 fois par 7. Ici, sept élévations au carré suffisent à produire les puissances utiles, puis cinq multiplications assemblent les six facteurs. En général, le nombre d'opérations croît comme le nombre de chiffres binaires de l'exposant.

Exercice 10 — Une récurrence et ses résidus

Soit

u_0=2

u_{n+1}=3u_n+4

Démontrer par récurrence que $u_n=4\times3^n-2$ .
Prouver que tous les termes ont pour reste 2 modulo 8.
Déterminer les indices n pour lesquels $u_n$ est divisible par 5.

Corrigé détaillé

Pour $n=0$ , la formule donne $4\times1-2=2=u_0$ . Si elle est vraie au rang n, alors $u_{n+1}=3(4\times3^n-2)+4=12\times3^n-2=4\times3^{n+1}-2$ . La propriété est donc vraie pour tout entier n positif ou nul.
Le nombre $3^n$ est impair ; il s'écrit $2t+1$ . Ainsi $u_n=4(2t+1)-2=8t+2$ , d'où $u_n\equiv2\pmod8$ . On peut aussi raisonner directement par récurrence : le reste 2 devient $3\times2+4=10$ , encore de reste 2.
Modulo 5, les puissances de 3 suivent le cycle 1,3,4,2 de période 4. La formule explicite donne donc, pour n de restes 0,1,2,3 modulo 4, les restes de $u_n$ : 2,0,4,1. Seul le deuxième est nul. Par conséquent, $5\mid u_n$ exactement lorsque $n\equiv1\pmod4$ , c'est-à-dire pour $n=1$ ,5,9,13,… Le premier terme concerné vaut $u_1=10$ , ce qui vérifie le résultat.

Exercice 11 — Construire un critère de divisibilité par 11

Démontrer le critère de la somme alternée des chiffres pour la divisibilité par 11.
L'appliquer à 583792.
Déterminer le chiffre a pour lequel le nombre à quatre chiffres 53a7 est divisible par 11.

Corrigé détaillé

Écrivons un entier décimal $N=a_0+10a_1+10^2a_2+\cdots+10^ra_r$ , où $a_0$ est le chiffre des unités. Comme $10\equiv-1\pmod{11}$ , on a $10^j\equiv(-1)^j\pmod{11}$ . Ainsi N est congru à la somme alternée $a_0-a_1+a_2-a_3+\cdots$ modulo 11. Il est divisible par 11 si et seulement si cette somme l'est. Il n'est pas nécessaire que la somme soit exactement nulle : elle peut valoir 11, -11 ou tout autre multiple.
Pour 583792, en partant des unités, on obtient $2-9+7-3+8-5=0$ . Le nombre est divisible par 11. La vérification exacte est $583792=11\times53072$ .
Pour 53a7, la somme alternée est $7-a+3-5=5-a$ . Comme a est un chiffre de 0 à 9, cette expression appartient à l'intervalle [-4,5]. Son seul multiple de 11 possible est 0. Donc $a=5$ . Le nombre est 5357, et $5357=11\times487$ . La contrainte sur le chiffre rend ici la réponse unique.

Exercice 12 — Un diviseur variable dans une expression polynomiale

Pour n entier positif, montrer que $n+2$ divise $n^2+5$ si et seulement s'il divise 9.
Déterminer tous les n positifs satisfaisant cette condition.
Calculer les quotients correspondants et vérifier les deux solutions.

Corrigé détaillé

L'identité utile est $n^2+5=(n+2)(n-2)+9$ . Si n+2 divise $n^2+5$ , il divise la différence entre ce nombre et $(n+2)(n-2)$ , donc il divise 9. Réciproquement, s'il divise 9, il divise la somme $(n+2)(n-2)+9=n^2+5$ . Les deux implications sont donc établies.
Puisque n est strictement positif, $n+2\geq3$ . Les diviseurs positifs de 9 sont 1, 3 et 9 ; seuls 3 et 9 conviennent. Les équations $n+2=3$ et $n+2=9$ donnent $n=1$ et $n=7$ .
Pour $n=1$ , on a $n^2+5=6$ et $n+2=3$ , donc le quotient est 2. Pour $n=7$ , on a $n^2+5=54$ et $n+2=9$ , donc le quotient est 6. Dans la formule générale, le quotient de divisibilité est $n-2+9/(n+2)$ ; il donne bien 2 puis 6. La réduction à un diviseur d'une constante transforme ainsi un problème apparemment infini en une liste finie de cas.

Exercice 13 — Résidus polynomiaux et obstruction

Construire le tableau des restes de $x^2+x+1$ modulo $7$ pour $x=0,\ldots,6$ .
Déterminer tous les entiers $n$ tels que $7$ divise $n^2+n+1$ .
Montrer que $n^2+n+1$ n’est jamais divisible par $49$ lorsque $n\equiv2\pmod7$ et $n=2+7k$ avec $k\equiv0\pmod7$ .

Corrigé détaillé

1. On obtient le tableau suivant.

$x$	0	1	2	3	4	5	6
Reste	1	3	0	6	0	3	1

2. Un polynôme à coefficients entiers conserve la congruence. Les seules classes donnant zéro sont donc

n\equiv2

n\equiv4\pmod7

. 3. Pour

n=2+7k

n^2+n+1=7+35k+49k^2=7(1+5k+7k^2)

. Si

k\equiv0\pmod7

, le facteur entre parenthèses est congru à

1

modulo

7

; il n’est pas divisible par

7

. Le produit est divisible par

7

mais pas par

49

Exercice 14 — Approfondissement — Des modules non premiers entre eux

Résoudre $x\equiv2\pmod6$ et $x\equiv5\pmod9$ .
Expliquer pourquoi le module final est 18 et non 54.
Le système obtenu en remplaçant la seconde condition par $x\equiv4\pmod9$ est-il soluble ?

Corrigé détaillé

Posons $x=2+6k$ . La seconde condition devient $6k\equiv3\pmod9$ . En divisant coefficient, second membre et module par 3, on obtient $2k\equiv1\pmod3$ , donc $k\equiv2\pmod3$ . On écrit $k=2+3t$ , puis $x=2+6(2+3t)=14+18t$ . Les solutions sont donc exactement $x\equiv14\pmod{18}$ .
Ajouter 18 conserve les restes modulo 6 et modulo 9, car 18 est leur PPCM. Si deux solutions existent, leur différence est divisible par 6 et par 9, donc par 18. Le produit 54 n'est pas la période minimale ; modulo 54, on aurait trois classes, 14, 32 et 50.
Le premier reste impose $x\equiv2\pmod3$ , tandis que le reste 4 modulo 9 impose $x\equiv1\pmod3$ . Ces conditions sont incompatibles. Le critère général exige que les deux restes soient congrus modulo le PGCD des modules, ici 3. Les restes 2 et 5 le sont ; les restes 2 et 4 ne le sont pas.

Exercice 15 — Approfondissement — Les racines de 1 modulo 24

Montrer que le carré de tout entier impair est congru à 1 modulo 8.
En déduire les solutions de $x^2\equiv1\pmod{24}$ .
Expliquer pourquoi il existe plus de deux solutions modulo 24.

Corrigé détaillé

Si x=2k+1, alors $x^2-1=4k(k+1)$ . Les entiers k et k+1 étant consécutifs, leur produit est pair. Il existe donc t tel que k(k+1)=2t, et $x^2-1=8t$ . Tout carré impair est bien congru à 1 modulo 8.
Pour que $x^2\equiv1\pmod{24}$ , il faut que x soit impair. Il faut aussi que x ne soit pas divisible par 3, car les carrés modulo 3 valent 0 ou 1. Réciproquement, si x est impair et non divisible par 3, alors $x^2-1$ est divisible par 8 et par 3 ; ces deux nombres sont premiers entre eux, donc il est divisible par 24. Parmi les restes de 0 à 23, on conserve exactement 1, 5, 7, 11, 13, 17, 19 et 23.
Le module 24 n'est pas premier. La factorisation $(x-1)(x+1)$ peut être divisible par 24 sans qu'un facteur soit lui-même divisible par 24. Par exemple, pour $x=5$ , le produit vaut $4\times6=24$ . On ne peut donc pas imposer uniquement $x=1$ ou $x=-1$ modulo 24.

Exercice 16 — Une divisibilité universelle par 30

Prouver que $n^5-n$ est divisible par 2 et par 3 pour tout entier n.
Vérifier sa divisibilité par 5 sans utiliser le petit théorème de Fermat.
Conclure pour 30, puis expliquer pourquoi 60 ne convient pas toujours.

Corrigé détaillé

Modulo 2, n a pour reste 0 ou 1, et sa cinquième puissance a le même reste : la différence est paire. Modulo 3, on peut prendre les représentants 0,1,-1. Chacun vérifie $r^5-r=0$ , donc $3\mid(n^5-n)$ .
Modulo 5, prenons les représentants 0,1,2,-2,-1. Pour 0,1,-1, la différence est nulle. Pour 2, elle vaut $2^5-2=32-2=30$ ; pour -2, elle vaut $(-2)^5-(-2)=-32+2=-30$ . Ces deux nombres sont divisibles par 5. La liste couvre toutes les classes, donc la divisibilité par 5 est démontrée pour tout entier.
Les nombres 2, 3 et 5 étant deux à deux premiers entre eux, leur produit 30 divise $n^5-n$ . On ne peut pas remplacer systématiquement 30 par 60 : pour $n=2$ , on trouve 30, qui n'est pas divisible par 60. L'argument précédent garantit un facteur 2, mais pas deux. Il n'utilise aucun résultat sur les puissances modulo un nombre premier au-delà d'une vérification exhaustive de petits restes.

Exercice 17 — Pourquoi le quotient et le reste sont uniques

Démontrer l'unicité de la division euclidienne par un entier $b>0$ .
Appliquer cette propriété aux écritures $146=11\times13+3$ et $146=11\times12+14$ .
Déterminer tous les couples entiers (q,r) tels que $146=11q+r$ avec $-5\leq r\leq5$ .

Corrigé détaillé

Supposons $a=bq+r=bq'+r'$ avec $0\leq r,r'<b$ . Par différence, $b(q-q')=r'-r$ . Or $-(b-1)\leq r'-r\leq b-1$ . Le seul multiple de b dans cet intervalle est 0 : donc r'=r, puis q'=q. Cette preuve explique le rôle essentiel de l'encadrement du reste.
La première écriture est euclidienne, car $0\leq3<11$ . La seconde est une égalité correcte, mais 14 n'est pas inférieur à 11 ; elle ne contredit donc pas l'unicité.
Puisque $146\equiv3\pmod{11}$ , le reste r doit être congru à 3 modulo 11. Dans l'intervalle [-5,5], le seul entier de cette classe est 3 : les voisins 3-11=-8 et 3+11=14 sont hors intervalle. On obtient alors q=(146-3)/11=13. Le seul couple est donc (13,3). Un autre choix d'intervalle de longueur 11 pourrait conduire à un reste négatif, mais il faudrait alors annoncer une convention différente de la division euclidienne usuelle.

Exercice 18 — Calendrier et calcul de jours

On code les jours par lundi=0, mardi=1, …, dimanche=6. Un événement commence un jeudi.

Quel jour tombe la date située 1000 jours plus tard ?
Un rappel est envoyé tous les 45 jours : quel jour tombe le septième rappel, le premier ayant lieu 45 jours après le départ ?
À quel premier rappel retrouve-t-on un jeudi ?

Corrigé détaillé

Le jeudi porte le code 3. Comme $1000=7\times142+6$ , le nouveau code est $3+6=9\equiv2\pmod7$ . Mille jours après le départ, on est donc un mercredi. Il s'agit d'un décalage de 1000 jours, sans compter le jour initial comme un jour écoulé.
Le septième rappel survient après $7\times45=315$ jours. Or 315=45×7 est divisible par 7 ; le code est inchangé et le rappel tombe un jeudi. On peut aussi noter que 45 a pour reste 3 modulo 7 et calculer $3+7\times3\equiv3$ .
Le rappel de numéro k retombe un jeudi lorsque $45k\equiv0\pmod7$ , soit $3k\equiv0\pmod7$ . Comme 3 est inversible modulo 7, cela impose $k\equiv0\pmod7$ . Le plus petit k strictement positif est 7. Les six premiers rappels ne peuvent donc pas convenir ; leurs décalages sont les restes 3,6,2,5,1,4, tous non nuls. Le septième est bien le premier retour au jour initial.

Exercice 19 — Approfondissement — Les nombres formés uniquement de 1

Pour

n\geq1

, on note

R_n

le nombre décimal composé de n chiffres 1.

Établir la relation $R_{n+1}=10R_n+1$ et calculer les restes de $R_1$ à $R_6$ modulo 7.
Montrer que $R_n$ est divisible par 7 exactement lorsque n est multiple de 6.
Donner le quotient de $R_6$ par 7.

Corrigé détaillé

Multiplier par 10 décale les chiffres et laisse un zéro final ; ajouter 1 crée le nouveau chiffre des unités. La relation est donc immédiate. En partant de $R_1$ =1 et en réduisant après chaque étape modulo 7, on obtient : 1 ; $10\times1+1=11\equiv4$ ; $10\times4+1=41\equiv6$ ; $10\times6+1=61\equiv5$ ; $10\times5+1=51\equiv2$ ; $10\times2+1=21\equiv0$ .
Après le reste 0, le reste suivant est 1, puis le même calcul déterministe recommence. Le cycle complet est donc 1,4,6,5,2,0 et ne contient qu'un seul zéro. Par répétition, le reste est nul exactement aux indices 6,12,18,… On peut formaliser la répétition par récurrence, puisque deux restes égaux produisent le même reste suivant.
On a $R_6$ =111111, et la division donne $111111=7\times15873$ . Ainsi $R_6$ /7=15873. Le cycle des restes prouve également qu'aucun nombre formé de moins de six chiffres 1 n'est divisible par 7.

Exercice 20 — Approfondissement — Puissances premières dans une factorielle

Déterminer la plus grande puissance de 2 divisant 100!.
Calculer le nombre de zéros terminaux de l'écriture décimale de 100!.
Expliquer pourquoi compter seulement les multiples de 2 ou seulement les multiples de 10 donnerait des réponses fausses.

Corrigé détaillé

Chaque multiple de 2 apporte au moins un facteur 2 ; chaque multiple de 4 en apporte un supplémentaire, et ainsi de suite. L'exposant total vaut $\lfloor100/2\rfloor+\lfloor100/4\rfloor+\lfloor100/8\rfloor+\lfloor100/16\rfloor+\lfloor100/32\rfloor+\lfloor100/64\rfloor=50+25+12+6+3+1=97$ . La plus grande puissance recherchée est donc $2^{97}$ : $2^{98}$ ne divise pas 100!.
Un zéro final correspond à un facteur 10=2×5. Le nombre de facteurs 5 est $\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24$ . Comme 97>24, le facteur limitant est 5. Il y a exactement 24 zéros terminaux.
Compter les 50 multiples de 2 oublierait les facteurs supplémentaires présents dans 4,8,16,… Compter les dix multiples de 10 oublierait les associations entre un facteur 5 et un facteur 2 provenant de nombres différents. Par exemple, le produit 2×5=10 possède un zéro sans que l'un des deux facteurs soit un multiple de 10. Il faut compter les facteurs premiers, pas seulement certains facteurs entiers visibles.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 min Cours de Maths expertes