Exercice 0.1 : Calculer des restes avec les congruences : dix calculs directs

Pour chaque ligne, donnez le reste, le chiffre ou l'entier demandé, sans calculer le grand nombre en entier. Un reste de la division par $n$ est toujours un entier de $\{0\,;1\,;\ldots\,;n-1\}$ , même quand le nombre divisé est négatif.

Une méthode pour les dix lignes : remplacer chaque nombre par son reste modulo $n$ AVANT d'opérer, ce que permet la compatibilité des congruences avec l'addition, la multiplication et les puissances. Pour une puissance, on cherche la première puissance congrue à $1$ (ou le petit théorème de Fermat quand $n$ est premier), puis on divise l'exposant par cette période. Pour $ax\equiv b\ [n]$ , on multiplie par un inverse de $a$ modulo $n$ .

a) Le reste de la division euclidienne de $98\,765$ par $12$ .
b) Le reste de la division euclidienne de $-45$ par $8$ .
c) Le reste de $843+659$ dans la division par $7$ .
d) Le reste de $1\,003\times 998$ dans la division par $11$ .
e) Le reste de $7\,384\,529$ dans la division par $9$ , par la somme de ses chiffres.
f) Le reste de $4^{35}$ dans la division par $9$ .
g) Le chiffre des unités de $8^{103}$ .
h) Le reste de $3^{1\,000}$ dans la division par $17$ , à l'aide du petit théorème de Fermat.
i) L'inverse de $7$ modulo $30$ : l'entier $u$ de $\{0\,;\ldots\,;29\}$ tel que $7u\equiv 1\ [30]$ .
j) Le plus petit entier naturel $x$ tel que $8x\equiv 5\ [21]$ .

Tape tes réponses, la page te dit juste ou faux 0/10

a)

Reste

b)

Reste

c)

Reste

d)

Reste

e)

Reste

f)

Reste

g)

Chiffre des unités

h)

Reste

i)

u

j)

x

Voir la correction

Réponses

a) $98\,765=12\times 8\,230+5$ ; reste $5$
b) $-45=8\times(-6)+3$ ; reste $3$
c) $3+1=4$ ; reste $4$
d) $2\times 8=16\equiv 5$ ; reste $5$
e) $38\equiv 11\equiv 2$ ; reste $2$
f) $4^{35}\equiv 4^{2}\equiv 7$ ; reste $7$
g) $8^{103}\equiv 8^{3}\equiv 2\ [10]$ ; chiffre $2$
h) $3^{1\,000}\equiv 3^{8}\equiv 16$ ; reste $16$
i) $7\times 13=91\equiv 1\ [30]$ ; $u=13$
j) $x\equiv 8\times 5\equiv 19\ [21]$ ; $x=19$

Le geste qui décide de tout : réduire d'abord, calculer ensuite. On ne développe jamais $1\,003\times 998$ ni $3^{1\,000}$ : on remplace chaque facteur par son reste, puis on travaille sur de petits nombres. Et un reste se ramène toujours dans $\{0\,;\ldots\,;n-1\}$ .

a)

$12\times 8\,230=98\,760$ , donc $98\,765=12\times 8\,230+5$ : le reste est $5$ .

b)

$-45=8\times(-6)+3$ , avec $0\le 3<8$ : le reste est $3$ . Piège : $-45=8\times(-5)-5$ donne $-5$ , qui n'est pas un reste, puisqu'un reste est positif ou nul.

c)

$843=7\times 120+3$ et $659=7\times 94+1$ , donc $843+659\equiv 3+1=4\ [7]$ : le reste est $4$ . Contrôle : $1\,502=7\times 214+4$ .

d)

$1\,003=11\times 91+2$ et $998=11\times 90+8$ , donc $1\,003\times 998\equiv 2\times 8=16\equiv 5\ [11]$ : le reste est $5$ . Piège : s'arrêter à $16$ , qui dépasse $10$ et n'est pas encore un reste.

e)

$10\equiv 1\ [9]$ , donc un entier est congru à la somme de ses chiffres : $7+3+8+4+5+2+9=38$ , puis $3+8=11$ et $1+1=2$ . Le reste est $2$ .

f)

$4^{1}\equiv 4$ , $4^{2}=16\equiv 7$ , $4^{3}\equiv 7\times 4=28\equiv 1\ [9]$ : la période est $3$ . Comme $35=3\times 11+2$ , $4^{35}=\left(4^{3}\right)^{11}\times 4^{2}\equiv 1\times 7=7\ [9]$ . Le reste est $7$ .

g)

Le chiffre des unités est le reste modulo $10$ . Les puissances $8^{1}$ à $8^{4}$ finissent par $8$ , $4$ , $2$ , $6$ ( $8^{4}=4\,096$ ), puis $8^{5}$ finit de nouveau par $8$ : le cycle a une période $4$ . Comme $103=4\times 25+3$ , $8^{103}$ finit comme $8^{3}=512$ : le chiffre des unités est $2$ . Piège : diviser l'exposant par une période mal comptée ; avec $3$ au lieu de $4$ , $103=3\times 34+1$ donnerait $8$ . On écrit le cycle jusqu'au retour du premier chiffre avant de diviser.

h)

$17$ est premier et ne divise pas $3$ , donc $3^{16}\equiv 1\ [17]$ . Comme $1\,000=16\times 62+8$ , $3^{1\,000}\equiv 3^{8}\ [17]$ . Puis $3^{4}=81=4\times 17+13\equiv -4$ , donc $3^{8}\equiv(-4)^{2}=16\ [17]$ : le reste est $16$ . Piège : Fermat donne l'exposant $p-1=16$ , pas $p=17$ .

i)

On essaie les multiples de $30$ augmentés de $1$ : $31$ , $61$ , $91=7\times 13$ . Donc $7\times 13=91=3\times 30+1\equiv 1\ [30]$ et l'inverse est $13$ . L'algorithme d'Euclide donne la même chose : $30=4\times 7+2$ , $7=3\times 2+1$ , d'où $1=7-3\times(30-4\times 7)=13\times 7-3\times 30$ .

j)

L'inverse de $8$ modulo $21$ est $8$ , puisque $8\times 8=64=3\times 21+1$ . On multiplie les deux membres par $8$ : $x\equiv 40\equiv 19\ [21]$ . Le plus petit entier naturel est $19$ . Contrôle : $8\times 19=152=7\times 21+5$ . Piège : « diviser par $8$ », ce qui n'a pas de sens modulo $21$ : on multiplie par l'inverse.

Contrôle : chaque reste se vérifie à la calculatrice pour les petits nombres ( $1\,003\times 998=1\,000\,994=11\times 90\,999+5$ ), et pour une puissance on recalcule les premières puissances jusqu'à retrouver $1$ : si la période trouvée ne divise pas $p-1$ quand $n=p$ est premier, une puissance est fausse.

Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.

Exercice 0.2 : Calculer un PGCD et des coefficients de Bézout : neuf calculs directs

Pour chaque ligne, calculez le PGCD, l'entier ou le couple demandé. Quand un couple n'est pas unique, l'énoncé impose le plus petit $u$ (ou $x$ ) strictement positif, pour que la réponse le soit.

Une méthode pour les neuf lignes : l'algorithme d'Euclide, divisions successives jusqu'au reste nul, le PGCD étant le DERNIER reste non nul. Pour un couple de Bézout, on remonte les divisions en partant de la dernière, en n'exprimant jamais que des restes. Pour $ax+by=c$ , on vérifie d'abord que $\mathrm{pgcd}(a\,;b)$ divise $c$ , on simplifie par ce PGCD, puis on multiplie un couple de Bézout par le second membre.

a) $\mathrm{pgcd}(588\,;252)$ .
b) $\mathrm{pgcd}(2\,431\,;1\,547)$ .
c) $\mathrm{pgcd}(1\,350\,;1\,260)$ , par décomposition en facteurs premiers.
d) Le nombre de diviseurs positifs communs à $1\,350$ et $1\,260$ .
e) Les entiers $391$ et $299$ sont-ils premiers entre eux ? Donnez leur PGCD.
f) Le couple $(u\,;v)$ d'entiers tel que $47u+13v=1$ , avec $u$ le plus petit possible strictement positif.
g) Le couple $(u\,;v)$ d'entiers tel que $101u+37v=1$ , avec $u$ le plus petit possible strictement positif.
h) L'équation $26x+16y=7$ a-t-elle des solutions entières ?
i) La solution entière $(x\,;y)$ de $26x+16y=6$ dont $x$ est le plus petit possible strictement positif.

Tape tes réponses, la page te dit juste ou faux 0/13

a)

\mathrm{pgcd}(588\,;252)

b)

\mathrm{pgcd}(2\,431\,;1\,547)

c)

\mathrm{pgcd}(1\,350\,;1\,260)

d)

Nombre de diviseurs communs

e)

Premiers entre eux

PGCD

f)

u

v

g)

u

v

h)

Solutions entières

i)

x

y

Voir la correction

Réponses

a) $\mathrm{pgcd}(588\,;252)=84$
b) $\mathrm{pgcd}(2\,431\,;1\,547)=221$
c) $2\times 3^{2}\times 5=90$
d) diviseurs de $90=2\times 3^{2}\times 5$ : $2\times 3\times 2=12$
e) non, $\mathrm{pgcd}(391\,;299)=23$
f) $5\times 47-18\times 13=1$ ; $(5\,;-18)$
g) $11\times 101-30\times 37=1$ ; $(11\,;-30)$
h) non, $2$ ne divise pas $7$
i) $26\times 7+16\times(-11)=6$ ; $(7\,;-11)$

Le geste qui décide de tout : écrire chaque division euclidienne en entier, $a=bq+r$ avec $0\le r<b$ , une ligne par division. Le PGCD se lit au dernier reste non nul, et la remontée de Bézout n'est possible que si chaque ligne est écrite.

a)

$588=2\times 252+84$ , puis $252=3\times 84+0$ . Le dernier reste non nul est $84$ : $\mathrm{pgcd}(588\,;252)=84$ .

b)

$2\,431=1\times 1\,547+884$ ; $1\,547=1\times 884+663$ ; $884=1\times 663+221$ ; $663=3\times 221+0$ . Donc $\mathrm{pgcd}(2\,431\,;1\,547)=221$ . Piège : répondre $0$ , le dernier reste, ou $3$ , le dernier quotient.

c)

$1\,350=2\times 3^{3}\times 5^{2}$ et $1\,260=2^{2}\times 3^{2}\times 5\times 7$ . Le PGCD prend chaque facteur premier COMMUN avec le plus petit exposant : $2^{1}\times 3^{2}\times 5^{1}=90$ . Piège : prendre les plus grands exposants, ce qui donne un multiple commun et non un diviseur.

d)

Les diviseurs communs de deux entiers sont exactement les diviseurs de leur PGCD, ici $90=2\times 3^{2}\times 5$ . Un diviseur s'écrit $2^{\alpha}3^{\beta}5^{\gamma}$ avec $\alpha\in\{0\,;1\}$ , $\beta\in\{0\,;1\,;2\}$ , $\gamma\in\{0\,;1\}$ : $2\times 3\times 2=12$ diviseurs communs positifs.

e)

$391=1\times 299+92$ ; $299=3\times 92+23$ ; $92=4\times 23+0$ . Donc $\mathrm{pgcd}(391\,;299)=23$ , et les deux entiers ne sont PAS premiers entre eux : $391=17\times 23$ et $299=13\times 23$ . Piège : conclure « premiers entre eux » parce qu'aucun petit diviseur ( $2$ , $3$ , $5$ , $7$ ) ne divise les deux.

f)

$47=3\times 13+8$ ; $13=1\times 8+5$ ; $8=1\times 5+3$ ; $5=1\times 3+2$ ; $3=1\times 2+1$ . On remonte : $1=3-2=3-(5-3)=2\times 3-5=2(8-5)-5=2\times 8-3\times 5=2\times 8-3(13-8)=5\times 8-3\times 13=5(47-3\times 13)-3\times 13=5\times 47-18\times 13$ . Donc $(u\,;v)=(5\,;-18)$ , et $u=5$ est bien le plus petit positif, les solutions en $u$ étant espacées de $13$ . Vérification : $235-234=1$ .

g)

$101=2\times 37+27$ ; $37=1\times 27+10$ ; $27=2\times 10+7$ ; $10=1\times 7+3$ ; $7=2\times 3+1$ . On remonte : $1=7-2\times 3=7-2(10-7)=3\times 7-2\times 10=3(27-2\times 10)-2\times 10=3\times 27-8\times 10=3\times 27-8(37-27)=11\times 27-8\times 37=11(101-2\times 37)-8\times 37=11\times 101-30\times 37$ . Donc $(u\,;v)=(11\,;-30)$ . Vérification : $1\,111-1\,110=1$ .

h)

$26=1\times 16+10$ ; $16=1\times 10+6$ ; $10=1\times 6+4$ ; $6=1\times 4+2$ ; $4=2\times 2$ : $\mathrm{pgcd}(26\,;16)=2$ . Le premier membre $26x+16y$ est toujours pair, et $7$ est impair : aucune solution entière.

i)

Cette fois $2$ divise $6$ : on simplifie en $13x+8y=3$ . Un couple de Bézout de $13$ et $8$ : $13\times 5+8\times(-8)=1$ . On multiplie par $3$ : $(15\,;-24)$ est solution. Les solutions sont $x=15+8k$ , $y=-24-13k$ ; le plus petit $x$ strictement positif est $15-8=7$ , avec $y=-24+13=-11$ . Vérification : $26\times 7+16\times(-11)=182-176=6$ . Piège : s'arrêter à $(15\,;-24)$ , qui est juste mais dont le $x$ n'est pas le plus petit.

Contrôle : un PGCD divise les deux nombres (on fait les deux divisions à la calculatrice) ; un couple de Bézout se vérifie en recalculant $au+bv$ ; une solution de $ax+by=c$ aussi, et l'on obtient les autres en ajoutant $\frac{b}{d}$ à $x$ et en retranchant $\frac{a}{d}$ à $y$ , où $d$ est le PGCD.

Exercice 1 : Division euclidienne et divisibilité

On rappelle que le reste d'une division euclidienne est toujours positif ou nul, et strictement inférieur au diviseur.

a) Effectuez la division euclidienne de 2024 par 7.
b) Effectuez la division euclidienne de $-17$ par 5. Attention au signe du reste.
c) Déterminez tous les diviseurs positifs de 36.
d) Démontrez que pour tout entier naturel $n$ , le produit $n(n+1)$ est pair.

Voir la correction

Réponses

a) $2024=7\times 289+1$
b) $-17=5\times(-4)+3$
c) $1,2,3,4,6,9,12,18,36$ : $9$ diviseurs
d) Deux consécutifs : l'un est pair

a)

On cherche le plus grand multiple de $7$ inférieur ou égal à $2024$ : $7\times 289=2023$ , donc $2024=7\times 289+1$ , avec $0\leq 1<7$ ✓. Le quotient est $289$ et le reste $1$ . La condition sur le reste doit être écrite, c'est elle qui garantit l'unicité du couple.

b)

Le piège est ici, et il coûte des points chaque année. On cherche $q$ tel que le reste tombe dans $[0\,;\,5[$ . Avec $q=-4$ : $5\times(-4)=-20$ et $-17-(-20)=3$ , donc $-17=5\times(-4)+3$ , avec quotient $-4$ et reste $3$ ✓. L'erreur classique consiste à écrire $-17=5\times(-3)-2$ , ce qui est une égalité vraie mais N'EST PAS une division euclidienne, car $-2$ n'est pas un reste valable. Le reste est toujours POSITIF, même pour un dividende négatif, et le quotient descend donc d'une unité.

c)

On décompose d'abord : $36=2^{2}\times 3^{2}$ . Les diviseurs positifs s'obtiennent en prenant chaque facteur premier à une puissance comprise entre $0$ et son exposant : $1$ , $2$ , $3$ , $4$ , $6$ , $9$ , $12$ , $18$ et $36$ . Il y en a $(2+1)\times(2+1)=9$ , formule qui donne le compte sans énumérer et qui resservira à l'exercice 5.

d)

Parmi deux entiers CONSÉCUTIFS, l'un est nécessairement pair, et l'on rédige par disjonction de cas. Si $n$ est pair, alors $n(n+1)$ l'est comme multiple de $n$ ; si $n$ est impair, alors $n+1$ est pair et le produit l'est encore. Dans tous les cas $n(n+1)$ est divisible par $2$ . Le même argument, étendu à trois entiers consécutifs, montrerait que leur produit est divisible par $6$ .

La division euclidienne est la brique de tout le chapitre, et il faut en retenir deux choses. D'une part le couple $(q\,;\,r)$ est UNIQUE dès qu'on impose $0\leq r<b$ , ce qui n'est vrai que grâce à cette condition, comme le montre la question b). D'autre part le reste est exactement ce que mesure la congruence : dire que $2024\equiv 1\ [7]$ , c'est dire que sa division par $7$ laisse un reste de $1$ . Toute l'arithmétique du programme consiste ensuite à ne travailler QUE sur les restes, ce qui permet de traiter des nombres à mille chiffres sans jamais les écrire.

Exercice 2 : Algorithme d'Euclide

Déterminez les PGCD demandés en écrivant toutes les étapes de l'algorithme d'Euclide.

a) $\mathrm{pgcd}(1071,\ 462)$
b) $\mathrm{pgcd}(240,\ 156)$
c) Retrouvez le résultat de b) par décomposition en facteurs premiers.
d) Les entiers 35 et 64 sont-ils premiers entre eux ?

Voir la correction

Réponses

a) $21$
b) $12$
c) $2^{2}\times 3=12$ ; PPCM $3\,120$
d) Oui : $\mathrm{pgcd}=1$

a)

On divise, puis on recommence avec le diviseur et le reste : $1071=2\times 462+147$ ; $462=3\times 147+21$ ; $147=7\times 21+0$ . Le dernier reste NON NUL est $21$ , donc $\text{pgcd}(1071\,;\,462)=21$ . Trois divisions ont suffi, là où l'énumération des diviseurs de $1071$ en aurait demandé des dizaines.

b)

$240=1\times 156+84$ ; $156=1\times 84+72$ ; $84=1\times 72+12$ ; $72=6\times 12+0$ . Donc $\text{pgcd}(240\,;\,156)=12$ . On remarquera que les trois premiers quotients valent $1$ , ce qui rend l'algorithme plus lent : c'est le cas le plus défavorable, et il se produit quand les deux nombres sont proches l'un de l'autre. La figure du corrigé pave le rectangle $240\times 156$ par des carrés : chaque division euclidienne y devient une rangée de carrés identiques, et le côté du dernier carré, $12$ , est le PGCD.

c)

$240=2^{4}\times 3\times 5$ et $156=2^{2}\times 3\times 13$ . On garde les facteurs COMMUNS affectés du plus petit exposant : $2^{2}\times 3=12$ ✓, le même résultat. On peut d'ailleurs en déduire le PPCM au passage, en prenant tous les facteurs au plus grand exposant : $2^{4}\times 3\times 5\times 13=3\,120$ , et l'on vérifie la relation $12\times 3\,120=37\,440=240\times 156$ ✓.

d)

$35=5\times 7$ et $64=2^{6}$ : ils n'ont aucun facteur premier commun, donc $\text{pgcd}(35\,;\,64)=1$ et ils sont PREMIERS ENTRE EUX. Le point à retenir est qu'aucun des deux n'est lui-même un nombre premier : être premiers entre eux est une propriété du COUPLE, pas de chaque nombre, ce que l'exercice 9 reprendra.

Les deux méthodes ne se valent pas, et il faut savoir choisir. L'algorithme d'Euclide est toujours praticable et très rapide, même sur des nombres de plusieurs centaines de chiffres, et c'est celui qu'utilisent les ordinateurs. La décomposition en facteurs premiers est plus parlante et donne en prime le PPCM et le nombre de diviseurs, mais elle devient impraticable dès que les nombres dépassent quelques dizaines de chiffres, la factorisation étant un problème réputé difficile. C'est d'ailleurs sur cette asymétrie, facile de multiplier mais difficile de factoriser, que repose la cryptographie moderne.

Exercice 3 : Congruences

Toutes les réponses doivent être justifiées par un raisonnement sur les congruences, sans calcul de la puissance complète.

a) Déterminez le reste de 2024 dans la division par 7.
b) Déterminez le reste de $3^{100}$ dans la division par 7.
c) Déterminez le chiffre des unités de $7^{2024}$ .
d) Résolvez la congruence $3x\equiv 1\ [7]$ .

Voir la correction

Réponses

a) $1$
b) $4$ (cycle de longueur $6$ )
c) $1$ (cycle de longueur $4$ )
d) $x\equiv 5\ [7]$

a)

D'après l'exercice 1, $2024=7\times 289+1$ , donc $2024\equiv 1\ [7]$ et le reste vaut $1$ . La congruence n'est qu'une autre écriture de la division euclidienne, et c'est cette écriture qui va permettre de calculer sur des puissances énormes. Compter modulo $n$ , c'est tourner sur un cercle à $n$ points : on revient au même endroit dès qu'on a bouclé un tour.

b)

On ne calcule surtout PAS $3^{100}$ , qui compte quarante-huit chiffres. On cherche le CYCLE des puissances de $3$ modulo $7$ : $3^{1}\equiv 3$ , $3^{2}\equiv 2$ , $3^{3}\equiv 6$ , $3^{4}\equiv 4$ , $3^{5}\equiv 5$ , $3^{6}\equiv 1$ . Dès qu'on retombe sur $1$ , tout recommence : le cycle a pour longueur $6$ . On divise alors l'exposant par cette longueur, $100=6\times 16+4$ , d'où $3^{100}=\left(3^{6}\right)^{16}\times 3^{4}\equiv 1^{16}\times 3^{4}\equiv 4\ [7]$ . Le reste vaut $4$ .

c)

Le chiffre des unités d'un entier est son reste MODULO 10, ce qu'il faut reconnaître pour transformer la question. Les puissances de $7$ modulo $10$ sont $7$ , $9$ , $3$ , $1$ , puis le cycle recommence : sa longueur est $4$ . Or $2024=4\times 506$ exactement, donc $7^{2024}=\left(7^{4}\right)^{506}\equiv 1\ [10]$ et le chiffre des unités est $1$ .

d)

Comme les restes modulo $7$ sont en nombre fini, on peut tous les tester : $3\times 0=0$ , $3\times 1=3$ , $3\times 2=6$ , $3\times 3=9\equiv 2$ , $3\times 4=12\equiv 5$ , $3\times 5=15=14+1\equiv 1$ ✓. Donc $x\equiv 5\ [7]$ , c'est-à-dire $x\in\{\ldots\,;\,-2\,;\,5\,;\,12\,;\,19\,;\,\ldots\}$ . On dit que $5$ est l'INVERSE de $3$ modulo $7$ .

La méthode du cycle est le cœur du chapitre et se réutilise telle quelle. On calcule les puissances successives modulo $n$ jusqu'à retomber sur $1$ , ce qui donne la longueur $\ell$ du cycle ; on divise l'exposant par $\ell$ ; et seul le RESTE de cette division compte. La longueur du cycle, appelée ordre, divise toujours $n-1$ quand $n$ est premier, ce qui est le contenu du petit théorème de Fermat de l'exercice 10 : ici $6$ divise bien $7-1=6$ ; pour le module $10$ , qui n'est pas premier, l'ordre $4$ divise tout de même $4$ , le nombre d'entiers inversibles modulo $10$ . Il faut retenir qu'un exposant énorme n'est jamais un obstacle, seul son reste modulo la longueur du cycle importe.

Exercice 4 : Critères de divisibilité par les congruences

Cet exercice montre d'où viennent les critères de divisibilité appris au collège.

a) Montrez que $10\equiv 1\ [9]$ , puis que $10^{k}\equiv 1\ [9]$ pour tout entier naturel $k$ .
b) Déduisez-en qu'un entier est congru à la somme de ses chiffres modulo 9.
c) Appliquez ce critère à 5823 : ce nombre est-il divisible par 9 ?
d) Montrez que $10\equiv-1\ [11]$ et déduisez-en le critère de divisibilité par 11.
e) Le nombre 5823 est-il divisible par 11 ?

Voir la correction

Réponses

a) $10\equiv 1$ , donc $10^{k}\equiv 1\ [9]$
b) $N\equiv$ somme des chiffres $[9]$
c) Somme $18$ : divisible par $9$
d) $10\equiv -1\ [11]$ : somme alternée
e) Somme alternée $4$ : non divisible

a)

$10-1=9$ est divisible par $9$ , donc $10\equiv 1\ [9]$ . La compatibilité des congruences avec le PRODUIT permet ensuite d'élever à la puissance : $10^{k}\equiv 1^{k}=1\ [9]$ pour tout entier naturel $k$ . C'est cette compatibilité, admise du cours, qui autorise tout le calcul modulaire.

b)

Un entier s'écrit dans le système décimal $N=\sum_{k}a_{k}10^{k}$ , où les $a_{k}$ sont ses chiffres. Comme $10^{k}\equiv 1\ [9]$ , chaque terme $a_{k}10^{k}$ est congru à $a_{k}$ , donc par somme $N\equiv\sum_{k}a_{k}\ [9]$ : un entier est congru à la SOMME DE SES CHIFFRES modulo $9$ . En particulier, $N$ est divisible par $9$ si et seulement si cette somme l'est, et l'on peut répéter l'opération autant que nécessaire.

c)

La somme des chiffres de $5\,823$ vaut $5+8+2+3=18$ , qui est divisible par $9$ . Donc $5\,823$ l'est aussi, et l'on vérifie : $5\,823=9\times 647$ ✓. On aurait pu resommer, $1+8=9$ , ce qui conclut encore plus vite.

d)

Cette fois $10+1=11$ est divisible par $11$ , donc $10\equiv-1\ [11]$ , puis $10^{k}\equiv(-1)^{k}\ [11]$ , valeur qui ALTERNE entre $1$ et $-1$ selon la parité de $k$ . Un entier est donc congru modulo $11$ à la somme ALTERNÉE de ses chiffres, en partant du chiffre des unités affecté du signe plus.

e)

La somme alternée vaut $3-2+8-5=4$ , qui n'est pas divisible par $11$ . Donc $5\,823$ ne l'est pas non plus, et le calcul direct confirme même le reste : $5\,823=11\times 529+4$ ✓, on retrouve exactement $4$ .

Cet exercice montre d'où viennent des règles apprises au collège sans justification, et c'est ce qui en fait sa valeur. La méthode se généralise immédiatement : pour obtenir un critère de divisibilité par $n$ , il suffit de calculer $10\ \text{mod}\ n$ et d'en tirer le comportement des puissances. Pour $n=3$ , on retrouve $10\equiv 1$ et donc le même critère que pour $9$ . Pour $n=2$ ou $n=5$ , on a $10\equiv 0$ , donc seul le chiffre des unités compte, ce qui explique ces deux critères. Pour $n=7$ en revanche, les puissances de $10$ suivent un cycle de longueur $6$ sans structure simple, et c'est pourquoi il n'existe pas de critère de divisibilité par $7$ facile à retenir.

Exercice 5 : Nombres premiers

On rappelle que 1 n'est pas un nombre premier.

a) Décomposez 360 en produit de facteurs premiers.
b) Décomposez 2024 en produit de facteurs premiers.
c) Combien 360 admet-il de diviseurs positifs ?
d) Le nombre 221 est-il premier ?
e) Pour tester si un entier $n$ est premier, jusqu'à quelle valeur faut-il chercher des diviseurs ? Justifiez.

Voir la correction

Réponses

a) $360=2^{3}\times 3^{2}\times 5$
b) $2024=2^{3}\times 11\times 23$
c) $24$ diviseurs
d) Non : $221=13\times 17$
e) Jusqu'à $\sqrt{n}$

a)

On divise successivement par les nombres premiers : $360=36\times 10=\left(2^{2}\times 3^{2}\right)\times\left(2\times 5\right)=2^{3}\times 3^{2}\times 5$ . Contrôle : $8\times 9\times 5=360$ ✓.

b)

$2024=2\times 1\,012=2^{2}\times 506=2^{3}\times 253$ . Il reste à factoriser $253$ , qui n'est divisible ni par $2$ , ni par $3$ , ni par $5$ , ni par $7$ , mais $253=11\times 23$ , deux nombres premiers. Donc $2024=2^{3}\times 11\times 23$ ✓.

c)

Le nombre de diviseurs positifs s'obtient en ajoutant $1$ à chaque exposant puis en multipliant, chaque diviseur correspondant à un choix indépendant d'exposant : $(3+1)\times(2+1)\times(1+1)=4\times 3\times 2=24$ diviseurs positifs pour $360$ . La formule évite une énumération de vingt-quatre nombres.

d)

Non. On teste les premiers successifs : $221$ n'est divisible ni par $2$ , ni par $3$ , ni par $5$ , ni par $7$ , ni par $11$ , mais $221=13\times 17$ . Il n'est donc pas premier, et le trouver demande d'aller jusqu'à $13$ , ce qui justifie la question suivante.

e)

Il suffit de chercher jusqu'à $\sqrt{n}$ , et la démonstration tient en une ligne. Si $n=ab$ avec $1<a\leq b$ , alors $a^{2}\leq ab=n$ , donc $a\leq\sqrt{n}$ : tout diviseur non trivial admet un PARTENAIRE, et le plus petit des deux ne dépasse jamais la racine. Pour $221$ , il suffisait donc d'aller jusqu'à $14$ , puisque $14^{2}=196<221<225=15^{2}$ , ce qui représente six divisions à tester au lieu de deux cent dix-neuf.

Le gain de la question e) n'est pas anecdotique, il change la nature du problème. Tester la primalité de $n$ en essayant tous les entiers inférieurs demande environ $n$ divisions, alors que s'arrêter à $\sqrt{n}$ n'en demande que $\sqrt{n}$ : pour un nombre à douze chiffres, on passe de mille milliards d'opérations à un million, soit de plusieurs jours à une fraction de seconde. On peut affiner encore en ne testant que les nombres PREMIERS jusqu'à $\sqrt{n}$ , puisqu'un diviseur composé aurait déjà été détecté par l'un de ses facteurs premiers. Notons enfin la cohérence entre a) et c) : la formule des exposants donne $24$ diviseurs, et l'énumération complète en donnerait bien vingt-quatre, ce qui vaut la peine d'être vérifié une fois pour se convaincre.

Exercice 6 : Coefficients de Bézout

On considère les entiers 17 et 5.

L'option maths expertes est évaluée en contrôle continu, sans écrit au baccalauréat : cette partie B est au niveau des devoirs surveillés de l'année.

a) Justifiez que 17 et 5 sont premiers entre eux.
b) Écrivez les deux divisions euclidiennes de l'algorithme d'Euclide appliqué à 17 et 5.
c) En remontant l'algorithme, déterminez deux entiers $u$ et $v$ tels que $17u+5v=1$ .
d) Vérifiez votre couple.
e) Le couple trouvé est-il unique ? Donnez-en un autre.

Voir la correction

Réponses

a) $17$ premier ne divise pas $5$
b) $17=3\times 5+2$ ; $5=2\times 2+1$
c) $u=-2$ , $v=7$
d) $-34+35=1$ ✓
e) Non : $(3\,;-10)$ par exemple

a)

Le nombre $17$ est premier et ne divise pas $5$ , donc leur seul diviseur commun positif est $1$ : ils sont premiers entre eux. On peut aussi invoquer l'algorithme de la question suivante, dont le dernier reste non nul vaudra $1$ .

b)

$17=3\times 5+2$ , puis $5=2\times 2+1$ . Le reste suivant serait nul, puisque $2=2\times 1+0$ , et le dernier reste non nul vaut bien $1$ ✓, ce qui confirme la coprimalité.

c)

On REMONTE l'algorithme en partant de la dernière égalité, où apparaît le $1$ : $1=5-2\times 2$ . Or la première égalité donne $2=17-3\times 5$ , qu'on substitue dans la précédente : $1=5-2\left(17-3\times 5\right)=5-2\times 17+6\times 5=7\times 5-2\times 17$ . Donc $u=-2$ et $v=7$ . Le point de méthode est de ne JAMAIS calculer les valeurs numériques en cours de route, mais de garder $17$ et $5$ apparents, faute de quoi on obtiendrait $1=1$ et rien d'autre.

d)

$17\times(-2)+5\times 7=-34+35=1$ ✓. Le couple convient. Cette vérification est immédiate et doit toujours être faite, la remontée de l'algorithme étant l'étape la plus propice aux erreurs de signe.

e)

Non, le couple n'est pas unique. En ajoutant $5$ à $u$ et en retranchant $17$ à $v$ , la valeur ne change pas : $17\times 3+5\times(-10)=51-50=1$ ✓. Plus généralement, tous les couples s'écrivent $(-2+5k\,;\,7-17k)$ pour $k$ entier, ce qui donne une INFINITÉ de solutions.

L'identité de Bézout affirme que $au+bv=\text{pgcd}(a\,;\,b)$ admet toujours des solutions entières, et l'algorithme d'Euclide remonté en fournit une explicitement. L'invariance constatée en e) s'explique simplement : ajouter $5$ à $u$ augmente le total de $17\times 5$ , et retrancher $17$ à $v$ le diminue de $5\times 17$ , les deux effets se compensant exactement. C'est ce mécanisme qui donnera la structure de l'ensemble des solutions à l'exercice suivant. Notons enfin l'usage le plus courant de Bézout : le coefficient $v=7$ trouvé ici est précisément l'INVERSE de $5$ modulo $17$ , puisque $5\times 7=35=2\times 17+1\equiv 1\ [17]$ ✓, et c'est ainsi qu'on inverse un nombre modulo $n$ .

Exercice 7 : Équation diophantienne

On cherche tous les couples d'entiers relatifs $(x,\ y)$ vérifiant $17x+5y=3$ .

a) Justifiez que cette équation admet des solutions entières.
b) À partir du couple de Bézout de l'exercice 6, déterminez une solution particulière.
c) Déterminez l'ensemble de toutes les solutions.
d) Vérifiez votre résultat pour deux valeurs différentes du paramètre.
e) Existe-t-il une solution avec $x$ et $y$ tous deux positifs ?
f) Soit $(x\,;\,y)$ une solution de l'équation et $d=\text{pgcd}(x\,;\,y)$ . Montrez que $d$ divise $3$ . Quelles sont les valeurs possibles de $d$ ?
g) On reprend l'écriture $x=-6+5k$ et $y=21-17k$ de la question c). Démontrez que $3$ divise $x$ si et seulement si $k$ est un multiple de $3$ , puis qu'il en est de même pour $y$ .
h) Déduisez-en l'ensemble des solutions $(x\,;\,y)$ telles que $\text{pgcd}(x\,;\,y)=3$ , puis, parmi elles, celle dont l'abscisse $x$ est le plus petit entier strictement positif.

Tape tes réponses, la page te dit juste ou faux 0/11

a)

Solutions car

b)

x_{0}

y_{0}

c)

Solutions

d)

x

pour

k=1

y

pour

k=1

e)

Solution à coordonnées positives ?

f)

Valeurs possibles de d

g)

3 divise x si et seulement si

h)

x

de la solution cherchée

y

de la solution cherchée

Voir la correction

Réponses

a) $\mathrm{pgcd}(17\,;5)=1$ divise $3$
b) $(-6\,;21)$
c) $(-6+5k\,;21-17k)$ , $k\in\mathbb{Z}$
d) $(-1\,;4)$ et $(4\,;-13)$ ✓
e) Non : conditions incompatibles
f) $\text{pgcd}(x\,;y)$ divise $17x+5y=3$ : il vaut $1$ ou $3$
g) $3\mid x\iff 3\mid k$ (Gauss, $\text{pgcd}(3;5)=1$ ) et $y\equiv k\ [3]$
h) $(-6+15j\,;21-51j)$ , $j\in\mathbb{Z}$ ; plus petit $x>0$ : $(9\,;-30)$

a)

L'équation $ax+by=c$ admet des solutions entières si et seulement si $\text{pgcd}(a\,;\,b)$ DIVISE $c$ . Ici $\text{pgcd}(17\,;\,5)=1$ , et $1$ divise $3$ : l'équation admet donc des solutions. Cette vérification préalable est obligatoire, car une équation comme $6x+4y=3$ n'en aurait aucune, $2$ ne divisant pas $3$ .

b)

On part du couple de Bézout de l'exercice 6, $17\times(-2)+5\times 7=1$ , et l'on multiplie TOUT par $3$ : $17\times(-6)+5\times 21=3$ ✓. Une solution particulière est donc $(x_{0}\,;\,y_{0})=(-6\,;\,21)$ . C'est le raccourci à connaître : on résout d'abord l'équation avec second membre $1$ , puis on multiplie.

c)

Soit $(x\,;\,y)$ une solution quelconque. En soustrayant l'égalité particulière de l'égalité générale : $17(x+6)+5(y-21)=0$ , donc $17(x+6)=-5(y-21)$ . Ainsi $5$ divise $17(x+6)$ , et comme $5$ et $17$ sont premiers entre eux, le théorème de GAUSS donne que $5$ divise $x+6$ . On écrit alors $x+6=5k$ , d'où $x=-6+5k$ , et en reportant on obtient $17\times 5k=-5(y-21)$ , soit $y=21-17k$ . Réciproquement ces couples conviennent, ce qu'il faut vérifier pour conclure. L'ensemble des solutions est $\{(-6+5k\,;\,21-17k)\,,\ k\in\mathbb{Z}\}$ .

d)

Pour $k=1$ : le couple $(-1\,;\,4)$ donne $17\times(-1)+5\times 4=-17+20=3$ ✓. Pour $k=2$ : le couple $(4\,;\,-13)$ donne $68-65=3$ ✓. Deux valeurs différentes du paramètre suffisent à donner confiance dans la forme générale.

e)

Il faudrait à la fois $-6+5k\geq 0$ , soit $k\geq 1{,}2$ donc $k\geq 2$ puisque $k$ est entier, et $21-17k\geq 0$ , soit $k\leq\frac{21}{17}\approx 1{,}235$ donc $k\leq 1$ . Ces deux conditions sont INCOMPATIBLES : il n'existe aucune solution à coordonnées toutes deux positives.

f)

$d$ divise $x$ et $d$ divise $y$ , donc $d$ divise toute combinaison linéaire à coefficients entiers de $x$ et de $y$ , en particulier $17x+5y$ .

Or $17x+5y=3$ : $d$ divise donc $3$ .

Les diviseurs positifs de $3$ sont $1$ et $3$ : $d=1$ ou $d=3$ .

Contrôle sur les solutions de d) : $\text{pgcd}(1\,;\,4)=1$ et $\text{pgcd}(4\,;\,13)=1$ ; la solution particulière $(-6\,;\,21)$ a pour PGCD $3$ . Les deux valeurs sont donc atteintes.

Piège : conclure « $d$ divise $17$ et $5$ ». C'est le second membre, $3$ , que $d$ divise, pas les coefficients.

g)

$x=-6+5k$ et $-6$ est un multiple de $3$ , donc $3$ divise $x$ si et seulement si $3$ divise $5k$ .

Si $3$ divise $k$ , il divise $5k$ . Réciproquement, si $3$ divise $5k$ , comme $3$ et $5$ sont premiers entre eux, le théorème de Gauss donne que $3$ divise $k$ .

Donc $3$ divise $x$ si et seulement si $k\equiv 0\ [3]$ .

Pour $y$ : $y=21-17k=21-18k+k$ , et $21-18k$ est un multiple de $3$ , donc $y\equiv k\ [3]$ . Ainsi $3$ divise $y$ si et seulement si $3$ divise $k$ .

Contrôle : $k=3$ donne $(9\,;\,-30)$ , deux multiples de $3$ ; $k=1$ donne $(-1\,;\,4)$ , aucun des deux.

Piège : écrire « $3$ divise $5k$ donc $3$ divise $k$ » sans dire pourquoi. Le théorème de Gauss exige $\text{pgcd}(3\,;\,5)=1$ , et c'est cette hypothèse qu'il faut citer.

h)

D'après f), $\text{pgcd}(x\,;\,y)$ vaut $1$ ou $3$ ; il vaut $3$ si et seulement si $3$ divise à la fois $x$ et $y$ .

D'après g), cela équivaut à $k=3j$ avec $j\in\mathbb{Z}$ . En reportant : $x=-6+15j$ et $y=21-51j$ .

L'ensemble cherché est $\{(-6+15j\,;\,21-51j)\,,\ j\in\mathbb{Z}\}$ ; pour toutes les autres valeurs de $k$ , le PGCD vaut $1$ .

$x>0$ équivaut à $15j>6$ , soit $j>0{,}4$ , donc $j\geq 1$ ; la plus petite abscisse strictement positive est obtenue pour $j=1$ : $(9\,;\,-30)$ .

Contrôle : $17\times 9+5\times(-30)=153-150=3$ ✓ et $\text{pgcd}(9\,;\,30)=3$ ✓.

La structure de l'ensemble des solutions mérite d'être formulée dans le cas général, car elle est toujours la même : une solution PARTICULIÈRE plus la solution générale de l'équation homogène $17x+5y=0$ , dont les solutions sont exactement $(5k\,;\,-17k)$ . C'est la même architecture que pour les équations différentielles ou les systèmes linéaires. Le pas de $5$ sur $x$ et de $-17$ sur $y$ n'est pas arbitraire : ce sont les coefficients de l'équation, échangés et affectés d'un signe, divisés par le PGCD. Enfin, la question e) illustre pourquoi ces équations s'appellent diophantiennes et servent en pratique : dès qu'on cherche des quantités entières et positives, comme des nombres d'objets, la contrainte de signe restreint l'infinité de solutions à un ensemble fini, parfois vide.

Exercice 8 : Théorème de Gauss

Le théorème de Gauss affirme que si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$ .

L'hypothèse de coprimalité est indispensable, comme le montre la dernière question.

a) Soit $n$ un entier tel que 7 divise $5n$ . Démontrez que 7 divise $n$ .
b) Résolvez la congruence $5x\equiv 0\ [7]$ .
c) Soit $n$ un entier tel que 6 divise $4n$ . Peut-on en conclure que 6 divise $n$ ? Donnez un contre-exemple.
d) Expliquez précisément quelle hypothèse manque dans la question c).
e) Que peut-on tout de même conclure dans la situation de la question c) ?

Voir la correction

Réponses

a) Gauss : $7\mid 5n$ et $\mathrm{pgcd}(7\,;5)=1$
b) Les multiples de $7$
c) Non : $n=3$
d) $\mathrm{pgcd}(6\,;4)=2\neq 1$
e) $3$ divise $n$

a)

Le nombre $7$ divise le produit $5\times n$ , et $\text{pgcd}(7\,;\,5)=1$ puisque $7$ est premier et ne divise pas $5$ . Les deux hypothèses du théorème de Gauss sont donc réunies, et il s'applique : $7$ divise $n$ . Il faut énoncer les deux hypothèses séparément, c'est ce que le barème vérifie.

b)

La congruence $5x\equiv 0\ [7]$ signifie exactement que $7$ divise $5x$ . D'après la question a), $7$ divise alors $x$ , c'est-à-dire $x\equiv 0\ [7]$ . Réciproquement, tout multiple de $7$ convient puisque $5x$ en est alors un aussi. L'ensemble des solutions est donc l'ensemble des MULTIPLES de $7$ .

c)

Non, on ne peut rien conclure. Contre-exemple : $n=3$ . Alors $4n=12$ , qui est bien divisible par $6$ , alors que $6$ ne divise pas $3$ . Un seul contre-exemple suffit à démolir l'implication.

d)

Il manque la COPRIMALITÉ : $\text{pgcd}(6\,;\,4)=2$ , qui n'est pas égal à $1$ . Le théorème de Gauss ne s'applique donc pas, et sa conclusion tombe. C'est un cas typique où l'on ne peut pas invoquer un théorème dont une hypothèse est en défaut, même si la conclusion paraît plausible.

e)

On peut tout de même conclure quelque chose, en SIMPLIFIANT d'abord par le PGCD. De $6\mid 4n$ on tire, en divisant les deux membres par $2$ , que $3$ divise $2n$ . Or $\text{pgcd}(3\,;\,2)=1$ , et cette fois Gauss s'applique : $3$ divise $n$ . On vérifie sur le contre-exemple de c) : $n=3$ est bien divisible par $3$ ✓, et la conclusion affaiblie est donc correcte là où la forte échouait.

Le théorème de Gauss est l'outil qui autorise à SIMPLIFIER en arithmétique, opération qui va de soi dans $\mathbb{R}$ mais qui devient délicate chez les entiers. Sans hypothèse de coprimalité, on ne peut rien simplifier, et l'exercice 9 en donnera une variante sur les congruences. La démarche de la question e) est celle qu'il faut retenir : quand l'hypothèse manque, on ne renonce pas, on divise par le PGCD pour la faire apparaître, puis on applique le théorème à la version réduite. C'est exactement ce qu'on fait pour résoudre une équation diophantienne dont le PGCD ne vaut pas $1$ .

Exercice 9 : Quatre implications fausses

Chacune des affirmations suivantes est fausse. Corrigez-la et donnez un contre-exemple.

a) « Si $a$ et $b$ sont premiers entre eux, alors $a$ ou $b$ est un nombre premier. »
b) « Si $a$ divise $bc$ , alors $a$ divise $b$ ou $a$ divise $c$ . »
c) « Si $ac\equiv bc\ [n]$ , alors $a\equiv b\ [n]$ . »
d) « 1 est un nombre premier, puisqu'il n'est divisible que par 1 et par lui-même. »

Voir la correction

Réponses

a) Faux : $8$ et $9$
b) Faux : $6\mid 12$ mais ni $4$ ni $3$
c) Faux : simplifier exige $\mathrm{pgcd}(c\,;n)=1$
d) Faux : un seul diviseur

a)

Faux. Contre-exemple : $a=8$ et $b=9$ . Leur PGCD vaut $1$ , ils sont donc premiers ENTRE EUX, et pourtant $8=2^{3}$ et $9=3^{2}$ ne sont ni l'un ni l'autre des nombres premiers. La confusion vient du vocabulaire : être premier est une propriété d'un NOMBRE, être premiers entre eux est une propriété du COUPLE, et les deux notions sont indépendantes.

b)

Faux. Contre-exemple : $a=6$ , $b=4$ et $c=3$ . On a $bc=12$ , divisible par $6$ , alors que $6$ ne divise ni $4$ ni $3$ . L'implication redevient vraie dans deux cas seulement : si $a$ est PREMIER, c'est le lemme d'Euclide, ou si l'on ajoute une hypothèse de coprimalité, ce qui donne le théorème de Gauss de l'exercice 8. Sans l'une de ces deux conditions, l'énoncé est faux.

c)

Faux. On ne peut simplifier par $c$ que si $c$ et le MODULE $n$ sont premiers entre eux. Contre-exemple modulo $6$ avec $c=2$ : $2\times 3=6\equiv 0$ et $2\times 0=0\equiv 0$ , donc $2\times 3\equiv 2\times 0\ [6]$ , et pourtant $3\not\equiv 0\ [6]$ . Ici $\text{pgcd}(2\,;\,6)=2\neq 1$ , ce qui explique l'échec. La règle correcte est que la simplification donne $a\equiv b\ \left[\frac{n}{\text{pgcd}(c\,;\,n)}\right]$ , ici modulo $3$ , et l'on vérifie bien que $3\equiv 0\ [3]$ ✓.

d)

Faux. Un nombre premier est par définition un entier admettant EXACTEMENT DEUX diviseurs positifs distincts. Or $1$ n'en a qu'un seul, lui-même, et il est donc exclu. Cette exclusion n'est pas une convention arbitraire : c'est elle qui rend UNIQUE la décomposition en facteurs premiers, car sinon on pourrait écrire $12=2^{2}\times 3=1\times 2^{2}\times 3=1^{17}\times 2^{2}\times 3$ et une infinité d'autres.

Trois de ces quatre erreurs portent sur une hypothèse manquante, et c'est le fil de tout le chapitre : en arithmétique, les théorèmes sont fragiles et leurs hypothèses ne sont jamais décoratives. La coprimalité en particulier apparaît partout, chez Gauss, dans la simplification des congruences et dans l'existence d'un inverse modulaire, et son absence fait toujours tomber la conclusion. La quatrième erreur est d'une autre nature, c'est une question de DÉFINITION, et elle rappelle qu'une définition bien posée est souvent celle qui rend un théorème vrai plutôt que celle qui paraît naturelle.

Exercice 10 : Petit théorème de Fermat

Le petit théorème de Fermat affirme que si $p$ est premier et ne divise pas $a$ , alors $a^{p-1}\equiv 1\ [p]$ .

Il permet de calculer le reste de très grandes puissances sans jamais les développer.

a) Déterminez le reste de $2^{100}$ dans la division par 11.
b) Déterminez le reste de $3^{2024}$ dans la division par 13.
c) Déterminez le reste de $7^{2024}$ dans la division par 13.
d) Pour la question b), on peut aussi remarquer que $3^{3}\equiv 1\ [13]$ . Vérifiez-le et refaites le calcul avec cet ordre plus court.
e) Pourquoi le théorème ne s'applique-t-il pas au calcul du reste de $6^{100}$ modulo 12 ?

Voir la correction

Réponses

a) $1$
b) $9$
c) $3$
d) $3^{3}\equiv 1$ ; reste $9$
e) $12$ n'est pas premier

a)

Le nombre $11$ est premier et ne divise pas $2$ , donc le petit théorème de Fermat s'applique : $2^{10}\equiv 1\ [11]$ . Comme $100=10\times 10$ , on obtient $2^{100}=\left(2^{10}\right)^{10}\equiv 1^{10}=1\ [11]$ . Le reste vaut $1$ . On a ainsi traité un nombre de trente et un chiffres sans jamais l'écrire.

b)

$13$ est premier et ne divise pas $3$ , donc $3^{12}\equiv 1\ [13]$ . On divise l'exposant par $12$ : $2\,024=12\times 168+8$ . Donc $3^{2024}=\left(3^{12}\right)^{168}\times 3^{8}\equiv 3^{8}\ [13]$ . Reste à calculer $3^{8}$ modulo $13$ par élévations au carré successives : $3^{2}=9$ , $3^{4}\equiv 81\equiv 3$ puisque $81=78+3$ , puis $3^{8}\equiv 3^{2}=9\ [13]$ . Le reste vaut $9$ .

c)

Même démarche : $7^{12}\equiv 1\ [13]$ et $2\,024=12\times 168+8$ , donc $7^{2024}\equiv 7^{8}\ [13]$ . On calcule par carrés successifs : $7^{2}=49\equiv 10$ , $7^{4}\equiv 10^{2}=100\equiv 9$ puisque $100=91+9$ , et $7^{8}\equiv 9^{2}=81\equiv 3\ [13]$ . Le reste vaut $3$ .

d)

Vérifions : $3^{3}=27=2\times 13+1$ , donc $3^{3}\equiv 1\ [13]$ ✓. L'ORDRE de $3$ modulo $13$ vaut donc $3$ , et non $12$ : c'est un diviseur de $12$ , comme le théorème de Lagrange le garantit. On écrit alors $2\,024=3\times 674+2$ , d'où $3^{2024}\equiv 3^{2}=9\ [13]$ ✓. On retrouve le même reste avec un calcul nettement plus court, puisqu'il n'a fallu élever qu'au carré au lieu d'aller jusqu'à la puissance huitième.

e)

Parce que $12$ n'est pas PREMIER. Le petit théorème de Fermat exige un module premier, et son hypothèse est ici en défaut. On remarque d'ailleurs que $\text{pgcd}(6\,;\,12)=6\neq 1$ , ce qui empêche toute inversibilité de $6$ modulo $12$ : les puissances de $6$ ne reviennent jamais à $1$ , elles valent $6$ puis $0$ dès l'exposant $2$ , et $6^{100}\equiv 0\ [12]$ . Il faudrait passer par un autre outil, le théorème d'Euler, qui remplace $p-1$ par le nombre d'entiers inversibles modulo $n$ .

Le contraste entre b) et d) porte l'enseignement principal : le théorème de Fermat donne un exposant qui MARCHE toujours, à savoir $p-1$ , mais pas nécessairement le plus petit. L'ordre réel divise $p-1$ et peut être bien plus court, ici $3$ au lieu de $12$ , ce qui divise le travail par quatre. En pratique on applique donc Fermat pour garantir un cycle, puis on cherche s'il n'existe pas un exposant plus court en testant les diviseurs de $p-1$ : pour $13$ , ce sont $1$ , $2$ , $3$ , $4$ , $6$ et $12$ . La question e) rappelle enfin la limite : dès que le module n'est pas premier, le théorème ne s'applique plus, et certains nombres n'ont même aucun ordre puisqu'ils ne reviennent jamais à $1$ .

Exercice 11 : Des équations impossibles, prouvées par les congruences

Pour montrer qu'une équation n'a aucune solution entière, il suffit parfois de trouver un module où elle est impossible : si les deux membres ne peuvent jamais avoir le même reste, ils ne peuvent pas être égaux.

a) Quels restes le carré d'un entier peut-il avoir modulo $3$ ?
b) L'équation $x^{2}-3y^{2}=2$ a-t-elle des solutions entières ?
c) Soit $a$ , $b$ , $c$ des entiers tels que $a^{2}+b^{2}=c^{2}$ . Montrez que $3$ divise $a$ ou $b$ . Vérifiez-le sur le triplet $(5\,;12\,;13)$ .
d) Les carrés modulo $8$ valent $0$ , $1$ ou $4$ . Montrez qu'un entier congru à $7$ modulo $8$ n'est jamais somme de trois carrés, puis calculez le reste de $2\,023$ modulo $8$ .
e) Les cubes modulo $9$ valent $0$ , $1$ ou $8$ . Quels restes une somme de trois cubes ne peut-elle jamais avoir ? Calculez le reste de $2\,021$ modulo $9$ et concluez.

Voir la correction

Réponses

a) Carré $\equiv 0$ ou $1\ [3]$
b) Aucune solution : $x^{2}\equiv 2\ [3]$ impossible
c) Sinon $c^{2}\equiv 2\ [3]$ ; ici $12$
d) Jamais $7$ modulo $8$ ; $2\,023\equiv 7$
e) Jamais $4$ ni $5$ modulo $9$ ; $2\,021\equiv 5$ : impossible

a)

$0^{2}=0$ , $1^{2}=1$ , $2^{2}=4\equiv 1\ [3]$ : un carré est congru à $0$ ou à $1$ modulo $3$ , jamais à $2$ .

b)

Modulo $3$ , $3y^{2}\equiv 0$ , donc l'équation donnerait $x^{2}\equiv 2\ [3]$ , impossible d'après a). Elle n'a AUCUNE solution entière, et on l'a prouvé sans essayer un seul couple.

c)

Si ni $a$ ni $b$ n'est multiple de $3$ , alors $a^{2}\equiv 1$ et $b^{2}\equiv 1$ , donc $c^{2}=a^{2}+b^{2}\equiv 2\ [3]$ , impossible. Par contraposée, $3$ divise $a$ ou $b$ . Pour $(5\,;12\,;13)$ : $25+144=169$ ✓, et c'est $12$ qui est multiple de $3$ .

d)

Trois restes pris dans $\{0\,;1\,;4\}$ ont pour somme $0,1,2,3,4,5,6,8,9$ ou $12$ , soit modulo $8$ : $0,1,2,3,4,5,6$ ; le reste $7$ n'est JAMAIS atteint. Or $2\,023=8\times 252+7$ : $2\,023$ n'est pas somme de trois carrés, il en faut au moins quatre.

e)

Trois restes pris dans $\{0\,;1\,;8\}$ donnent modulo $9$ les sommes $0,1,2,3,6,7,8$ : jamais $4$ ni $5$ . Or $2\,021=9\times 224+5$ , donc $2\,021$ n'est pas somme de trois cubes d'entiers. Pour $4$ et $5$ modulo $9$ , la question est close ; pour les autres restes, elle est encore étudiée par les chercheurs.

Exercice 12 : La clé de contrôle d'un code-barres

Un code-barres EAN-13 compte treize chiffres $d_{1}d_{2}\ldots d_{13}$ . Le dernier est une clé de contrôle, choisie pour que $S=d_{1}+3d_{2}+d_{3}+3d_{4}+\cdots+d_{11}+3d_{12}+d_{13}$ soit divisible par $10$ : les chiffres de rang impair ont le poids $1$ , ceux de rang pair le poids $3$ .

Les douze premiers chiffres d'un produit sont $3\ 7\ 6\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8$ .

a) Calculez la somme pondérée des douze premiers chiffres.
b) Déterminez la clé de contrôle $d_{13}$ .
c) Un chiffre de rang pair est mal lu : $a$ devient $b\neq a$ . Montrez que l'erreur est toujours détectée.
d) Deux chiffres voisins $a$ et $b$ sont inversés. De combien varie $S$ ? Pour quelle valeur de $|a-b|$ l'erreur passe-t-elle inaperçue ?
e) Le lecteur lit $3\ 7\ 6\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 8\ 7\ 4$ . Calculez le reste de $S$ modulo $10$ et concluez.

Voir la correction

Réponses

a) $106$
b) $d_{13}=4$
c) Variation $3(b-a)$ , jamais multiple de $10$
d) Variation $2(a-b)$ ; non détecté si $|a-b|=5$
e) $S\equiv 8\ [10]$ : code refusé

a)

Rangs impairs : $3+6+1+3+5+7=25$ . Rangs pairs : $7+0+2+4+6+8=27$ , pondérés par $3$ : $81$ . Total : $25+81=106$ .

b)

Il faut $106+d_{13}\equiv 0\ [10]$ , soit $d_{13}\equiv -6\equiv 4\ [10]$ . La clé vaut $4$ et le code complet est $3760123456784$ .

c)

$S$ varie de $3(b-a)$ . Pour que l'erreur passe inaperçue, il faudrait $3(b-a)\equiv 0\ [10]$ . Comme $3$ et $10$ sont premiers entre eux, le théorème de Gauss impose que $10$ divise $b-a$ , impossible pour deux chiffres distincts. L'erreur est toujours DÉTECTÉE ; au rang impair, la variation $b-a$ n'est pas non plus multiple de $10$ .

d)

Si $a$ est au rang impair et $b$ au rang pair, $S$ passe de $a+3b$ à $b+3a$ : la variation vaut $2(a-b)$ . Elle est multiple de $10$ lorsque $a-b$ est multiple de $5$ , soit $|a-b|=5$ : l'inversion de $1$ et $6$ , ou de $2$ et $7$ , n'est PAS détectée. Aucune clé à poids $1$ et $3$ ne détecte toutes les inversions.

e)

Rangs impairs : $3+6+1+3+5+8+4=30$ ; rangs pairs : $7+0+2+4+6+7=26$ , soit $78$ . $S=108\equiv 8\ [10]$ , non nul : le code est REFUSÉ. Les chiffres $7$ et $8$ ont été inversés, et comme $|8-7|=1\neq 5$ , l'inversion a été détectée.

Exercice 13 : Carreler une pièce et synchroniser des phares

Une pièce rectangulaire mesure $3{,}36\ \mathrm{m}$ sur $2{,}40\ \mathrm{m}$ . On veut la couvrir exactement avec des carreaux carrés identiques, sans découpe, les plus grands possible.

Sur une côte, trois phares s'allument ensemble à minuit. Le premier clignote toutes les $18\ \mathrm{s}$ , le deuxième toutes les $30\ \mathrm{s}$ , le troisième toutes les $42\ \mathrm{s}$ .

La figure ci-dessous représente la pièce.

a) Justifiez que le côté du carreau, en centimètres, est $\mathrm{pgcd}(336\,;240)$ , et calculez-le par l'algorithme d'Euclide.
b) Combien de carreaux faut-il ?
c) Au bout de combien de secondes les deux premiers phares s'allument-ils à nouveau ensemble ?
d) Calculez $\mathrm{ppcm}(336\,;240)$ à l'aide de la relation entre PGCD et PPCM.
e) Au bout de combien de temps les trois phares s'allument-ils de nouveau ensemble ? Donnez la réponse en secondes puis en minutes.

Voir la correction

Réponses

a) $\mathrm{pgcd}(336\,;240)=48$ cm
b) $35$ carreaux
c) $\mathrm{ppcm}(18\,;30)=90$ s
d) $\mathrm{ppcm}(336\,;240)=1\,680$
e) $630$ s $=10{,}5$ min

a)

Le côté $c$ doit diviser $336$ et $240$ , pour qu'un nombre entier de carreaux tienne dans chaque dimension ; le plus grand tel $c$ est leur PGCD. Euclide : $336=1\times 240+96$ ; $240=2\times 96+48$ ; $96=2\times 48+0$ . Donc $c=48\ \mathrm{cm}$ .

b)

$\dfrac{336}{48}=7$ carreaux sur la longueur et $\dfrac{240}{48}=5$ sur la largeur, soit $7\times 5=35$ carreaux. On vérifie par les aires : $\dfrac{336\times 240}{48^{2}}=\dfrac{80\,640}{2\,304}=35$ ✓.

c)

Les instants d'allumage du premier sont les multiples de $18$ , ceux du deuxième les multiples de $30$ : ils coïncident au plus petit multiple commun, $\mathrm{ppcm}(18\,;30)$ . Avec $18=2\times 3^{2}$ et $30=2\times 3\times 5$ : $\mathrm{ppcm}=2\times 3^{2}\times 5=90\ \mathrm{s}$ . Ce n'est pas $18\times 30=540$ , qui est un multiple commun mais pas le plus petit.

d)

Pour deux entiers positifs, $\mathrm{pgcd}(a\,;b)\times\mathrm{ppcm}(a\,;b)=ab$ . Donc $\mathrm{ppcm}(336\,;240)=\dfrac{336\times 240}{48}=1\,680$ .

e)

$42=2\times 3\times 7$ , donc $\mathrm{ppcm}(18\,;30\,;42)=2\times 3^{2}\times 5\times 7=630\ \mathrm{s}$ , soit $10{,}5\ \mathrm{min}$ : les trois phares se retrouvent ensemble à $0$ h $10$ min $30$ s.

Exercice 14 : Le chiffrement affine

On numérote les lettres de $A=0$ à $Z=25$ . Le chiffrement affine de clé $(5\,;8)$ remplace la lettre de rang $x$ par la lettre de rang $y$ , reste de $5x+8$ modulo $26$ : $y\equiv 5x+8\ [26]$ .

Le tableau ci-dessous donne le rang de chaque lettre.

a) Chiffrez la lettre $M$ ( $x=12$ ).
b) Chiffrez la lettre $T$ ( $x=19$ ).
c) Trouvez l'inverse de $5$ modulo $26$ , c'est-à-dire l'entier $u$ de $\{0\,;\ldots\,;25\}$ tel que $5u\equiv 1\ [26]$ .
d) Montrez que le déchiffrement s'écrit $x\equiv u(y-8)\ [26]$ . Déchiffrez la lettre $K$ ( $y=10$ ).
e) Pourquoi la clé $(4\,;8)$ serait-elle inutilisable ? Combien de valeurs de $a$ entre $1$ et $25$ donnent une clé utilisable ?

Voir la correction

Réponses

a) $Q$
b) $Z$
c) $u=21$
d) $x\equiv 21(y-8)$ ; $K$ donne $Q$
e) $\mathrm{pgcd}(4\,;26)=2$ ; $12$ clés utilisables

a)

$5\times 12+8=68=2\times 26+16$ : $y=16$ , la lettre $Q$ .

b)

$5\times 19+8=103=3\times 26+25$ : $y=25$ , la lettre $Z$ .

c)

On cherche $5u=1+26k$ . Avec l'algorithme d'Euclide : $26=5\times 5+1$ , donc $1=26-5\times 5$ et $5\times(-5)\equiv 1\ [26]$ . Le représentant dans $\{0\,;\ldots\,;25\}$ est $-5+26=21$ . Vérification : $5\times 21=105=4\times 26+1$ ✓.

d)

De $y\equiv 5x+8$ on tire $y-8\equiv 5x$ , puis en multipliant par $21$ : $21(y-8)\equiv 105x\equiv x\ [26]$ . Pour $y=10$ : $21\times 2=42=26+16$ , donc $x=16$ , la lettre $Q$ . Contrôle sur a) : $21\times(16-8)=168=6\times 26+12$ redonne bien $M$ ✓.

e)

Avec $a=4$ : $A$ ( $x=0$ ) donne $8$ , et $N$ ( $x=13$ ) donne $4\times 13+8=60\equiv 8\ [26]$ . Deux lettres ont le même chiffré, on ne peut pas déchiffrer. La cause est que $\mathrm{pgcd}(4\,;26)=2$ : $4$ n'a pas d'inverse modulo $26$ . Les valeurs utilisables de $a$ sont celles premières avec $26=2\times 13$ , les impairs différents de $13$ : $1,3,5,7,9,11,15,17,19,21,23,25$ , soit $12$ valeurs.

Exercice 15 : Le trésor des pirates : un système de congruences

Des pirates se partagent un nombre $N$ de pièces d'or. Répartis par groupes de $3$ , il en reste $2$ ; par groupes de $5$ , il en reste $3$ ; par groupes de $7$ , il en reste $2$ .

On cherche donc les entiers $N$ tels que $N\equiv 2\ [3]$ , $N\equiv 3\ [5]$ et $N\equiv 2\ [7]$ .

a) Montrez que les deux conditions $N\equiv 2\ [3]$ et $N\equiv 2\ [7]$ équivalent à $N\equiv 2\ [21]$ .
b) En écrivant $N=2+21k$ , traduisez la condition modulo $5$ en une congruence sur $k$ , et résolvez-la.
c) Déduisez-en l'ensemble des solutions et le plus petit nombre de pièces possible.
d) Le butin compte entre $1\,000$ et $1\,100$ pièces. Combien y en a-t-il ?
e) Pourquoi les solutions sont-elles espacées de $105$ exactement ?

Voir la correction

Réponses

a) $21\mid N-2$ par Gauss
b) $k\equiv 1\ [5]$
c) $N=23+105m$ ; minimum $23$
d) $1\,073$ pièces
e) $3\times 5\times 7=105$

a)

$N-2$ est divisible par $3$ et par $7$ . Comme $3$ et $7$ sont premiers entre eux, $N-2$ est divisible par leur produit : si $N-2=3m$ et $7\mid 3m$ , Gauss donne $7\mid m$ , donc $21\mid N-2$ . Réciproquement, un multiple de $21$ est multiple de $3$ et de $7$ . D'où $N\equiv 2\ [21]$ .

b)

$2+21k\equiv 3\ [5]$ , et $21\equiv 1\ [5]$ , donc $2+k\equiv 3$ et $k\equiv 1\ [5]$ : $k=1+5m$ .

c)

$N=2+21(1+5m)=23+105m$ , $m$ entier. Le plus petit nombre positif est $N=23$ . Vérification : $23=3\times 7+2$ , $23=5\times 4+3$ , $23=7\times 3+2$ ✓.

d)

$23+105m\in[1\,000\,;1\,100]$ donne $m\geq 9{,}3$ et $m\leq 10{,}2$ , donc $m=10$ et $N=1\,073$ . Contrôle : $1\,073=3\times 357+2=5\times 214+3=7\times 153+2$ ✓.

e)

Deux solutions ont la même différence avec $2$ modulo $3$ et $7$ , et avec $3$ modulo $5$ : leur écart est multiple de $3$ , de $5$ et de $7$ , premiers entre eux deux à deux, donc de $3\times 5\times 7=105$ . Réciproquement, ajouter $105$ ne change aucun des trois restes. C'est le théorème chinois des restes.

Exercice 16 : Il existe une infinité de nombres premiers : la démonstration d'Euclide

Cet exercice démontre l'un des plus anciens théorèmes des mathématiques, déjà dans les Éléments d'Euclide, puis examine ce que la démonstration dit, et surtout ce qu'elle ne dit pas.

a) Soit $n\geq 2$ un entier. On note $p$ le plus petit diviseur de $n$ strictement supérieur à $1$ . Démontrez que $p$ est premier. Quel est le plus petit diviseur strictement supérieur à $1$ de $91$ ?
b) On suppose qu'il n'existe qu'un nombre fini de nombres premiers $p_{1}$ , $p_{2}$ , ..., $p_{k}$ , et l'on pose $N=p_{1}p_{2}\cdots p_{k}+1$ . Démontrez qu'aucun $p_{i}$ ne divise $N$ : quel est le reste de la division de $N$ par $p_{i}$ ? Concluez.
c) On forme les nombres $N$ de la question b) avec les premiers nombres premiers : $2\times 3\times 5\times 7+1$ , puis $2\times 3\times 5\times 7\times 11\times 13+1$ . Calculez-les.
d) Le second vaut $30\,031$ . Est-il premier ? Déterminez son plus petit diviseur premier, et dites ce que cela change à la démonstration.
e) Les nombres premiers sont en nombre infini, mais ils peuvent être très espacés. Démontrez que les cinq entiers $6!+2$ , $6!+3$ , $6!+4$ , $6!+5$ , $6!+6$ sont tous composés, et donnez le plus petit diviseur strictement supérieur à $1$ de $6!+5$ .

Voir la correction

Réponses

a) Le plus petit diviseur supérieur à $1$ est premier ; pour $91$ , c'est $7$
b) Reste $1$ : un diviseur premier de $N$ est hors de la liste, contradiction
c) $211$ et $30\,031$
d) Non : $30\,031=59\times 509$ ; $59$ est un premier nouveau, la preuve tient
e) $k$ divise $6!+k$ ; $725=5^{2}\times 29$ , plus petit diviseur $5$

a)

L'ensemble des diviseurs de $n$ strictement supérieurs à $1$ contient $n$ lui-même : il est non vide et admet donc un plus petit élément $p$ . Supposons $p$ non premier : il aurait un diviseur $q$ avec $1<q<p$ . Alors $q$ divise $p$ , qui divise $n$ , donc $q$ divise $n$ ; c'est un diviseur de $n$ plus petit que $p$ et supérieur à $1$ , ce qui contredit la définition de $p$ . Donc $p$ est premier : tout entier $n\geq 2$ admet un diviseur premier. Pour $91$ : ni $2$ , ni $3$ , ni $5$ ne le divisent, et $91=7\times 13$ ; le plus petit diviseur est $7$ , qui est bien premier.

b)

Pour chaque $i$ , $N=p_{i}\times\left(\text{produit des autres}\right)+1$ avec $0\leq 1<p_{i}$ : c'est une division euclidienne, et le reste vaut $1$ . Donc aucun $p_{i}$ ne divise $N$ . Or $N\geq 2$ , donc par a) $N$ admet un diviseur premier $q$ . Ce $q$ est différent de tous les $p_{i}$ : c'est un nombre premier qui n'est pas dans la liste, alors que la liste était supposée les contenir tous. La supposition est absurde : l'ensemble des nombres premiers est infini. C'est un raisonnement par l'absurde, et sa rédaction doit le dire en toutes lettres.

c)

$2\times 3\times 5\times 7+1=210+1=211$ , et $2\times 3\times 5\times 7\times 11\times 13+1=30\,030+1=30\,031$ . Le premier, $211$ , est premier : on le vérifie en testant les nombres premiers jusqu'à $\sqrt{211}\approx 14{,}5$ , soit $2$ , $3$ , $5$ , $7$ , $11$ et $13$ , dont aucun ne le divise.

d)

$30\,031$ n'est PAS premier : $30\,031=59\times 509$ , et $59$ est son plus petit diviseur premier. La démonstration n'a jamais prétendu que $N$ était premier, seulement qu'il avait un diviseur premier hors de la liste. Ici ce diviseur est $59$ , qui n'est pas parmi $2$ , $3$ , $5$ , $7$ , $11$ et $13$ : le raisonnement fonctionne parfaitement. Écrire « $N$ est premier » est l'erreur classique de cette démonstration, et $30\,031$ en est le contre-exemple.

e)

$6!=720$ . Pour $k$ entre $2$ et $6$ , $k$ divise $6!=1\times 2\times\cdots\times 6$ , donc $k$ divise $6!+k$ ; et $6!+k>k$ , donc $6!+k$ a un diviseur strictement compris entre $1$ et lui-même : il est composé. Les cinq entiers consécutifs $722$ à $726$ sont composés. Pour $6!+5=725$ : il n'est divisible ni par $2$ ni par $3$ ( $7+2+5=14$ ), et il se termine par $5$ , donc son plus petit diviseur supérieur à $1$ est $5$ ; $725=5\times 145=5^{2}\times 29$ . En remplaçant $6$ par $n$ , on obtient $n-1$ composés consécutifs : aussi long que l'on veut.

À retenir : la démonstration d'Euclide construit un nombre dont un diviseur premier est nouveau ; elle n'affirme jamais que ce nombre est lui-même premier.

Exercice 17 : Le PGCD s'écrit ax + by : démonstration du théorème de Bézout

Soit $a$ et $b$ deux entiers naturels non tous deux nuls. On note $E$ l'ensemble des entiers STRICTEMENT POSITIFS qui s'écrivent $ax+by$ avec $x$ et $y$ entiers relatifs. On illustre chaque étape avec $a=84$ et $b=60$ .

a) Justifiez que $E$ est non vide et admet un plus petit élément $d$ , que l'on écrit $d=au+bv$ . Pour $a=84$ et $b=60$ , calculez $84\times(-2)+60\times 3$ .
b) En effectuant la division euclidienne de $a$ par $d$ , $a=dq+r$ avec $0\leq r<d$ , démontrez que $r=0$ , c'est-à-dire que $d$ divise $a$ . On admet de même que $d$ divise $b$ .
c) Démontrez que tout diviseur commun de $a$ et $b$ divise $d$ , puis que $d=\mathrm{pgcd}(a\,;b)$ . Donnez $\mathrm{pgcd}(84\,;60)$ .
d) Déduisez-en le théorème de Bézout : $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que $au+bv=1$ . L'entier $30$ appartient-il à $E$ pour $a=84$ et $b=60$ ?
e) On pose $a'=\frac{84}{12}$ et $b'=\frac{60}{12}$ . À partir du couple de la question a), trouvez un couple de Bézout de $a'$ et $b'$ , et calculez $7\times(-2)+5\times 3$ . Que peut-on en conclure ?

Voir la correction

Réponses

a) $E$ non vide, plus petit élément $d=au+bv$ ; $84\times(-2)+60\times 3=12$
b) $r=a(1-uq)+b(-vq)$ , et $0<r<d$ contredirait la minimalité : $r=0$
c) Tout diviseur commun divise $d$ , donc $d=\mathrm{pgcd}$ ; $\mathrm{pgcd}(84\,;60)=12$
d) $d=1$ si et seulement si $au+bv=1$ ; $30\notin E$
e) $7\times(-2)+5\times 3=1$ : $7$ et $5$ premiers entre eux

a)

$E$ est non vide : si $a\neq 0$ , alors $a=a\times 1+b\times 0>0$ est dans $E$ ; sinon $b>0$ y est. Toute partie non vide de $\mathbb{N}$ admet un plus petit élément : c'est $d$ , et comme $d\in E$ , il existe des entiers $u$ et $v$ tels que $d=au+bv$ . Sur l'exemple, $84\times(-2)+60\times 3=-168+180=12$ , donc $12\in E$ . On verra que c'est exactement le plus petit élément. Le geste clé de toute la démonstration est là : on ne construit pas $u$ et $v$ , on prend le PLUS PETIT élément d'un ensemble dont on sait seulement qu'il n'est pas vide.

b)

$r=a-dq=a-(au+bv)q=a(1-uq)+b(-vq)$ : $r$ s'écrit $ax+by$ avec $x=1-uq$ et $y=-vq$ entiers. Si l'on avait $r>0$ , $r$ serait dans $E$ et strictement inférieur à $d$ , ce qui contredit la minimalité de $d$ . Donc $r=0$ et $d$ divise $a$ . Le même raisonnement, avec la division de $b$ par $d$ , montre que $d$ divise $b$ . C'est la division euclidienne qui fournit un candidat plus petit, et la minimalité qui l'élimine.

c)

Si $k$ divise $a$ et $b$ , il divise toute combinaison $au+bv$ , donc il divise $d$ . En particulier $k\leq d$ pour tout diviseur commun positif $k$ ; comme $d$ est lui-même un diviseur commun par b), $d$ est le PLUS GRAND diviseur commun : $d=\mathrm{pgcd}(a\,;b)$ . Pour l'exemple, $84=2^{2}\times 3\times 7$ et $60=2^{2}\times 3\times 5$ , donc $\mathrm{pgcd}(84\,;60)=12$ , ce qui confirme que $12$ , trouvé en a), est bien le plus petit élément de $E$ .

d)

Si $a$ et $b$ sont premiers entre eux, $d=1$ et $1=au+bv$ . Réciproquement, si $au+bv=1$ , tout diviseur commun positif de $a$ et $b$ divise $1$ , donc vaut $1$ : $a$ et $b$ sont premiers entre eux. De plus, c) montre que $E$ ne contient que des multiples de $d$ : $ax+by$ est toujours divisible par $d$ . Pour $84$ et $60$ , $30$ n'est pas un multiple de $12$ , donc $30\notin E$ : aucune combinaison $84x+60y$ ne vaut $30$ . À l'inverse, $36=3\times 12$ s'écrit $84\times(-6)+60\times 9$ .

e)

$a'=7$ et $b'=5$ . On divise l'égalité $84\times(-2)+60\times 3=12$ par $12$ : $7\times(-2)+5\times 3=-14+15=1$ . Par le théorème de Bézout, $7$ et $5$ sont premiers entre eux. Le résultat est général : en divisant $au+bv=d$ par $d$ , on obtient $\frac{a}{d}u+\frac{b}{d}v=1$ , donc $\frac{a}{d}$ et $\frac{b}{d}$ sont TOUJOURS premiers entre eux. C'est la propriété qu'on utilise pour résoudre une équation diophantienne après avoir divisé par le PGCD.

À retenir : le PGCD est le plus petit entier strictement positif qui s'écrit $ax+by$ ; Bézout en est le cas $d=1$ , et c'est la seule valeur qui caractérise.

Exercice 18 : Le théorème de Gauss : démonstration et quatre conséquences

Théorème de Gauss : si un entier $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$ . On le démontre à l'aide du théorème de Bézout (exercice 17), puis on s'en sert.

a) Démontrez le théorème de Gauss. Quelle égalité, fournie par Bézout, faut-il multiplier par $c$ ?
b) Démontrez que si $a$ et $b$ sont premiers entre eux et divisent tous deux $n$ , alors $ab$ divise $n$ . Avec $a=4$ et $b=6$ , qui ne sont pas premiers entre eux, donnez le plus petit entier $n>0$ divisible par $4$ et par $6$ , et constatez que $24$ ne le divise pas.
c) Démontrez que si un nombre premier $p$ divise un produit $bc$ , alors $p$ divise $b$ ou $p$ divise $c$ .
d) On suppose $\sqrt{2}=\frac{p}{q}$ avec $p$ et $q$ entiers strictement positifs premiers entre eux. Montrez que $2$ divise $p$ , puis que $2$ divise $q$ . Concluez.
e) Déterminez tous les entiers $x$ de l'intervalle $[0\,;100]$ tels que $12x\equiv 0\ [45]$ . Combien y en a-t-il ?

Voir la correction

Réponses

a) $au+bv=1$ donne $c=acu+bcv$ , somme de deux multiples de $a$
b) $n=ak$ , Gauss donne $b\mid k$ , donc $ab\mid n$ ; pour $4$ et $6$ : $12$ , que $24$ ne divise pas
c) $\mathrm{pgcd}(p\,;b)=1$ puis Gauss : lemme d'Euclide
d) $2\mid p$ puis $2\mid q$ : contradiction, $\sqrt{2}$ irrationnel
e) $15\mid x$ : $0$ , $15$ , $30$ , $45$ , $60$ , $75$ , $90$ , soit $7$ solutions

a)

Comme $a$ et $b$ sont premiers entre eux, Bézout fournit des entiers $u$ et $v$ tels que $au+bv=1$ . On multiplie par $c$ : $acu+bcv=c$ . Or $a$ divise $acu$ , évidemment, et $a$ divise $bcv$ puisqu'il divise $bc$ . Donc $a$ divise la somme, qui vaut $c$ . La démonstration tient en trois lignes, mais chacune porte une hypothèse : la première utilise « premiers entre eux », la dernière « $a$ divise $bc$ ». Sans la première, il n'y a pas de couple $(u\,;v)$ donnant $1$ , et le théorème tombe, comme le montre l'exercice 8 c).

b)

$a$ divise $n$ , donc $n=ak$ avec $k$ entier. $b$ divise $n=ak$ et $b$ est premier avec $a$ : par Gauss, $b$ divise $k$ , soit $k=bm$ . Alors $n=abm$ , et $ab$ divise $n$ . Contre-exemple sans l'hypothèse : les multiples communs de $4$ et $6$ sont les multiples de $12$ , le plus petit étant $12$ ; et $24=4\times6$ ne divise pas $12$ . C'est pour cela que « divisible par $4$ et par $6$ » ne veut pas dire « divisible par $24$ », alors que « divisible par $8$ et par $9$ » veut bien dire « divisible par $72$ ».

c)

Si $p$ divise $b$ , c'est fini. Sinon, les seuls diviseurs positifs de $p$ sont $1$ et $p$ , et $p$ ne divise pas $b$ , donc $\mathrm{pgcd}(p\,;b)=1$ : $p$ et $b$ sont premiers entre eux. Par Gauss, $p$ divise $c$ . C'est le lemme d'Euclide. Il est FAUX pour un diviseur non premier : $6$ divise $4\times 9$ sans diviser ni $4$ ni $9$ (exercice 9 b).

d)

$\sqrt{2}=\frac{p}{q}$ donne $p^{2}=2q^{2}$ . Donc $2$ divise $p^{2}=p\times p$ , et par c) avec $2$ premier, $2$ divise $p$ : $p=2p'$ . Alors $4p'^{2}=2q^{2}$ , soit $q^{2}=2p'^{2}$ : de même $2$ divise $q$ . Donc $2$ divise $p$ et $q$ , qui étaient supposés premiers entre eux : contradiction. Le nombre $\sqrt{2}$ n'est pas rationnel. La preuve n'utilise que le lemme d'Euclide, lui-même tiré de Gauss.

e)

$\mathrm{pgcd}(12\,;45)=3$ . $12x\equiv 0\ [45]$ signifie que $45$ divise $12x$ , soit $12x=45k$ , et en divisant par $3$ : $4x=15k$ , donc $15$ divise $4x$ . Or $\mathrm{pgcd}(15\,;4)=1$ : par Gauss, $15$ divise $x$ . Réciproquement, si $x=15m$ , alors $12x=180m=45\times 4m$ . Les solutions de $[0\,;100]$ sont $0$ , $15$ , $30$ , $45$ , $60$ , $75$ et $90$ : il y en a $7$ . L'erreur fréquente est d'appliquer Gauss directement à $45$ et $12$ , qui ne sont PAS premiers entre eux, et de conclure que $45$ divise $x$ , ce qui ne donne que $3$ solutions.

À retenir : Gauss se démontre par Bézout en multipliant $au+bv=1$ par $c$ ; avant de l'appliquer, on divise par le PGCD pour se ramener à deux nombres premiers entre eux.

Exercice 19 : Le crible d'Ératosthène en Python

Pour obtenir tous les nombres premiers inférieurs ou égaux à $n$ , le crible d'Ératosthène part de la liste des entiers de $2$ à $n$ et, pour chaque nombre premier $p$ rencontré, barre ses multiples. La fonction ci-dessous le programme : la liste est_premier dit, pour chaque entier $k$ de $0$ à $n$ , s'il n'a pas été barré.

def crible(n):
    est_premier = [True] * (n + 1)
    est_premier[0] = False
    est_premier[1] = False
    p = 2
    while p * p <= n:
        if est_premier[p]:
            for m in range(p * p, n + 1, p):
                est_premier[m] = False
        p = p + 1
    return [k for k in range(n + 1) if est_premier[k]]

a) On appelle crible(50). Pour quelles valeurs de $p$ la boucle for barre-t-elle des multiples ? Donnez la plus grande.
b) Pourquoi peut-on commencer à barrer à $p\times p$ plutôt qu'à $2p$ ?
c) Pourquoi peut-on arrêter la boucle while dès que $p\times p>n$ ? Démontrez que tout entier composé $m\leq n$ a un diviseur premier $q$ avec $q^{2}\leq m$ .
d) Combien d'éléments la liste renvoyée par crible(100) contient-elle ? Quel est le dernier élément de crible(50) ?
e) Pour crible(30), combien de fois l'instruction est_premier[m] = False est-elle exécutée ? Comparez au nombre d'entiers composés entre $2$ et $30$ et expliquez l'écart.

Voir la correction

Réponses

a) $p=2$ , $3$ , $5$ , $7$ ; la plus grande est $7$
b) $kp$ avec $k<p$ a un diviseur premier plus petit que $p$ , il est déjà barré
c) $m=rs$ , $r\leq s$ donne $r^{2}\leq m$ : un diviseur premier $q$ de $r$ vérifie $q^{2}\leq m$
d) $25$ éléments ; dernier élément de crible(50) : $47$
e) $24$ exécutions pour $19$ composés : $5$ passages en trop

a)

La boucle while tourne tant que $p^{2}\leq 50$ , donc pour $p$ de $2$ à $7$ ( $7^{2}=49\leq 50$ et $8^{2}=64>50$ ). Elle ne barre que si est_premier[p] vaut encore True, c'est-à-dire si $p$ n'a pas été barré : c'est le cas de $2$ , $3$ , $5$ et $7$ , pas de $4$ ni de $6$ , déjà barrés comme multiples de $2$ . La plus grande valeur qui barre est donc $7$ . Le test sur est_premier[p] fait que seuls les nombres PREMIERS barrent : un entier non barré au moment où on l'atteint n'a aucun diviseur premier plus petit que lui, il est donc premier.

b)

Un multiple $kp$ avec $2\leq k<p$ a un facteur $k$ plus petit que $p$ , donc un diviseur premier $q\leq k<p$ : il a déjà été barré lors du passage de $q$ . Par exemple, pour $p=7$ , les multiples $14$ , $21$ , $28$ , $35$ et $42$ ont été barrés par $2$ , $3$ ou $5$ ; le premier multiple de $7$ encore à barrer est $49=7\times 7$ . Commencer à $p^{2}$ ne change pas le résultat, cela évite du travail inutile.

c)

Soit $m$ composé : $m=rs$ avec $2\leq r\leq s$ . Alors $r^{2}\leq rs=m$ , et un diviseur premier $q$ de $r$ vérifie $q\leq r$ , donc $q^{2}\leq m\leq n$ . Ainsi tout composé $m\leq n$ est un multiple d'un premier $q$ avec $q^{2}\leq n$ , et il a été barré lors du passage de $q$ . Une fois $p^{2}>n$ , il ne reste aucun composé à barrer : tout ce qui n'est pas barré est premier. C'est le même argument que celui qui limite un test de primalité à la racine carrée.

d)

crible(100) renvoie les nombres premiers inférieurs ou égaux à $100$ : $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ , $31$ , $37$ , $41$ , $43$ , $47$ , $53$ , $59$ , $61$ , $67$ , $71$ , $73$ , $79$ , $83$ , $89$ , $97$ , soit $25$ nombres. Le dernier élément de crible(50) est $47$ , puisque $48$ , $49$ et $50$ sont barrés.

e)

Pour $n=30$ , la boucle barre pour $p=2$ (de $4$ à $30$ de $2$ en $2$ : $14$ fois), $p=3$ (de $9$ à $30$ de $3$ en $3$ : $8$ fois) et $p=5$ ( $25$ et $30$ : $2$ fois) ; $p=4$ ne barre pas et $6^{2}>30$ arrête la boucle. Total : $14+8+2=24$ exécutions. Or il n'y a que $19$ composés entre $2$ et $30$ ( $29$ entiers dont $10$ premiers). L'écart de $5$ vient des nombres barrés plusieurs fois : $12$ , $18$ et $24$ par $2$ et par $3$ , et $30$ par $2$ , $3$ et $5$ , soit $3\times 1+2=5$ passages en trop. Barrer deux fois ne fausse rien ; cela coûte seulement du temps.

À retenir : le crible barre les multiples des seuls nombres premiers, de $p^{2}$ jusqu'à $n$ , et s'arrête quand $p^{2}>n$ ; ce qui reste est exactement l'ensemble des nombres premiers.

Exercice 20 : La décomposition en facteurs premiers en Python

Tout entier $n\geq 2$ s'écrit de façon unique, à l'ordre près, comme produit de nombres premiers. La fonction ci-dessous calcule cette décomposition : elle essaie les diviseurs $d=2$ , $3$ , $4$ ... et divise $n$ par $d$ tant que c'est possible.

def decompose(n):
    facteurs = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            facteurs.append(d)
            n = n // d
        d = d + 1
    if n > 1:
        facteurs.append(n)
    return facteurs

a) Faites tourner decompose(1386) à la main. Combien d'éléments la liste renvoyée contient-elle, et quel est le dernier ?
b) La variable $d$ prend aussi des valeurs non premières, comme $4$ ou $6$ . Pourquoi ne peuvent-elles jamais être ajoutées à la liste ?
c) À quoi sert le test final if n > 1 ? Que renvoie decompose(94) ?
d) Pour $n=997$ , qui est premier, combien de valeurs de $d$ la boucle while teste-t-elle ?
e) En utilisant l'unicité de la décomposition, montrez que $12^{k}\neq 18^{j}$ pour tous entiers $k\geq 1$ et $j\geq 1$ .

Voir la correction

Réponses

a) $[2, 3, 3, 7, 11]$ : $5$ éléments, le dernier est $11$
b) Quand $d$ arrive, les facteurs premiers plus petits ont été retirés : $d$ ajouté est premier
c) Le reste $n>1$ est premier ; decompose(94) renvoie $[2, 47]$
d) $d$ de $2$ à $31$ : $30$ valeurs
e) $2^{2k}3^{k}=2^{j}3^{2j}$ imposerait $2k=j$ et $k=2j$ , donc $k=0$ : impossible

a)

$d=2$ : $1386=2\times 693$ , on ajoute $2$ et $n$ devient $693$ , impair. $d=3$ : $693=3\times 231$ puis $231=3\times 77$ , on ajoute deux fois $3$ et $n$ devient $77$ . $d=4$ , $5$ , $6$ : aucun ne divise $77$ . $d=7$ : $77=7\times 11$ , on ajoute $7$ et $n$ devient $11$ . Puis $d=8$ et $8\times 8=64>11$ : la boucle s'arrête. Comme $n=11>1$ , on ajoute $11$ . La liste est $[2, 3, 3, 7, 11]$ : $5$ éléments, le dernier est $11$ , et $1\,386=2\times 3^{2}\times 7\times 11$ .

b)

Quand $d$ atteint $4$ , tous les facteurs $2$ ont déjà été retirés de $n$ par la boucle intérieure lorsque $d$ valait $2$ : $n$ n'est plus pair, donc $4$ ne le divise pas. Plus généralement, quand $d$ arrive, $n$ n'a plus aucun diviseur premier strictement inférieur à $d$ ; si $d$ divisait $n$ , un diviseur premier de $d$ , plus petit que $d$ , diviserait $n$ , ce qui est impossible. Donc tout $d$ ajouté est premier. C'est la même idée que dans le crible : on ne teste que ce qui reste.

c)

La boucle s'arrête quand $d^{2}>n$ . Si à ce moment $n>1$ , ce $n$ n'a aucun diviseur premier $q$ avec $q^{2}\leq n$ : par l'argument de l'exercice 19 c), il est premier, et c'est le dernier facteur. Sans ce test, le plus grand facteur premier serait perdu. Pour $94$ : $d=2$ donne $94=2\times 47$ , $n$ devient $47$ ; puis $d$ va de $3$ à $6$ sans diviser, et $7^{2}=49>47$ arrête la boucle. On ajoute $47$ : decompose(94) renvoie $[2, 47]$ .

d)

Aucun $d$ ne divise $997$ , donc $n$ reste égal à $997$ et la boucle tourne tant que $d^{2}\leq 997$ . Or $31^{2}=961\leq 997$ et $32^{2}=1\,024>997$ : $d$ prend les valeurs $2$ à $31$ , soit $30$ valeurs. Le test final ajoute $997$ . Le coût est de l'ordre de $\sqrt{n}$ essais : pour un nombre de dix chiffres, environ cent mille, ce qui reste rapide, mais pour un nombre de trois cents chiffres, c'est hors de portée, et c'est sur cette difficulté que repose le chiffrement RSA.

e)

$12=2^{2}\times 3$ et $18=2\times 3^{2}$ , donc $12^{k}=2^{2k}\times 3^{k}$ et $18^{j}=2^{j}\times3^{2j}$ . Si ces deux nombres étaient égaux, l'unicité de la décomposition imposerait les mêmes exposants : $2k=j$ et $k=2j$ . Alors $k=2j=4k$ , donc $k=0$ , ce qui contredit $k\geq 1$ . Ainsi $12^{k}\neq 18^{j}$ . L'algorithme calcule UNE décomposition ; c'est le théorème d'unicité, démontré grâce au lemme d'Euclide (exercice 18 c), qui garantit qu'il n'y en a pas d'autre.

À retenir : on divise par $d$ tant que c'est possible avant de passer à $d+1$ , on s'arrête quand $d^{2}>n$ , et le reste, s'il dépasse $1$ , est premier.

Exercices corrigés : l'arithmétique (maths expertes)

Rappel de cours

Calculs : les restes à calculer

Exercice 0.1 : Calculer des restes avec les congruences : dix calculs directs

Calculs : PGCD et Bézout à calculer

Exercice 0.2 : Calculer un PGCD et des coefficients de Bézout : neuf calculs directs

Partie A : Les bases (/50)

Exercice 1 : Division euclidienne et divisibilité

Exercice 2 : Algorithme d'Euclide

Exercice 3 : Congruences

Exercice 4 : Critères de divisibilité par les congruences

Exercice 5 : Nombres premiers

Partie B : Niveau baccalauréat (/50)

Exercice 6 : Coefficients de Bézout

Exercice 7 : Équation diophantienne

Exercice 8 : Théorème de Gauss

Exercice 9 : Quatre implications fausses

Exercice 10 : Petit théorème de Fermat

Partie C : les classiques (/50)

Exercice 11 : Des équations impossibles, prouvées par les congruences

Exercice 12 : La clé de contrôle d'un code-barres

Exercice 13 : Carreler une pièce et synchroniser des phares

Exercice 14 : Le chiffrement affine

Exercice 15 : Le trésor des pirates : un système de congruences

Partie D : démonstrations et algorithmes du programme (/50)

Exercice 16 : Il existe une infinité de nombres premiers : la démonstration d'Euclide

Exercice 17 : Le PGCD s'écrit ax + by : démonstration du théorème de Bézout

Exercice 18 : Le théorème de Gauss : démonstration et quatre conséquences

Exercice 19 : Le crible d'Ératosthène en Python

Exercice 20 : La décomposition en facteurs premiers en Python

Voir aussi

Vous cherchez un tuteur de maths expertes à Montréal ?