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

a) $2024=7\times 289+1$, avec $0\leq 1<7$. Le quotient est 289 et le reste 1.

b) On cherche $q$ tel que le reste soit dans $[0;5[$. Avec $q=-4$ : $5\times(-4)=-20$ et $-17-(-20)=3$. Donc $-17=5\times(-4)+3$, quotient $-4$ et reste 3. L'erreur classique serait d'écrire $-17=5\times(-3)-2$, mais $-2$ n'est pas un reste valable.

c) $36=2^{2}\times 3^{2}$, donc ses diviseurs positifs sont $1$, $2$, $3$, $4$, $6$, $9$, $12$, $18$ et $36$. Il y en a $(2+1)\times(2+1)=9$.

d) Parmi deux entiers consécutifs, l'un est nécessairement pair. Plus précisément, si $n$ est pair alors $n(n+1)$ l'est ; si $n$ est impair alors $n+1$ est pair et le produit l'est aussi. Dans tous les cas $n(n+1)$ est divisible par 2.

a) $1071=2\times 462+147$ ; $462=3\times 147+21$ ; $147=7\times 21+0$. Le dernier reste non nul est 21, donc $\mathrm{pgcd}(1071,\ 462)=21$.

b) $240=1\times 156+84$ ; $156=1\times 84+72$ ; $84=1\times 72+12$ ; $72=6\times 12+0$. Donc $\mathrm{pgcd}(240,\ 156)=12$.

c) $240=2^{4}\times 3\times 5$ et $156=2^{2}\times 3\times 13$. On garde les facteurs communs avec le plus petit exposant : $2^{2}\times 3=12$. On retrouve bien le même résultat.

d) $35=5\times 7$ et $64=2^{6}$ : ils n'ont aucun facteur premier commun, donc $\mathrm{pgcd}(35,\ 64)=1$. Ils sont premiers entre eux, bien qu'aucun des deux ne soit un nombre premier.

a) D'après l'exercice 1, $2024=7\times 289+1$, donc $2024\equiv 1\ [7]$ et le reste vaut 1.

b) On calcule les puissances successives 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$. Le cycle a pour longueur 6. Or $100=6\times 16+4$, donc $3^{100}\equiv 3^{4}\equiv 4\ [7]$. Le reste vaut 4.

c) Le chiffre des unités est le reste modulo 10. Les puissances de 7 modulo 10 sont $7$, $9$, $3$, $1$, puis le cycle recommence : sa longueur est 4. Or $2024=4\times 506$, donc $7^{2024}\equiv 7^{4}\equiv 1\ [10]$. Le chiffre des unités est 1.

d) On teste les restes possibles : $3\times 5=15=14+1\equiv 1\ [7]$. Donc $x\equiv 5\ [7]$, c'est-à-dire $x\in\{\ldots,\ -2,\ 5,\ 12,\ 19,\ \ldots\}$.

a) $10-1=9$ est divisible par 9, donc $10\equiv 1\ [9]$. En élevant à la puissance $k$, la compatibilité des congruences avec le produit donne $10^{k}\equiv 1^{k}=1\ [9]$.

b) Un entier s'écrit $N=\sum a_{k}10^{k}$ où les $a_{k}$ sont ses chiffres. Comme $10^{k}\equiv 1\ [9]$, on obtient $N\equiv\sum a_{k}\ [9]$ : $N$ est congru à la somme de ses chiffres modulo 9. En particulier, $N$ est divisible par 9 si et seulement si cette somme l'est.

c) La somme des chiffres vaut $5+8+2+3=18$, qui est divisible par 9. Donc 5823 l'est aussi, et en effet $5823=9\times 647$.

d) $10+1=11$ est divisible par 11, donc $10\equiv-1\ [11]$, puis $10^{k}\equiv(-1)^{k}\ [11]$. Un entier est donc congru modulo 11 à la somme alternée de ses chiffres, en partant du chiffre des unités avec un signe plus.

e) La somme alternée vaut $3-2+8-5=4$, qui n'est pas divisible par 11. Donc 5823 ne l'est pas non plus : la division donne $5823=11\times 529+4$, et on retrouve bien le reste 4.

a) $360=36\times 10=2^{2}\times 3^{2}\times 2\times 5=2^{3}\times 3^{2}\times 5$.

b) $2024=2\times 1012=2^{2}\times 506=2^{3}\times 253$. Ensuite $253=11\times 23$, deux nombres premiers. Donc $2024=2^{3}\times 11\times 23$.

c) Le nombre de diviseurs s'obtient en ajoutant 1 à chaque exposant et en multipliant : $(3+1)\times(2+1)\times(1+1)=4\times 3\times 2=24$ diviseurs positifs.

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.

e) Il suffit de chercher jusqu'à $\sqrt{n}$. En effet, 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 pas $\sqrt{n}$. Pour 221, il suffisait donc d'aller jusqu'à 14, puisque $14^{2}=196<221<225=15^{2}$.

a) 17 est premier et ne divise pas 5, donc leur seul diviseur commun positif est 1 : ils sont premiers entre eux.

b) $17=3\times 5+2$, puis $5=2\times 2+1$. Le reste suivant serait nul, et le dernier reste non nul vaut bien 1.

c) On part de la dernière égalité : $1=5-2\times 2$. Or la première donne $2=17-3\times 5$. En substituant : $1=5-2(17-3\times 5)=5-2\times 17+6\times 5=7\times 5-2\times 17$. Donc $u=-2$ et $v=7$.

d) $17\times(-2)+5\times 7=-34+35=1$. Le couple convient.

e) Non, il 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.

a) $\mathrm{pgcd}(17,\ 5)=1$, et 1 divise 3. L'équation admet donc des solutions entières.

b) De $17\times(-2)+5\times 7=1$, 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) Soit $(x,\ y)$ une solution quelconque. En soustrayant, $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 $x+6=5k$, d'où $x=-6+5k$ et, en reportant, $y=21-17k$. Réciproquement ces couples conviennent. L'ensemble des solutions est $\{(-6+5k,\ 21-17k),\ k\in\mathbb{Z}\}$.

d) Pour $k=1$ : $(-1,\ 4)$ et $17\times(-1)+5\times 4=-17+20=3$. Pour $k=2$ : $(4,\ -13)$ et $68-65=3$. Les deux conviennent.

e) Il faut $-6+5k\geq 0$, soit $k\geq 1{,}2$ donc $k\geq 2$, et $21-17k\geq 0$, soit $k\leq 1{,}23$ donc $k\leq 1$. Ces deux conditions sont incompatibles : il n'existe aucune solution à coordonnées toutes deux positives.

a) 7 divise le produit $5\times n$, et $\mathrm{pgcd}(7,\ 5)=1$ puisque 7 est premier et ne divise pas 5. Le théorème de Gauss s'applique : 7 divise $n$.

b) $5x\equiv 0\ [7]$ signifie 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. L'ensemble des solutions est donc l'ensemble des multiples de 7.

c) Non. Contre-exemple : $n=3$. Alors $4n=12$, qui est bien divisible par 6, alors que 6 ne divise pas 3.

d) Il manque la coprimalité : $\mathrm{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.

e) On peut simplifier par le PGCD. De $6\mid 4n$ on tire, en divisant par 2, que $3$ divise $2n$. Or $\mathrm{pgcd}(3,\ 2)=1$, donc cette fois Gauss s'applique : 3 divise $n$. On vérifie sur le contre-exemple : $n=3$ est bien divisible par 3.

a) 11 est premier et ne divise pas 2, donc $2^{10}\equiv 1\ [11]$. Comme $100=10\times 10$, on obtient $2^{100}=(2^{10})^{10}\equiv 1^{10}=1\ [11]$. Le reste vaut 1.

b) 13 est premier et ne divise pas 3, donc $3^{12}\equiv 1\ [13]$. On divise l'exposant par 12 : $2024=12\times 168+8$. Donc $3^{2024}\equiv 3^{8}\ [13]$. Or $3^{2}=9$, $3^{4}\equiv 81\equiv 3$, puis $3^{8}\equiv 3^{2}=9\ [13]$. Le reste vaut 9.

c) De même $7^{12}\equiv 1\ [13]$ et $2024=12\times 168+8$, donc $7^{2024}\equiv 7^{8}\ [13]$. On calcule : $7^{2}=49\equiv 10$, $7^{4}\equiv 100\equiv 9$, $7^{8}\equiv 81\equiv 3\ [13]$. Le reste vaut 3.

d) $3^{3}=27=2\times 13+1$, donc $3^{3}\equiv 1\ [13]$ : l'ordre de 3 modulo 13 vaut 3, ce qui est bien un diviseur de 12. On écrit alors $2024=3\times 674+2$, d'où $3^{2024}\equiv 3^{2}=9\ [13]$. On retrouve le même reste, avec un calcul plus court.

e) Parce que 12 n'est pas premier. Le petit théorème de Fermat exige un module premier ; ici il faudrait passer par un autre outil. On remarque d'ailleurs que $\mathrm{pgcd}(6,\ 12)=6\neq 1$, ce qui empêche toute inversibilité de 6 modulo 12.

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. Être premiers entre eux est une propriété du couple, pas de chaque nombre.

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 devient vraie si $a$ est premier, ou si l'on ajoute une hypothèse de coprimalité comme dans le théorème de Gauss.

c) Faux. On ne peut simplifier par $c$ que si $c$ et $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]$, pourtant $3\not\equiv 0\ [6]$. Ici $\mathrm{pgcd}(2,\ 6)=2\neq 1$.

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. L'exclure n'est pas une convention arbitraire : c'est ce qui rend unique la décomposition en facteurs premiers, sinon on pourrait insérer autant de facteurs 1 que l'on veut.