Terminale maths expertes / Arithmétique

Ex. 1★★★Multiples et diviseurs — Réponds à chaque question en justifiant en une ou deux lignes.

1. aListe tous les diviseurs positifs de $156$.
2. bDonne tous les diviseurs de $15$ dans $\mathbb{Z}$.
3. c$0$ est-il un multiple de $23$ ? Justifie.
4. dJustifie que $17 \mid 391$. A-t-on aussi $391 \mid 17$ ? Justifie.
5. e$-8$ est-il un diviseur de $120$ ? Justifie.
6. f$1$ est-il un nombre premier ? Justifie.

Ex. 2★★★Critères de divisibilité sans confusion — En plus des critères par $3$, $4$ et $9$, on admet le critère par $11$ : un entier est divisible par $11$ si, en partant des unités, la somme alternée de ses chiffres (unités $-$ dizaines $+$ centaines $-$ …) est un multiple de $11$. Justifie chaque réponse par le bon critère.

1. a$8\,316$ est-il divisible par $4$ ? par $9$ ?
2. b$4\,125$ est divisible par $3$. L'est-il par $9$ ?
3. cInès affirme : « $3\,718$ est pair, donc il est divisible par $4$. » A-t-elle raison ? Justifie.
4. d$7\,293$ est-il divisible par $11$ ?
5. eMalo affirme : « La somme des chiffres de $6\,391$ vaut $19$, donc $6\,391$ n'est pas divisible par $11$. » A-t-il raison ? Justifie.

Ex. 3★★★Vrai ou faux sur les entiers — Pour chaque affirmation, dis si elle est vraie ou fausse. Justifie : démonstration si elle est vraie, contre-exemple si elle est fausse.

1. aPour tout entier $n$, $n + (n + 1)$ est pair.
2. bPour tout entier $n$, $n^2 + n$ est pair.
3. cLa somme de deux entiers impairs quelconques est un multiple de $4$.
4. dSi un entier $a$ divise le produit $bc$ de deux entiers $b$ et $c$, alors $a \mid b$ ou $a \mid c$.
5. eSami constate que $n^2 + n + 41$ est premier pour $n = 0$, $1$, $2$ et $3$. Il en conclut : « $n^2 + n + 41$ est premier pour tout entier naturel $n$. »

Ex. 4★★★Parité et produit de trois consécutifs — Soit $n$ un entier naturel. On pose $P = n(n + 1)(n + 2)$.

1. aEn traitant $n = 2k$ puis $n = 2k + 1$, démontre que $n^2$ et $n$ ont la même parité.
2. bDéduis-en que $n^2 + 3n + 5$ est impair.
3. cJustifie que $P$ est pair.
4. dEn traitant $n = 3k$, $n = 3k + 1$ et $n = 3k + 2$, démontre que $P$ est un multiple de $3$.
5. eDéduis-en que $P$ est un multiple de $6$.

Ex. 5★★★Nombres premiers : corriger, puis démontrer — Un entier naturel est premier s'il a exactement deux diviseurs positifs distincts : $1$ et lui-même.

1. aLina dit : « $91$ n'est divisible ni par $2$, ni par $3$, ni par $5$, donc $91$ est premier. » Corrige-la. Détermine ensuite si $223$ est premier, en justifiant à quel diviseur tu arrêtes les tests.
2. bTom affirme : « Aucun nombre premier n'est pair. » Corrige-le, puis démontre que $2$ est le seul nombre premier pair.
3. cSoit $p$ un nombre premier tel que $p \geqslant 5$. À l'aide de la division euclidienne de $p$ par $6$, démontre que $p = 6k + 1$ ou $p = 6k + 5$, avec $k \in \mathbb{N}$.
4. dDémontre que pour tout nombre premier $p \geqslant 5$, $24 \mid p^2 - 1$. Tu peux traiter séparément $k$ pair et $k$ impair.
5. eVrai ou faux : « Si $n \geqslant 5$ est un entier tel que $24 \mid n^2 - 1$, alors $n$ est premier. » Justifie.

Ex. 6★★★Quand n − 2 divise n + 7 — Dans tout l'exercice, $n$ désigne un entier relatif. On cherche tous les $n$ tels que $n - 2 \mid n + 7$.

1. aPour $n = 2$, le nombre $n + 7$ est-il un multiple de $n - 2$ ? Justifie.
2. bDémontre que si $n - 2 \mid n + 7$, alors $n - 2 \mid 9$.
3. cListe tous les diviseurs de $9$ dans $\mathbb{Z}$, puis déduis-en tous les entiers relatifs $n$ tels que $n - 2 \mid n + 7$.
4. dAna affirme : « Puisque $n - 2$ divise $n + 7$, on a aussi $n + 7$ qui divise $n - 2$. » A-t-elle raison ? Justifie.
5. eDémontre que si $a$ et $b$ sont deux entiers naturels non nuls tels que $a \mid b$ et $b \mid a$, alors $a = b$. Ce résultat reste-t-il vrai dans $\mathbb{Z}$ ? Justifie.

Ex. 7★★★Diviseurs en Python et nombres parfaits — Un entier naturel $n \geqslant 1$ est parfait s'il est égal à la somme de ses diviseurs positifs autres que lui-même. Ben écrit cette fonction censée lister les diviseurs positifs de $a \geqslant 1$ :def diviseurs(a): L = [] d = 1 while d * d <= a: if a % d == 0: L.append(d) L.append(a // d) d = d + 1 return L

1. aQu'affiche print(diviseurs(45)) ? Justifie pourquoi la boucle peut s'arrêter dès que d * d > a.
2. bQu'affiche print(diviseurs(49)) ? Explique le défaut, puis corrige la fonction en ajoutant un test.
3. cÀ l'aide de la fonction corrigée, liste les diviseurs positifs de $496$. Le nombre $496$ est-il parfait ? Justifie.
4. dDémontre qu'aucun nombre premier n'est parfait. Le nombre $1$ est-il parfait ? Justifie.
5. eLéo vérifie que $6$ est parfait et conclut : « Tout nombre parfait est un multiple de $6$. » A-t-il raison ? Justifie.

Ex. 8★★★Divisions euclidiennes, dividendes négatifs compris — Donne à chaque fois le quotient $q$ et le reste $r$, avec $a = bq + r$ et $0 \leqslant r < b$.

1. aEffectue la division euclidienne de $1\,000$ par $37$.
2. bEffectue la division euclidienne de $2\,026$ par $48$.
3. cEffectue la division euclidienne de $-85$ par $6$.
4. dEffectue la division euclidienne de $-250$ par $11$.
5. eEffectue la division euclidienne de $-1$ par $13$.
6. fEffectue la division euclidienne de $7$ par $15$.

Ex. 9★★★Est-ce bien la division demandée ? — Chaque égalité est exacte. Si elle ne donne pas la division euclidienne demandée, écris la bonne division.

1. aL'égalité $250 = 12 \times 19 + 22$ donne-t-elle la division euclidienne de $250$ par $12$ ? Justifie.
2. bL'égalité $318 = 25 \times 12 + 18$ donne-t-elle la division euclidienne de $318$ par $25$ ? Justifie.
3. cL'égalité $318 = 25 \times 12 + 18$ donne-t-elle la division euclidienne de $318$ par $12$ ? Justifie.
4. dL'égalité $-71 = 8 \times (-8) - 7$ donne-t-elle la division euclidienne de $-71$ par $8$ ? Justifie.
5. eL'égalité $-60 = 9 \times (-7) + 3$ donne-t-elle la division euclidienne de $-60$ par $9$ ? Justifie.

Ex. 10★★★Quand $n - 3$ divise $2n + 9$ — On cherche tous les entiers relatifs $n$ tels que $n - 3$ divise $2n + 9$.

1. aTrouve des entiers $u$ et $v$ tels que $u(2n + 9) + v(n - 3)$ ne dépende pas de $n$. Déduis-en un entier que $n - 3$ divise forcément.
2. bDéduis-en la liste des valeurs possibles de $n$ dans $\mathbb{Z}$.
3. cVérifie que chacune de ces valeurs convient, puis conclus.
4. dDéduis-en les entiers naturels $n$ pour lesquels $\frac{2n + 9}{n - 3}$ est un entier naturel.

Ex. 11★★★Restes d'une somme, d'un produit, changement de diviseur — Dans la division euclidienne par $14$, l'entier naturel $a$ a pour reste $9$ et l'entier naturel $b$ a pour reste $11$.

1. aDétermine le reste de la division euclidienne de $a + b$ par $14$.
2. bDétermine le reste de la division euclidienne de $ab$ par $14$.
3. cDétermine le reste de la division euclidienne de $a$ par $7$.
4. dLe reste de la division euclidienne de $a$ par $28$ est-il forcément $9$ ? Justifie.
5. eYanis affirme : « si $14$ divise un produit $cd$ d'entiers, alors $14$ divise $c$ ou $d$ ». Vrai ou faux ? Justifie.

Ex. 12★★★Quand $n + 5$ divise $n^2 + 12$ — On cherche tous les entiers relatifs $n$ tels que $n + 5$ divise $n^2 + 12$.

1. aDémontre que si $n + 5$ divise $n^2 + 12$, alors $n + 5$ divise $5n - 12$.
2. bDéduis-en que $n + 5$ divise un entier qui ne dépend pas de $n$, puis donne la liste des valeurs possibles de $n$.
3. cVérifie chaque valeur trouvée et conclus. Explique pourquoi cette vérification est nécessaire.
4. dDéduis-en les entiers naturels $n$ pour lesquels $\frac{n^2 + 12}{n + 5}$ est un entier, et donne la valeur de cet entier.

Ex. 13★★★Un reste égal au carré du quotient — On cherche les entiers naturels $a$ dont la division euclidienne par $17$ a un reste égal au carré du quotient. On note $q$ ce quotient.

1. aExprime $a$ en fonction de $q$, puis justifie que $q \leqslant 4$.
2. bDéduis-en toutes les valeurs possibles de $a$. Vérifie que chacune convient.
3. cDétermine maintenant les entiers relatifs $a < 0$ dont la division euclidienne par $17$ a un reste égal au carré du quotient.
4. dDémontre que tous les entiers trouvés aux deux questions précédentes sont pairs, sans les tester un par un.
5. eOn remplace $17$ par $50$. Combien d'entiers naturels $a$ ont alors un reste égal au carré du quotient ? Justifie.

Ex. 14★★★Carrés et division par $4$ — Dans tout l'exercice, $n$, $a$ et $b$ désignent des entiers relatifs.

1. aEn distinguant $n$ pair et $n$ impair, démontre que le reste de la division euclidienne de $n^2$ par $4$ vaut $0$ ou $1$.
2. bDéduis-en tous les restes possibles de la division euclidienne de $a^2 + b^2$ par $4$.
3. cJustifie que $2\,027$ n'est pas la somme des carrés de deux entiers.
4. dVrai ou faux : si $4$ divise $a^2 + b^2$, alors $a$ et $b$ sont pairs. Justifie.
5. eDéduis-en que si $a$ et $b$ sont impairs, alors $a^2 + b^2$ n'est le carré d'aucun entier.

Ex. 15★★★Euclide à la main — Détaille chaque calcul.

1. aCalcule $\operatorname{PGCD}(2\,431\,;1\,001)$ avec l’algorithme d’Euclide.
2. bDéduis-en la liste des diviseurs communs positifs de $2\,431$ et $1\,001$.
3. cJustifie que $\operatorname{PGCD}(4\,199\,;1\,547)=\operatorname{PGCD}(1\,547\,;1\,105)$, puis termine le calcul.
4. dCalcule $\operatorname{PGCD}((-126)\,;495)$.
5. eCalcule $\operatorname{PGCD}(637\,;0)$.
6. fCalcule $\operatorname{PGCD}(1\,847\,;1\,848)$ en une ligne, sans algorithme.

Ex. 16★★★Euclide en Python — On donne le programme suivant.def euclide(a, b): n = 0 while b != 0: r = a % b a = b b = r n = n + 1 return a, nValeurs à la fin de chaque passage dans la boucle pour euclide(1071, 462) :

1. aRecopie et complète le tableau.
2. bQu’affiche print(euclide(1071, 462)) ? Que représentent les deux nombres affichés ?
3. cLéa échange les lignes a = b et b = r. Qu’affiche alors print(euclide(1071, 462)) ? Explique son erreur.
4. dQu’affiche print(euclide(462, 1071)) ? Justifie.
5. eQu’affiche print(euclide(58, 0)) ? Justifie.

Ex. 17★★★Un PGCD qui dépend de n — Pour tout entier naturel $n$, on pose $a=2n+7$ et $b=n+2$.

1. aDémontre que $\operatorname{PGCD}(a\,;b)=\operatorname{PGCD}(n+2\,;3)$. Déduis-en les valeurs possibles de $\operatorname{PGCD}(a\,;b)$.
2. bHugo en conclut que $\operatorname{PGCD}(a\,;b)=3$ pour tout $n$. A-t-il raison ? Justifie.
3. cDétermine les entiers naturels $n$ pour lesquels $\operatorname{PGCD}(a\,;b)=3$.
4. dLa fraction $\frac{2n+7}{n+2}$ est-elle irréductible pour $n=2\,026$ ? Et pour $n=2\,027$ ? Justifie.

Ex. 18★★★PGCD imposé, somme imposée — On cherche les entiers naturels $a$ et $b$, avec $a\leqslant b$, tels que $a+b=288$ et $\operatorname{PGCD}(a\,;b)=24$. On admet que $\operatorname{PGCD}(ka\,;kb)=k\times\operatorname{PGCD}(a\,;b)$ pour tout entier naturel $k$ non nul.

1. aJustifie qu’il existe des entiers naturels $a'$ et $b'$ tels que $a=24a'$, $b=24b'$ et $\operatorname{PGCD}(a'\,;b')=1$.
2. bDémontre que $a'+b'=12$.
3. cNina propose $a'=2$ et $b'=10$, soit $a=48$ et $b=240$. A-t-elle raison ? Justifie.
4. dDétermine tous les couples $(a\,;b)$ cherchés.

Ex. 19★★★Une fraction qui se simplifie parfois — Pour tout entier naturel $n$, on pose $a = 5n + 3$ et $b = 3n + 4$. On note $d = \operatorname{PGCD}(a\,;b)$.

1. aTrouve des entiers $u$ et $v$ tels que $ua + vb$ ne dépende pas de $n$. Déduis-en les valeurs possibles de $d$.
2. bDémontre que $11 \mid b$ si et seulement si $11 \mid a$.
3. cDétermine tous les entiers naturels $n$ pour lesquels $d = 11$.
4. dPour quels entiers naturels $n$ la fraction $\frac{5n+3}{3n+4}$ est-elle irréductible ? Écris-la sous forme irréductible pour $n = 17$.

Ex. 20★★★PGCD égal à 18 : produit ou écart imposé — On cherche des entiers naturels $a$ et $b$, avec $1 \leqslant a < b$, tels que $\operatorname{PGCD}(a\,;b) = 18$. On admet que $\operatorname{PGCD}(ka\,;kb) = k \times \operatorname{PGCD}(a\,;b)$ pour tout entier naturel $k$ non nul.

1. aJustifie qu’il existe des entiers naturels $a'$ et $b'$, premiers entre eux, tels que $a = 18a'$ et $b = 18b'$.
2. bOn impose $ab = 11\,664$. Malik propose le couple $(36\,;324)$, dont le produit vaut bien $11\,664$. Ce couple convient-il ? Justifie.
3. cDétermine tous les couples $(a\,;b)$ tels que $\operatorname{PGCD}(a\,;b) = 18$ et $ab = 11\,664$.
4. dDémontre que, pour tout entier naturel $k$, $\operatorname{PGCD}(k\,;k+1) = 1$.
5. eDéduis-en tous les couples $(a\,;b)$ tels que $\operatorname{PGCD}(a\,;b) = 18$ et $b - a = 18$.

Ex. 21★★★Un programme qui renvoie toujours 0 — Pour calculer $\operatorname{PGCD}(a\,;b)$ avec $a \geqslant 1$ et $b \geqslant 1$, Inès écrit ce programme :def pgcd(a, b): r = a % b while r != 0: a = b b = r r = a % b return r

1. aQu’affiche print(pgcd(28, 6)) ? Explique l’erreur d’Inès et corrige une seule ligne.
2. bAvec le programme corrigé, écris une boucle qui affiche $\operatorname{PGCD}(n^2+3\,;n+1)$ pour $n$ de $0$ à $7$. Donne ce qu’elle affiche.
3. cPour tout entier naturel $n$, calcule $(n^2 + 3) - (n-1)(n+1)$. Déduis-en que $\operatorname{PGCD}(n^2+3\,;n+1) = \operatorname{PGCD}(n+1\,;4)$.
4. dDétermine, selon les valeurs de $n$, la valeur de $\operatorname{PGCD}(n^2+3\,;n+1)$.

Ex. 22★★★Remonter l'algorithme d'Euclide — Écris l'algorithme d'Euclide en isolant chaque reste, puis remonte-le pour obtenir l'égalité demandée. Termine par une vérification numérique.

1. aDétermine $\operatorname{PGCD}(53\,;17)$ et un couple d'entiers $(u\,;v)$ tel que $53u+17v=\operatorname{PGCD}(53\,;17)$.
2. bDétermine $\operatorname{PGCD}(117\,;45)$ et un couple d'entiers $(u\,;v)$ tel que $117u+45v=\operatorname{PGCD}(117\,;45)$.
3. cDétermine $\operatorname{PGCD}(100\,;37)$, puis un couple d'entiers $(u\,;v)$ tel que $100u+37v=3$.
4. dTrouve des entiers $u$ et $v$ tels que $29u-12v=1$. Attention au signe devant $12v$.

Ex. 23★★★Premiers entre eux pour tout entier n — Dans tout l'exercice, $n$ est un entier naturel.

1. aDémontre que $n$ et $2n+1$ sont premiers entre eux.
2. bCalcule $3(2n+1)-2(3n+1)$. Déduis-en que la fraction $\frac{3n+1}{2n+1}$ est irréductible.
3. cDémontre que $n+1$ et $n^2+n+1$ sont premiers entre eux.
4. dCalcule $2(2n+3)-(4n+1)$. Peut-on en déduire que $2n+3$ et $4n+1$ sont toujours premiers entre eux ? Justifie avec $n=1$.
5. eInès affirme : « $2n+1$ et $3n+1$ sont premiers entre eux, donc ce sont des nombres premiers. » A-t-elle raison ? Justifie avec $n=4$.

Ex. 24★★★Bézout : vrai ou faux ? — Pour chaque affirmation, dis si elle est vraie ou fausse. Justifie : démonstration ou contre-exemple.

1. aComme $6\times 4+10\times(-2)=4$, on a $\operatorname{PGCD}(6\,;10)=4$.
2. bIl existe des entiers $u$ et $v$ strictement positifs tels que $14u+9v=1$.
3. c$(3\,;-11)$ est l'unique couple d'entiers $(u\,;v)$ tel que $15u+4v=1$.
4. dComme $13\times 3+20\times(-2)=-1$, les entiers $13$ et $20$ sont premiers entre eux.

Ex. 25★★★Euclide étendu en Python — On considère la fonction suivante. def bezout(a, b): u0, v0, u1, v1 = 1, 0, 0, 1 while b != 0: q = a // b a, b = b, a % b u0, u1 = u1, u0 - q * u1 v0, v1 = v1, v0 - q * v1 return a, u0, v0

1. aOn appelle bezout(162, 70). Complète le tableau des valeurs après chaque passage dans la boucle.

   passage	a	b	u0	v0
   départ	162	70	1	0
   1	…	…	…	…
   2	…	…	…	…
   3	…	…	…	…
   4	…	…	…	…

2. bQu'affiche print(bezout(162, 70)) ? Écris l'égalité de Bézout obtenue et vérifie-la.
3. cDéduis-en un couple d'entiers $(x\,;y)$ tel que $81x+35y=1$. Que peux-tu dire de $81$ et $35$ ?
4. dDéduis-en un couple d'entiers $(x\,;y)$ tel que $162x+70y=14$. Existe-t-il des entiers $x$, $y$ tels que $162x+70y=15$ ? Justifie.

Ex. 26★★★PGCD de deux expressions en n : un diviseur de 11 — Pour tout entier naturel $n$, on pose $a=2n+3$ et $b=5n+2$. On note $d=\operatorname{PGCD}(a\,;b)$.

1. aCalcule $5a-2b$. Malik en déduit que $d=11$ pour tout entier naturel $n$. A-t-il raison ? Justifie.
2. bDéduis-en les valeurs possibles de $d$.
3. cDémontre que si $11 \mid 2n+3$, alors $11 \mid n-4$. Tu pourras calculer $6(2n+3)-11(n+2)$.
4. dDéduis-en l'ensemble des entiers naturels $n$ pour lesquels $d=11$.
5. eLa fraction $\frac{2n+3}{5n+2}$ est-elle irréductible pour $n=2\,026$ ? Pour $n=2\,028$ ? Sinon, simplifie-la.

Ex. 27★★★Euclide étendu, signes et couples de Bézout — On s'intéresse aux entiers $281$ et $76$.

1. aComplète le tableau de l'algorithme d'Euclide ($a=bq+r$, $0\leqslant r<b$), puis donne $\operatorname{PGCD}(281\,;76)$.

   a	b	q	r
   281	76	…	…
   …	…	…	…
   …	…	…	…
   …	…	…	…
   …	…	…	…
   …	…	…	…

2. bRemonte l'algorithme pour obtenir un couple $(u\,;v)$ d'entiers tel que $281u+76v=1$. Vérifie ton résultat.
3. cLucas affirme que ce couple est le seul possible. A-t-il raison ? Justifie, puis donne un couple solution dont le premier terme est strictement négatif.
4. dDéduis-en un couple $(x\,;y)$ d'entiers naturels tel que $76x-281y=1$.
5. eOn exécute le programme suivant. Qu'affiche-t-il ? Justifie qu'il n'affiche qu'une seule ligne. for x in range(281): if (76 * x - 1) % 281 == 0: print(x, (76 * x - 1) // 281)

Ex. 28★★★Démontrer avec Bézout : ab et a + b — Dans les questions a) à c), $a$ et $b$ sont deux entiers naturels non nuls premiers entre eux.

1. aJustifie qu'il existe des entiers $u$ et $v$ tels que $au+bv=1$, puis démontre que $a$ et $a+b$ sont premiers entre eux.
2. bSoit $c$ un entier premier avec $a$ et avec $b$. En multipliant deux égalités de Bézout, démontre que $c$ et $ab$ sont premiers entre eux.
3. cOn admet que $b$ et $a+b$ sont aussi premiers entre eux. Déduis-en que $ab$ et $a+b$ sont premiers entre eux.
4. dPour tout entier naturel $n$ non nul, démontre que la fraction $\frac{2n+1}{n^2+n}$ est irréductible.
5. eZoé affirme : « $14$ et $25$ ne sont pas premiers, donc $350$ et $39$ ne sont pas premiers entre eux. » A-t-elle raison ? Justifie.

Ex. 29★★★Appliquer Gauss et son corollaire — Dans chaque cas, $n$ est un entier. Justifie chaque conclusion, en vérifiant les hypothèses du théorème utilisé.

1. aOn sait que $13 \mid 8n$. Que peux-tu en déduire pour $n$ ?
2. bOn sait que $15 \mid 4(n-3)$. Donne la forme générale des entiers $n$ concernés.
3. cOn sait que $14 \mid 6n$. Peut-on en déduire que $14 \mid n$ ? Que peut-on déduire à la place ?
4. d$n$ est divisible par $9$ et par $10$. Par quel entier plus grand $n$ est-il forcément divisible ?
5. eVrai ou faux ? « Si $8 \mid n$ et $12 \mid n$, alors $96 \mid n$. » Justifie, puis donne un diviseur de $n$ plus grand que $12$ que ces deux hypothèses garantissent.

Ex. 30★★★Des solutions ou pas ? — Pour chaque équation d'inconnue $(x\,;y) \in \mathbb{Z}^2$, dis si elle admet des solutions. Si oui, écris l'équation équivalente obtenue en divisant par le PGCD des coefficients.

Ex. 31★★★Résolution complète avec Bézout — On considère l'équation (E) : $34x + 24y = 6$, d'inconnue $(x\,;y) \in \mathbb{Z}^2$.

1. aJustifie que (E) admet des solutions et écris l'équation simplifiée (E') qui lui est équivalente.
2. bÀ l'aide de l'algorithme d'Euclide, trouve une relation de Bézout entre $17$ et $12$, puis déduis-en une solution particulière de
   (E').
3. cRésous (E') dans $\mathbb{Z}^2$ en utilisant le théorème de Gauss.
4. dDétermine la solution de (E) telle que $0 \leqslant x < 12$.
5. eLéo propose $x = 15 + 17k$, $y = -21 - 12k$. Teste sa proposition avec $k = 1$ et explique son erreur.

Ex. 32★★★Miel et confiture au marché — Au marché de Colmar, Inès achète des pots de miel à $9$ € et des pots de confiture à $7$ €. Elle dépense exactement $100$ €. On note $x$ le nombre de pots de miel et $y$ le nombre de pots de confiture.

1. aJustifie que l'équation $9x + 7y = 100$ admet des solutions dans $\mathbb{Z}^2$, puis trouve une solution particulière avec $0 \leqslant x \leqslant 6$.
2. bRésous l'équation $9x + 7y = 100$ dans $\mathbb{Z}^2$.
3. cDéduis-en tous les achats possibles pour Inès.
4. dInès a acheté au moins autant de pots de miel que de pots de confiture. Combien de pots de chaque sorte a-t-elle achetés ?

Ex. 33★★★Restes imposés (type bac) — On cherche les entiers relatifs $N$ dont la division euclidienne par $19$ a pour reste $4$, et dont la division euclidienne par $12$ a pour reste $7$.

1. aDémontre que $N$ convient si et seulement si $N = 19x + 4 = 12y + 7$, où $(x\,;y) \in \mathbb{Z}^2$ est solution de (E) : $19x - 12y = 3$.
2. bAvec l'algorithme d'Euclide, trouve deux entiers $u$ et $v$ tels que $19u + 12v = 1$. Déduis-en une solution particulière de
   (E).
3. cRésous (E) dans $\mathbb{Z}^2$. Justifie l'usage du théorème de Gauss et vérifie la réciproque.
4. dDéduis-en l'expression des entiers $N$ cherchés, puis le plus petit entier naturel qui convient.
5. eDétermine tous les entiers $N$ qui conviennent et qui vérifient $1\,000 \leqslant N \leqslant 2\,000$.

Ex. 34★★★Billetterie du musée de Nantes — Au musée de Nantes, un billet adulte coûte $14$ € et un billet enfant coûte $8$ €. Pour un groupe, on note $x$ le nombre de billets adultes et $y$ le nombre de billets enfants vendus.

1. aUn jour, la caissière annonce une recette de $225$ € pour un groupe. Démontre qu'elle s'est trompée.
2. bUn autre groupe paie $222$ €. Écris l'équation (E) vérifiée par $(x\,;y)$, puis une équation (E') équivalente dont les coefficients sont premiers entre eux.
3. cRésous (E') dans $\mathbb{Z}^2$ : donne une solution particulière, applique le théorème de Gauss, puis vérifie la réciproque.
4. dHugo affirme que les solutions de (E') sont les couples $(9 + 8k\,;12 - 14k)$, avec $k \in \mathbb{Z}$. A-t-il raison ? Justifie.
5. eDétermine toutes les compositions possibles du groupe, puis celle où il y a plus d'adultes que d'enfants.

Ex. 35★★★Racines rationnelles d'un polynôme — On considère l'équation (E) : $3x^3 + x^2 + x - 2 = 0$. On suppose qu'un rationnel $\frac{p}{q}$ est solution de (E), avec $p \in \mathbb{Z}$, $q \in \mathbb{N}^*$ et $\operatorname{PGCD}(p\,;q)=1$.

1. aDémontre que $3p^3 + p^2q + pq^2 = 2q^3$. Déduis-en que $p \mid 2q^3$ et que $q \mid 3p^3$.
2. bEn appliquant plusieurs fois le théorème de Gauss, démontre que $p \mid 2$ et que $q \mid 3$.
3. cDéduis-en la liste des rationnels qui peuvent être solutions de (E), puis détermine toutes les solutions rationnelles de
   (E).
4. dÉcris une solution de (E) sous la forme $\frac{p}{q}$ avec $p \nmid 2$. Explique quelle hypothèse du théorème de Gauss n'est alors plus vérifiée.

Ex. 36★★★Tester la primalité, utiliser le crible — Pour décider si un entier $n \geqslant 2$ est premier, il suffit de tester les nombres premiers $p$ tels que $p^2 \leqslant n$.

1. aLe nombre $1$ est-il premier ? Justifie.
2. bEncadre $263$ entre deux carrés consécutifs, puis décide si $263$ est premier.
3. cÉcris $391$ comme une différence de deux carrés, puis déduis-en si $391$ est premier.
4. dThéo teste $527$ avec $2$, $3$, $5$, $7$, $11$ et $13$. Aucun ne divise $527$, donc il conclut que $527$ est premier. A-t-il raison ? Justifie.
5. eInès dit : « Pour tester $409$, je dois essayer tous les entiers jusqu'à $204$. » Corrige sa méthode, puis décide si $409$ est premier.
6. fTu appliques le crible d'Ératosthène aux entiers de $2$ à $200$. À partir de quel nombre commences-tu à barrer les multiples de $11$ ? Justifie.
7. gDans ce même crible jusqu'à $200$, quel est le dernier nombre premier dont tu dois barrer les multiples ? Justifie.

Ex. 37★★★Décomposer, compter les diviseurs, carrés parfaits

1. aDécompose $1\,008$ en produit de facteurs premiers.
2. bDéduis-en le nombre de diviseurs positifs de $1\,008$.
3. cDécompose $2\,310$ en facteurs premiers et donne son nombre de diviseurs positifs.
4. dCombien $1\,008$ a-t-il de diviseurs positifs impairs ? Donne-les.
5. e$1\,008$ est-il un carré parfait ? Justifie.
6. fDétermine le plus petit entier $k \geqslant 1$ tel que $1\,008k$ soit un carré parfait, et précise de quel entier c'est le carré.
7. gCombien $1\,008k$ a-t-il de diviseurs positifs ? Explique pourquoi ce nombre est impair.

Ex. 38★★★PGCD et PPCM par les décompositions — On considère les entiers $a = 2\,200$ et $b = 480$.

1. aDécompose $a$ et $b$ en produits de facteurs premiers.
2. bMalik écrit : « $\operatorname{PGCD}(a\,;b) = 2^3 \times 3 \times 5 \times 11$, car je prends le plus petit exposant de chaque facteur qui apparaît. » Explique son erreur, puis calcule $\operatorname{PGCD}(a\,;b)$.
3. cDéduis-en $\operatorname{PPCM}(a\,;b)$ avec la relation entre PGCD, PPCM et $ab$. Contrôle ensuite ton résultat avec les décompositions.
4. dDétermine le plus petit entier $m \geqslant 1$ tel que $2\,200m$ soit un multiple de $480$. Justifie.
5. eCombien $a$ et $b$ ont-ils de diviseurs positifs communs ? Donne-les.

Ex. 39★★★Une infinité de nombres premiers — On suppose, par l'absurde, qu'il n'existe qu'un nombre fini de nombres premiers : $p_1$, $p_2$, …, $p_k$. On pose $N = p_1 \times p_2 \times \dots \times p_k + 1$.

1. aJustifie que $N \geqslant 2$, puis que $N$ admet au moins un diviseur premier $p$.
2. bDémontre que $p$ n'est égal à aucun des $p_i$.
3. cConclus le raisonnement par l'absurde.
4. dLina affirme : « La preuve montre que $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1$ est premier. » Calcule ce nombre et divise-le par $59$. A-t-elle raison ? Justifie.
5. eDémontre que, pour tout entier $n \geqslant 2$, $n! + 1$ a un diviseur premier $p > n$. Vérifie-le pour $n = 5$.

Ex. 40★★★Expressions en n : premières ou non ? — Dans tout l'exercice, $n$ désigne un entier naturel.

1. aFactorise $n^2 - 1$. Déduis-en tous les entiers naturels $n$ pour lesquels $n^2 - 1$ est premier.
2. bDémontre que $n^4 + 4 = (n^2 + 2n + 2)(n^2 - 2n + 2)$.
3. cDémontre que $n^4 + 4$ est premier si et seulement si $n = 1$.
4. dCalcule $7^4 + 4$, puis donne sa décomposition en facteurs premiers. Justifie que chaque facteur obtenu est premier.
5. eQue renvoie premier(1) ? Corrige la fonction. Explique pourquoi il suffit de tester les d tels que d * d <= n, et pas tous les d jusqu'à n // 2.def premier(n): d = 2 while d * d <= n: if n % d == 0: return False d = d + 1 return True

Ex. 41★★★Entiers à nombre de diviseurs imposé — On rappelle que si $n = p_1^{a_1} \times \dots \times p_r^{a_r}$ (décomposition en facteurs premiers), alors $n$ a $(a_1 + 1) \times \dots \times (a_r + 1)$ diviseurs positifs.

1. aYanis affirme : « $56 = 2^3 \times 7$ a $3 \times 1 = 3$ diviseurs positifs. » Corrige son erreur, puis donne la liste des diviseurs positifs de $56$.
2. bDétermine toutes les formes possibles de la décomposition en facteurs premiers d'un entier qui a exactement $12$ diviseurs positifs.
3. cDéduis-en le plus petit entier naturel qui a exactement $12$ diviseurs positifs. Justifie.
4. dDétermine tous les entiers $n = 2^a \times 3^b$, avec $a$ et $b$ entiers naturels, qui ont exactement $9$ diviseurs positifs. Justifie qu'ils sont tous des carrés parfaits.
5. eDémontre qu'un entier $n \geqslant 2$ a un nombre impair de diviseurs positifs si et seulement si $n$ est un carré parfait.

Ex. 42★★★Retrouver deux entiers à partir de leur PGCD et de leur PPCM — On cherche des couples d'entiers naturels non nuls dont on connaît le PGCD et le PPCM.

1. aSoit $a = 2^4 \times 3 \times 7^2$ et $b = 2^2 \times 3^3 \times 5$. Calcule $\operatorname{PGCD}(a\,;b)$ et $\operatorname{PPCM}(a\,;b)$, en écrivant d'abord $a$ et $b$ avec les mêmes facteurs premiers.
2. bDémontre que pour tous entiers naturels non nuls $a$ et $b$, on a $\operatorname{PGCD}(a\,;b) \times \operatorname{PPCM}(a\,;b) = ab$.
3. cOn cherche $a \leqslant b$ tels que $\operatorname{PGCD}(a\,;b) = 18$ et $\operatorname{PPCM}(a\,;b) = 1\,260$. On pose $a = 18a'$ et $b = 18b'$. Justifie que $a'$ et $b'$ sont premiers entre eux et calcule $a'b'$.
4. dDéduis-en tous les couples $(a\,;b)$ cherchés.
5. eNora affirme : « Il existe deux entiers de PGCD $18$ et de PPCM $1\,000$. » A-t-elle raison ? Justifie.

Ex. 43★★★Restes de grandes puissances — Vérifie les hypothèses du petit théorème de Fermat, puis détermine le reste de la division euclidienne.

1. aReste de $2^{150}$ modulo $13$.
2. bReste de $5^{243}$ modulo $11$.
3. cReste de $2^{500}$ modulo $17$.
4. dReste de $6^{2026}$ modulo $19$.
5. eReste de $3^{1000}$ modulo $23$.

Ex. 44★★★Le théorème s'applique-t-il ? — Pour chaque calcul, dis si le petit théorème de Fermat s'applique et sous quelle forme. Justifie, puis donne le reste.

1. aReste de $4^{16}$ modulo $17$.
2. bReste de $10^{14}$ modulo $15$.
3. cReste de $22^{10}$ modulo $11$.
4. dReste de $5^{23}$ modulo $23$.
5. eReste de $2^{20}$ modulo $21$.
6. fReste de $9^{28}$ modulo $29$.

Ex. 45★★★Trois élèves, trois affirmations — Pour chaque élève, repère l'éventuelle erreur, justifie, puis donne une conclusion correcte.

1. aPour le reste de $3^{200}$ modulo $11$, Léa écrit : « $200 = 11 \times 18 + 2$, donc $3^{200} \equiv 3^{2} = 9\ [11]$. » A-t-elle raison ? Justifie.
2. bSachant que $2^{560} \equiv 1\ [561]$, Malik conclut que $561$ est premier. A-t-il raison ? Justifie.
3. cNora affirme : « $11$ est premier, donc pour tout entier $n$, $n^{10} \equiv 1\ [11]$. » A-t-elle raison ? Justifie.

Ex. 46★★★Un diviseur commun à tous les $n^{7} - n$ — Soit $n$ un entier. On étudie la divisibilité de $N = n^{7} - n$.

1. aDémontre que $7$ divise $N$ pour tout entier $n$.
2. bEn utilisant $n^{3} \equiv n\ [3]$, démontre que $3$ divise $N$ pour tout entier $n$.
3. cDémontre que $2$ divise $N$ pour tout entier $n$.
4. dDéduis-en un entier $d > 7$ qui divise $N$ pour tout entier $n$. Vérifie avec $n = 2$ et $n = 3$.

Ex. 47★★★Un faux premier : 341 — On dit qu'un entier $a$ est un témoin pour $n$ si $n \nmid a$ et si $a^{n-1} \not\equiv 1\ [n]$. Un témoin prouve que $n$ n'est pas premier.

1. aDécompose $341$ en facteurs premiers.
2. bCalcule $2^{10}$, puis le reste de la division euclidienne de $2^{10}$ par $341$.
3. cDéduis-en le reste de la division euclidienne de $2^{340}$ par $341$.
4. dHugo a trouvé ce reste. Il affirme : « D'après le petit théorème de Fermat, $341$ est donc premier. » A-t-il raison ? Justifie.
5. eAvec le petit théorème de Fermat modulo $31$, calcule le reste de $3^{340}$ modulo $31$. Déduis-en que $3$ est un témoin pour $341$.

Ex. 48★★★Les diviseurs de $n^{17} - n$ — Pour tout entier naturel $n$, on pose $N = n^{17} - n$.

1. aDémontre que $17 \mid N$ pour tout entier naturel $n$, y compris lorsque $17 \mid n$.
2. bSoit $p \in \{2\,;3\,;5\}$. Démontre que $p \mid N$ : traite d'abord le cas $p \nmid n$, puis le cas $p \mid n$.
3. cDéduis-en un entier $d$ supérieur à $17$ qui divise $N$ pour tout entier naturel $n$. Justifie.
4. dCalcule $N$ pour $n = 2$. Déduis-en que $4$ ne divise pas $N$ pour tout entier naturel $n$.
5. eAna affirme : « Par le même raisonnement, $7 \mid N$ pour tout entier naturel $n$. » Vrai ou faux ? Justifie.

Ex. 49★★★Quels premiers divisent $2^{p} + 1$ ? — On cherche les nombres premiers $p$ tels que $p \mid 2^{p} + 1$. Inès écrit ce programme : def premier(n): if n < 2: return False d = 2 while d * d <= n: if n % d == 0: return False d = d + 1 return True for p in range(2, 60): if premier(p) and (2**p + 1) % p == 0: print(p)

1. aExplique pourquoi la fonction premier peut s'arrêter dès que d * d > n.
2. bSoit $p$ un nombre premier. Démontre que $p \mid 2^{p} + 1$ si et seulement si $p \mid 3$.
3. cDéduis-en tous les nombres premiers $p$ tels que $p \mid 2^{p} + 1$, puis ce qu'affiche le programme.
4. dMila remplace le test par (3**p + 5) % p == 0. Elle pense que l'affichage ne change pas. A-t-elle raison ? Justifie.
5. eTom affirme : « Pour tout nombre premier $p$, $p \mid 2^{p-1} - 1$. » Vrai ou faux ? Justifie.