Aller au contenu

Arithmétique dans Z 1 bac SM : 16 exercices corrigés

Type
Exercices corrigés
Exercices
16

Lister des diviseurs, diviser un entier négatif, calculer un PGCD par l'algorithme d'Euclide, trouver le reste d'une grande puissance, démontrer une divisibilité pour tout entier nn et résoudre une équation dans Z/nZ\mathbb{Z}/n\mathbb{Z}. Cette série de 16 exercices corrigés couvre le chapitre « Arithmétique dans ℤ » de la 1re année du bac sciences mathématiques, seule filière qui l'étudie. Elle suit l'ordre du cours et résumé d'arithmétique dans Z.

Niveaux : 5 exercices faciles, 9 moyens et 2 difficiles, puis quatre questions flash et un devoir d'une heure qui associe l'arithmétique, la récurrence et une suite. Aucun calcul ne demande de calculatrice.

Sommaire10 parties

Diviseurs et divisibilité dans Z

On cherche les diviseurs positifs, puis on ajoute leurs opposés. Pour savoir quand n+αn+\alpha divise une expression, on écrit l'expression comme un multiple de n+αn+\alpha plus une constante : n+αn+\alpha doit diviser cette constante. Une équation produit dans Z2\mathbb{Z}^2, le produit cartésien Z×Z\mathbb{Z}\times\mathbb{Z}, se ramène à une liste de couples de diviseurs.

Exercice 1 : Diviseurs d’un entier relatif

Facile
On considère l'entier a=−234a=-234.
  1. Décomposer 234 en produit de facteurs premiers.
  2. Lister les diviseurs positifs de 234.
  3. Combien aa a-t-il de diviseurs dans Z\mathbb{Z} ?
  4. Vrai ou faux : a) −18∣a-18\mid a ; b) a∣−18a\mid-18 ; c) 26∣a26\mid a et 9∣a9\mid a, donc 26×9∣a26\times9\mid a ; d) 4∣a4\mid a.
Voir le corrigé
  1. 234=2×117=2×32×13234=2\times117=2\times3^2\times13.
  2. Les diviseurs positifs sont les 2α×3β×13γ2^{\alpha}\times3^{\beta}\times13^{\gamma} avec α∈{0 ;1}\alpha\in\{0\,;1\}, β∈{0 ;1 ;2}\beta\in\{0\,;1\,;2\}, γ∈{0 ;1}\gamma\in\{0\,;1\}, soit (1+1)(2+1)(1+1)=12(1+1)(2+1)(1+1)=12 diviseurs : 1, 2, 3, 6, 9, 13, 18, 26, 39, 78, 117, 234.
  3. aa et −a=234-a=234 ont les mêmes diviseurs ; chaque diviseur positif donne aussi son opposé : aa a 24 diviseurs dans Z\mathbb{Z}.
  4. a) Vrai : −234=(−18)×13-234=(-18)\times13. b) Faux : un diviseur de −18-18 a une valeur absolue au plus 18, or ∣a∣=234|a|=234. c) Vrai ici, car 26×9=23426\times9=234 ; mais le raisonnement est faux en général : 6∣126\mid12 et 4∣124\mid12, alors que 24∤1224\nmid12. d) Faux : l'exposant de 2 dans 234 est 1, et 4=224=2^2.

Exercice 2 : Trouver n pour qu’un entier en divise un autre

Moyen
Dans tout l'exercice, nn désigne un entier relatif.
  1. Déterminer les entiers n≠1n\neq1 tels que n−1n-1 divise 4n+114n+11.
  2. Vérifier que n2+10=(n+3)(n−3)+19n^2+10=(n+3)(n-3)+19, puis déterminer les entiers n≠−3n\neq-3 tels que n+3n+3 divise n2+10n^2+10.
  3. En déduire les entiers nn pour lesquels 4n+11n−1\dfrac{4n+11}{n-1} et n2+10n+3\dfrac{n^2+10}{n+3} sont tous les deux des entiers relatifs.
Voir le corrigé
  1. 4n+11=4(n−1)+154n+11=4(n-1)+15. Comme n−1n-1 divise 4(n−1)4(n-1), la propriété de combinaison donne n−1∣4n+11  ⟺  n−1∣15n-1\mid4n+11\iff n-1\mid15. Les diviseurs de 15 sont ±1\pm1, ±3\pm3, ±5\pm5, ±15\pm15, donc n∈{−14 ;−4 ;−2 ;0}n\in\{-14\,;-4\,;-2\,;0\} ou n∈{2 ;4 ;6 ;16}n\in\{2\,;4\,;6\,;16\}. Contrôle : n=16n=16 donne 7515=5\frac{75}{15}=5.
  2. (n+3)(n−3)=n2−9(n+3)(n-3)=n^2-9, donc n2+10=(n+3)(n−3)+19n^2+10=(n+3)(n-3)+19. De même, n+3∣n2+10  ⟺  n+3∣19n+3\mid n^2+10\iff n+3\mid19. 19 est premier, donc n+3∈{−19 ;−1 ;1 ;19}n+3\in\{-19\,;-1\,;1\,;19\}, soit n∈{−22 ;−4 ;−2 ;16}n\in\{-22\,;-4\,;-2\,;16\}.
  3. On prend l'intersection des deux ensembles : n∈{−4 ;−2 ;16}n\in\{-4\,;-2\,;16\}. Contrôle : pour n=−4n=-4, −5−5=1\frac{-5}{-5}=1 et 26−1=−26\frac{26}{-1}=-26 ; pour n=−2n=-2, 3−3=−1\frac{3}{-3}=-1 et 141=14\frac{14}{1}=14 ; pour n=16n=16, 5 et 26619=14\frac{266}{19}=14.

Exercice 3 : Équation produit à deux inconnues entières

Moyen
  1. Développer (x+2)(y−3)(x+2)(y-3), puis résoudre dans Z2\mathbb{Z}^2 l'équation xy−3x+2y=13xy-3x+2y=13.
  2. Montrer que, pour xx et yy entiers, xy=2x+3y  ⟺  (x−3)(y−2)=6xy=2x+3y\iff(x-3)(y-2)=6.
  3. En déduire les couples (x ;y)(x\,;y) d'entiers naturels non nuls tels que 3x+2y=1\dfrac3x+\dfrac2y=1.
Indication
Question 3 : multiplier par xyxy. Les facteurs x−3x-3 et y−2y-2 peuvent être négatifs, mais x−3≥−2x-3\geq-2 et y−2≥−1y-2\geq-1.
Voir le corrigé
  1. (x+2)(y−3)=xy−3x+2y−6(x+2)(y-3)=xy-3x+2y-6, donc l'équation équivaut à (x+2)(y−3)=7(x+2)(y-3)=7. Les entiers x+2x+2 et y−3y-3 forment un couple de diviseurs de 7 dont le produit vaut 7 : (1 ;7)(1\,;7), (7 ;1)(7\,;1), (−1 ;−7)(-1\,;-7), (−7 ;−1)(-7\,;-1). Les solutions sont (−1 ;10)(-1\,;10), (5 ;4)(5\,;4), (−3 ;−4)(-3\,;-4) et (−9 ;2)(-9\,;2). Contrôle : 5×4−15+8=135\times4-15+8=13.
  2. (x−3)(y−2)=xy−2x−3y+6(x-3)(y-2)=xy-2x-3y+6, donc (x−3)(y−2)=6  ⟺  xy−2x−3y=0  ⟺  xy=2x+3y(x-3)(y-2)=6\iff xy-2x-3y=0\iff xy=2x+3y.
  3. Pour x,y∈N∗x,y\in\mathbb{N}^*, on multiplie par xy≠0xy\neq0 : 3x+2y=1  ⟺  3y+2x=xy  ⟺  (x−3)(y−2)=6\frac3x+\frac2y=1\iff3y+2x=xy\iff(x-3)(y-2)=6. Comme x≥1x\geq1 et y≥1y\geq1, x−3≥−2x-3\geq-2 et y−2≥−1y-2\geq-1. Un produit positif à facteurs négatifs exigerait x−3∈{−2 ;−1}x-3\in\{-2\,;-1\} et y−2=−1y-2=-1, donc un produit égal à 2 ou à 1, et non à 6. Les deux facteurs sont donc des diviseurs positifs de 6 : (x−3 ;y−2)(x-3\,;y-2) est l'un des couples (1 ;6)(1\,;6), (2 ;3)(2\,;3), (3 ;2)(3\,;2), (6 ;1)(6\,;1), d'où les solutions (x ;y)(x\,;y) : (4 ;8)(4\,;8), (5 ;5)(5\,;5), (6 ;4)(6\,;4) et (9 ;3)(9\,;3). Contrôle : 39+23=13+23=1\frac39+\frac23=\frac13+\frac23=1.

Division euclidienne et restes : exercices

Pour a∈Za\in\mathbb{Z} et b∈N∗b\in\mathbb{N}^*, on écrit a=bq+ra=bq+r et l'on vérifie toujours 0≤r<b0\leq r\lt b : un reste n'est jamais négatif. Quand les nombres dépendent de nn, la condition r<br\lt b impose une condition sur nn. Pour une propriété de tous les entiers, on raisonne selon les restes possibles.

Exercice 4 : Division euclidienne avec des entiers négatifs

Facile
  1. Effectuer la division euclidienne de 345 par 17, puis celle de −345-345 par 17.
  2. Écrire 345=(−17)q+r345=(-17)q+r avec 0≤r<170\leq r\lt17.
  3. Le reste de la division euclidienne d'un entier aa par 11 est 6. Déterminer les restes de −a-a, de a+27a+27 et de 3a3a dans la division par 11.
  4. Déterminer les entiers relatifs aa dont le quotient dans la division euclidienne par 7 est −4-4.
Voir le corrigé
  1. 345=17×20+5345=17\times20+5 avec 0≤5<170\leq5\lt17 : quotient 20, reste 5. Donc −345=17×(−20)−5=17×(−21)+12-345=17\times(-20)-5=17\times(-21)+12, avec 0≤12<170\leq12\lt17 : quotient −21-21, reste 12, et non −5-5.
  2. 345=(−17)×(−20)+5345=(-17)\times(-20)+5 : q=−20q=-20 et r=5r=5.
  3. a=11q+6a=11q+6 avec q∈Zq\in\mathbb{Z}. Alors −a=11(−q)−6=11(−q−1)+5-a=11(-q)-6=11(-q-1)+5 : reste 5. a+27=11q+33=11(q+3)+0a+27=11q+33=11(q+3)+0 : reste 0, donc 11 divise a+27a+27. 3a=33q+18=11(3q+1)+73a=33q+18=11(3q+1)+7 : reste 7. Chaque fois, le reste obtenu est bien compris entre 0 et 10.
  4. a=7×(−4)+ra=7\times(-4)+r avec r∈{0 ;1 ;… ;6}r\in\{0\,;1\,;\dots\,;6\}, donc −28≤a≤−22-28\leq a\leq-22 : aa est l'un des sept entiers −28-28, −27-27, −26-26, −25-25, −24-24, −23-23, −22-22.

Exercice 5 : Division euclidienne dont les termes dépendent de n

Moyen
Dans cet exercice, nn est un entier naturel.
  1. Vérifier que n2+5n+9=(n+2)(n+3)+3n^2+5n+9=(n+2)(n+3)+3. Pour quels entiers nn peut-on en déduire le quotient et le reste de la division euclidienne de n2+5n+9n^2+5n+9 par n+2n+2 ?
  2. Effectuer cette division pour n=0n=0 et pour n=1n=1.
  3. Déterminer les entiers naturels nn tels que le reste de la division euclidienne de 2n+312n+31 par n+4n+4 soit égal à 5.
Voir le corrigé
  1. (n+2)(n+3)+3=n2+5n+6+3=n2+5n+9(n+2)(n+3)+3=n^2+5n+6+3=n^2+5n+9. L'écriture est la division euclidienne par n+2n+2 si et seulement si 0≤3<n+20\leq3\lt n+2, soit n≥2n\geq2 : alors le quotient est n+3n+3 et le reste 3 (unicité du couple). Exemple : n=4n=4 donne 45=6×7+345=6\times7+3.
  2. Pour n=0n=0 : 9=2×4+19=2\times4+1, reste 1. Pour n=1n=1 : 15=3×5+015=3\times5+0, reste 0. Dans les deux cas, 3 n'est pas inférieur au diviseur, donc ce n'est pas le reste.
  3. Si le reste vaut 5, il existe un quotient qq tel que 2n+31=(n+4)q+52n+31=(n+4)q+5, avec 5<n+45\lt n+4, soit n≥2n\geq2. Alors n+4n+4 divise 2n+262n+26, donc aussi 2n+26−2(n+4)=182n+26-2(n+4)=18. Les diviseurs de 18 supérieurs à 5 sont 6, 9 et 18, d'où n∈{2 ;5 ;14}n\in\{2\,;5\,;14\}. Réciproquement : 35=6×5+535=6\times5+5, 41=9×4+541=9\times4+5 et 59=18×3+559=18\times3+5, avec un reste 5 inférieur au diviseur à chaque fois.

Exercice 6 : Raisonner sur les restes : cubes et division par 9

Moyen
  1. Soit n∈Zn\in\mathbb{Z}, écrit n=3q+rn=3q+r avec q∈Zq\in\mathbb{Z} et r∈{0 ;1 ;2}r\in\{0\,;1\,;2\}. Montrer qu'il existe un entier kk tel que n3=9k+r3n^3=9k+r^3.
  2. En déduire que le reste de la division euclidienne de n3n^3 par 9 est 0, 1 ou 8.
  3. Quels restes la division de x3+y3x^3+y^3 par 9 peut-elle donner, pour xx et yy entiers ? L'équation x3+y3=220x^3+y^3=220 a-t-elle des solutions dans Z2\mathbb{Z}^2 ?
Voir le corrigé
  1. Par la formule du cube d'une somme : n3=27q3+27q2r+9qr2+r3=9(3q3+3q2r+qr2)+r3,\begin{aligned}n^3&=27q^3+27q^2r\\&\quad+9qr^2+r^3\\&=9\left(3q^3+3q^2r+qr^2\right)\\&\quad+r^3,\end{aligned} et k=3q3+3q2r+qr2k=3q^3+3q^2r+qr^2 est un entier.
  2. Selon la valeur de rr (disjonction des cas) : r=0r=0 donne n3=9kn^3=9k, reste 0 ; r=1r=1 donne n3=9k+1n^3=9k+1, reste 1 ; r=2r=2 donne n3=9k+8n^3=9k+8, reste 8, car 0≤8<90\leq8\lt9.
  3. x3=9k+sx^3=9k+s et y3=9k′+ty^3=9k^{\prime}+t avec s,t∈{0 ;1 ;8}s,t\in\{0\,;1\,;8\}, donc x3+y3x^3+y^3 a le même reste que s+t∈{0 ;1 ;2 ;8 ;9 ;16}s+t\in\{0\,;1\,;2\,;8\,;9\,;16\} : les restes possibles sont 0, 1, 2, 7 et 8. Or 220=9×24+4220=9\times24+4 : le reste 4 est impossible, donc l'équation x3+y3=220x^3+y^3=220 n'a aucune solution dans Z2\mathbb{Z}^2.

Nombres premiers et décomposition en facteurs premiers : exercices

Pour tester si nn est premier, on essaie les nombres premiers pp tels que p2≤np^2\leq n. Pour montrer qu'une expression n'est pas première, on la factorise en deux facteurs supérieurs à 1. Le nombre de diviseurs positifs se lit sur les exposants de la décomposition.

Exercice 7 : Test de primalité, décomposition et nombre de diviseurs

Facile
  1. Le nombre 523 est-il premier ?
  2. Le nombre 851 est-il premier ?
  3. Décomposer 3 528 en produit de facteurs premiers et donner le nombre de ses diviseurs positifs.
  4. Déterminer le plus petit entier naturel non nul mm tel que 3528m3528m soit le carré d'un entier.
Voir le corrigé
  1. 222=484≤523<529=23222^2=484\leq523\lt529=23^2 : on teste les nombres premiers jusqu'à 19. Par les critères de divisibilité, 523 n'est divisible ni par 2, ni par 3 (somme des chiffres 10), ni par 5. Puis 523=7×74+5=11×47+6=13×40+3=17×30+13=19×27+10523=7\times74+5=11\times47+6=13\times40+3=17\times30+13=19\times27+10. Aucun reste n'est nul : 523 est premier.
  2. 292=841≤851<90029^2=841\leq851\lt900 : on teste jusqu'à 29. Les essais 2, 3, 5, 7, 11, 13, 17 et 19 échouent, puis 851=23×37851=23\times37 : 851 n'est pas premier.
  3. 3528=2×1764=22×882=23×441=23×32×723528=2\times1764=2^2\times882=2^3\times441=2^3\times3^2\times7^2. Le nombre de diviseurs positifs est (3+1)(2+1)(2+1)=36(3+1)(2+1)(2+1)=36.
  4. Un entier naturel non nul est un carré si et seulement si tous les exposants de sa décomposition sont pairs (on double les exposants d'une racine, et on les divise par 2 dans l'autre sens). Dans 3528m3528m, l'exposant de 2 vaut 3 plus celui de mm : pour qu'il soit pair, mm doit être pair, donc m≥2m\geq2. Et m=2m=2 convient : 7056=24×32×72=(22×3×7)2=8427056=2^4\times3^2\times7^2=\left(2^2\times3\times7\right)^2=84^2.

Exercice 8 : Nombres premiers, restes et infinité de premiers

Difficile
  1. Déterminer les nombres premiers pp tels que p+10p+10 et p+20p+20 soient aussi premiers.
  2. Factoriser n3+1n^3+1 par n+1n+1. Pour quels entiers naturels nn le nombre n3+1n^3+1 est-il premier ?
  3. Montrer qu'un nombre premier impair s'écrit 4k+14k+1 ou 4k+34k+3 (k∈Nk\in\mathbb{N}), et que le produit de deux entiers de la forme 4k+14k+1 est encore de cette forme.
  4. On suppose qu'il n'existe qu'un nombre fini de nombres premiers de la forme 4k+34k+3, notés p1,…,pmp_1,\dots,p_m, et l'on pose N=4p1p2⋯pm−1N=4p_1p_2\cdots p_m-1. Montrer que NN a un diviseur premier de la forme 4k+34k+3, puis aboutir à une contradiction.
Indication
Question 1 : raisonner selon le reste de pp dans la division par 3. Question 4 : si tous les facteurs premiers de NN étaient de la forme 4k+14k+1, quel serait le reste de NN dans la division par 4 ?
Voir le corrigé
  1. Écrivons p=3q+rp=3q+r avec r∈{0 ;1 ;2}r\in\{0\,;1\,;2\}. Si r=1r=1, p+20=3(q+7)p+20=3(q+7) est un multiple de 3 strictement supérieur à 3 : il n'est pas premier. Si r=2r=2, p+10=3(q+4)p+10=3(q+4) n'est pas premier pour la même raison. Il reste r=0r=0 : pp est un nombre premier multiple de 3, donc p=3p=3. Réciproquement, 3, 13 et 23 sont premiers. La seule solution est p=3p=3.
  2. n3+1=(n+1)(n2−n+1)n^3+1=(n+1)(n^2-n+1) (développer pour vérifier). Pour n=0n=0, n3+1=1n^3+1=1 n'est pas premier ; pour n=1n=1, il vaut 2, premier. Pour n≥2n\geq2, n+1≥3n+1\geq3 et n2−n+1=n(n−1)+1≥3n^2-n+1=n(n-1)+1\geq3 : n3+1n^3+1 est le produit de deux entiers supérieurs à 1, il n'est pas premier. Seul n=1n=1 convient.
  3. Un entier s'écrit 4k+r4k+r avec r∈{0 ;1 ;2 ;3}r\in\{0\,;1\,;2\,;3\} ; 4k4k et 4k+24k+2 sont pairs, donc un premier impair est de la forme 4k+14k+1 ou 4k+34k+3. Ensuite (4k+1)(4k′+1)=4(4kk′+k+k′)+1(4k+1)(4k^{\prime}+1)=4(4kk^{\prime}+k+k^{\prime})+1. Par récurrence sur le nombre de facteurs, tout produit d'entiers de la forme 4k+14k+1 est de la forme 4k+14k+1.
  4. N=4(p1⋯pm−1)+3N=4(p_1\cdots p_m-1)+3 est de la forme 4k+34k+3, donc impair, et N≥4×3−1=11N\geq4\times3-1=11, car 3 est l'un des pip_i. Ses facteurs premiers sont impairs ; s'ils étaient tous de la forme 4k+14k+1, leur produit NN le serait aussi (question 3), alors que son reste par 4 est 3 (unicité du reste). Donc NN a un diviseur premier qq de la forme 4k+34k+3, qui est l'un des pip_i. Alors qq divise NN et 4p1⋯pm4p_1\cdots p_m, donc leur différence 1 : impossible. Il existe donc une infinité de nombres premiers de la forme 4k+34k+3.

PGCD et PPCM : exercices

L'algorithme d'Euclide donne le PGCD comme dernier reste non nul ; les diviseurs communs sont les diviseurs du PGCD, et (a∧b)(a∨b)=∣ab∣(a\wedge b)(a\vee b)=|ab|. Avec les décompositions, on prend le plus petit exposant pour le PGCD et le plus grand pour le PPCM. Pour des expressions en nn, on remplace a∧ba\wedge b par b∧(a−kb)b\wedge(a-kb), qui a les mêmes diviseurs communs.

Exercice 9 : Algorithme d’Euclide, diviseurs communs et PPCM

Facile
  1. Calculer 3289∧11733289\wedge1173 par l'algorithme d'Euclide.
  2. Donner l'ensemble des diviseurs communs de 3 289 et 1 173 dans Z\mathbb{Z}.
  3. En déduire 3289∨11733289\vee1173.
  4. Calculer (−3289)∧1173(-3289)\wedge1173 et 6578∧23466578\wedge2346.
Voir le corrigé
  1. Divisions successives : 3289=1173×2+9431173=943×1+230943=230×4+23230=23×10+0\begin{aligned}3289&=1173\times2+943\\1173&=943\times1+230\\943&=230\times4+23\\230&=23\times10+0\end{aligned} Le dernier reste non nul est 23 : 3289∧1173=233289\wedge1173=23.
  2. Les diviseurs communs sont les diviseurs de 23, nombre premier : {−23 ;−1 ;1 ;23}\{-23\,;-1\,;1\,;23\}.
  3. 3289=23×1433289=23\times143 et 1173=23×511173=23\times51, donc 3289∨1173=3289×117323=143×1173=1677393289\vee1173=\dfrac{3289\times1173}{23}=143\times1173=167739.
  4. (−3289)∧1173=3289∧1173=23(-3289)\wedge1173=3289\wedge1173=23, car le PGCD ne dépend que des valeurs absolues. 6578=2×32896578=2\times3289 et 2346=2×11732346=2\times1173, donc 6578∧2346=2×23=466578\wedge2346=2\times23=46.

Exercice 10 : PGCD et PPCM par la décomposition en facteurs premiers

Moyen
  1. Décomposer 2 250 et 1 320, puis calculer 2250∧13202250\wedge1320 et 2250∨13202250\vee1320. Vérifier que leur produit vaut 2250×13202250\times1320.
  2. Déterminer les couples (a ;b)(a\,;b) d'entiers naturels tels que a≤ba\leq b, a∧b=10a\wedge b=10 et a∨b=1300a\vee b=1300.
  3. Parmi ces couples, lequel vérifie a+b=230a+b=230 ?
Indication
Question 2 : pour chaque nombre premier, les exposants dans aa et bb sont le plus petit et le plus grand exposant lus dans 10 et 1 300.
Voir le corrigé
  1. 2250=2×32×532250=2\times3^2\times5^3 et 1320=23×3×5×111320=2^3\times3\times5\times11. Plus petits exposants : 2250∧1320=2×3×5=302250\wedge1320=2\times3\times5=30. Plus grands exposants : 2250∨1320=23×32×53×11=990002250\vee1320=2^3\times3^2\times5^3\times11=99000. Contrôle : 30×99000=2970000=2250×132030\times99000=2970000=2250\times1320.
  2. 10=2×510=2\times5 et 1300=22×52×131300=2^2\times5^2\times13. Pour 2, les exposants de aa et bb sont 1 et 2 dans un ordre ou dans l'autre ; de même pour 5 ; pour 13, ils sont 0 et 1. Aucun autre nombre premier ne divise aa ou bb, puisque aa et bb divisent 1 300. Cela donne 2×2×2=82\times2\times2=8 couples ordonnés, donc 4 avec a≤ba\leq b : (a ;b)∈{(10 ;1300) ;(20 ;650) ;(50 ;260) ;(100 ;130)}.\begin{aligned}(a\,;b)\in\{&(10\,;1300)\,;\\&(20\,;650)\,;\\&(50\,;260)\,;\\&(100\,;130)\}.\end{aligned} Contrôle : 100=22×52100=2^2\times5^2 et 130=2×5×13130=2\times5\times13 donnent bien 100∧130=10100\wedge130=10 et 100∨130=1300100\vee130=1300.
  3. 100+130=230100+130=230 : c'est le couple (100 ;130)(100\,;130). Les autres sommes valent 1 310, 670 et 310.

Exercice 11 : PGCD de deux expressions dépendant de n

Moyen
Dans cet exercice, nn est un entier naturel.
  1. Montrer que (4n+9)∧(n+1)=(n+1)∧5(4n+9)\wedge(n+1)=(n+1)\wedge5. En déduire les valeurs possibles de (4n+9)∧(n+1)(4n+9)\wedge(n+1).
  2. Pour quels entiers nn ce PGCD vaut-il 5 ?
  3. On pose A=n2+2n+6A=n^2+2n+6 et B=n+3B=n+3. Montrer que A∧B=B∧9A\wedge B=B\wedge9, puis déterminer A∧BA\wedge B selon les valeurs de nn.
Voir le corrigé
  1. 4n+9=4(n+1)+54n+9=4(n+1)+5. Un diviseur commun de 4n+94n+9 et n+1n+1 divise (4n+9)−4(n+1)=5(4n+9)-4(n+1)=5 ; un diviseur commun de n+1n+1 et 5 divise 4(n+1)+54(n+1)+5. Les deux couples ont donc les mêmes diviseurs communs, et (4n+9)∧(n+1)=(n+1)∧5(4n+9)\wedge(n+1)=(n+1)\wedge5. Ce PGCD est un diviseur positif de 5 : il vaut 1 ou 5.
  2. Il vaut 5 si et seulement si 5∣n+15\mid n+1, c'est-à-dire n=5j+4n=5j+4 avec j∈Nj\in\mathbb{N} : n∈{4 ;9 ;14 ;… }n\in\{4\,;9\,;14\,;\dots\}. Contrôle : n=9n=9 donne 45∧10=545\wedge10=5, et n=3n=3 donne 21∧4=121\wedge4=1.
  3. (n+3)(n−1)=n2+2n−3(n+3)(n-1)=n^2+2n-3, donc A=B(n−1)+9A=B(n-1)+9 et, comme à la question 1, A∧B=B∧9A\wedge B=B\wedge9. Les diviseurs positifs de 9 sont 1, 3 et 9 :
    • si 9∣n+39\mid n+3, c'est-à-dire n=9j+6n=9j+6 avec j∈Nj\in\mathbb{N}, alors A∧B=9A\wedge B=9 (par exemple n=6n=6 : 54∧9=954\wedge9=9) ;
    • si 3∣n+33\mid n+3 sans que 9 le divise, c'est-à-dire n=9jn=9j ou n=9j+3n=9j+3, alors A∧B=3A\wedge B=3 (n=0n=0 : 6∧3=36\wedge3=3) ;
    • sinon, c'est-à-dire si nn n'est pas multiple de 3, A∧B=1A\wedge B=1 (n=1n=1 : 9∧4=19\wedge4=1).

Congruences : restes, chiffre des unités et divisibilité

On remplace chaque base par son reste. On cherche ensuite une puissance congrue à 1 (ou à −1-1, ce qui introduit un facteur (−1)q(-1)^q), ou à défaut le cycle des restes. L'exposant se divise par la longueur du cycle ; il ne se réduit jamais modulo nn. Le chiffre des unités est le reste modulo 10. Une divisibilité pour tout nn se démontre par congruences ou par récurrence.

Exercice 12 : Calculer des restes avec les congruences

Facile
Les entiers aa et bb vérifient a≡4 [12]a\equiv4\ [12] et b≡9 [12]b\equiv9\ [12].
  1. Déterminer les restes de a+ba+b, abab et −a-a dans la division euclidienne par 12.
  2. Déterminer les restes de a2−3ba^2-3b et de a3a^3 par 12.
  3. Déterminer le chiffre des unités de 19345+247819^{345}+24^{78}.
Voir le corrigé
  1. Par compatibilité : a+b≡13≡1 [12]a+b\equiv13\equiv1\ [12], reste 1 ; ab≡36=3×12ab\equiv36=3\times12, reste 0, alors que ni aa ni bb n'est multiple de 12 ; −a≡−4≡8 [12]-a\equiv-4\equiv8\ [12], reste 8 (un reste est entre 0 et 11).
  2. a2−3b≡16−27=−11≡1 [12]a^2-3b\equiv16-27=-11\equiv1\ [12], reste 1. a2≡16≡4 [12]a^2\equiv16\equiv4\ [12], donc a3=a2×a≡4×4=16≡4 [12]a^3=a^2\times a\equiv4\times4=16\equiv4\ [12], reste 4.
  3. On travaille modulo 10. 19≡−1 [10]19\equiv-1\ [10] et 345 est impair, donc 19345≡(−1)345=−1≡9 [10]19^{345}\equiv(-1)^{345}=-1\equiv9\ [10]. 24≡4 [10]24\equiv4\ [10] et 42=16≡6 [10]4^2=16\equiv6\ [10], puis 6×6=36≡66\times6=36\equiv6, donc toute puissance de 6 d'exposant non nul est congrue à 6 : 2478≡(42)39≡639≡6 [10]24^{78}\equiv\left(4^2\right)^{39}\equiv6^{39}\equiv6\ [10]. La somme est congrue à 9+6=15≡5 [10]9+6=15\equiv5\ [10] : son chiffre des unités est 5.

Exercice 13 : Reste d’une grande puissance : puissances de 7 modulo 15

Moyen
  1. Déterminer les restes de 717^1, 727^2, 737^3 et 747^4 dans la division par 15.
  2. En déduire le reste de 7n7^n par 15 selon le reste de nn dans la division par 4.
  3. Déterminer les restes de 73057^{305} et de 2210222^{102} par 15.
  4. Déterminer les entiers naturels nn tels que 15 divise 7n+117^n+11.
Voir le corrigé
  1. 71=77^1=7 ; 72=49=3×15+4≡47^2=49=3\times15+4\equiv4 ; 73≡4×7=28≡137^3\equiv4\times7=28\equiv13 ; 74≡13×7=91=6×15+1≡1 [15]7^4\equiv13\times7=91=6\times15+1\equiv1\ [15]. Les restes sont 7, 4, 13 et 1.
  2. Écrivons n=4k+sn=4k+s avec s∈{0 ;1 ;2 ;3}s\in\{0\,;1\,;2\,;3\}. Alors 7n=(74)k×7s≡1k×7s [15]7^n=\left(7^4\right)^k\times7^s\equiv1^k\times7^s\ [15]. Le reste de 7n7^n est 1, 7, 4 ou 13 selon que ss vaut 0, 1, 2 ou 3.
  3. 305=4×76+1305=4\times76+1, donc 7305≡7 [15]7^{305}\equiv7\ [15] : reste 7. 22≡7 [15]22\equiv7\ [15], donc 22102≡710222^{102}\equiv7^{102}, et 102=4×25+2102=4\times25+2 : reste 4.
  4. 15∣7n+11  ⟺  7n≡−11≡4 [15]15\mid7^n+11\iff7^n\equiv-11\equiv4\ [15]. D'après la question 2, cela équivaut à s=2s=2, soit n≡2 [4]n\equiv2\ [4] : n∈{2 ;6 ;10 ;… }n\in\{2\,;6\,;10\,;\dots\}. Contrôle : 72+11=60=15×47^2+11=60=15\times4.

Exercice 14 : Divisibilité pour tout entier n : congruences et récurrence

Difficile
Pour n∈Nn\in\mathbb{N}, on pose An=33n+1+23n+4A_n=3^{3n+1}+2^{3n+4}.
  1. Calculer A0A_0 et A1A_1. Comparer 333^3 et 232^3 modulo 19, puis démontrer avec les congruences que 19 divise AnA_n pour tout n∈Nn\in\mathbb{N}.
  2. Démontrer le même résultat par récurrence, en exprimant Ak+1A_{k+1} à l'aide de AkA_k.
  3. Montrer que AnA_n n'est jamais divisible par 5.
Indication
Question 2 : Ak+1=27×33k+1+8×23k+4A_{k+1}=27\times3^{3k+1}+8\times2^{3k+4} ; remplacer 33k+13^{3k+1} par Ak−23k+4A_k-2^{3k+4}. Question 3 : étudier les restes de 2n2^n et 3n3^n modulo 5.
Voir le corrigé
  1. A0=3+16=19A_0=3+16=19 et A1=81+128=209=19×11A_1=81+128=209=19\times11. De plus 33=27=19+8≡8=23 [19]3^3=27=19+8\equiv8=2^3\ [19]. Donc An=3×27n+16×8n≡3×8n+16×8n=19×8n≡0 [19].\begin{aligned}A_n&=3\times27^n+16\times8^n\\&\equiv3\times8^n+16\times8^n\\&=19\times8^n\equiv0\ [19].\end{aligned} Ainsi 19 divise AnA_n pour tout n∈Nn\in\mathbb{N}.
  2. On raisonne par récurrence ; notons P(n)P(n) : « 19 divise AnA_n ».
    Initialisation. A0=19A_0=19, donc P(0)P(0) est vraie.
    Hérédité. Soit k∈Nk\in\mathbb{N} tel que P(k)P(k) soit vraie : Ak=19qA_k=19q avec q∈Zq\in\mathbb{Z}. Alors 33k+1=19q−23k+43^{3k+1}=19q-2^{3k+4} et Ak+1=27×33k+1+8×23k+4=27(19q−23k+4)+8×23k+4=19×27q−19×23k+4=19(27q−23k+4).\begin{aligned}A_{k+1}&=27\times3^{3k+1}\\&\quad+8\times2^{3k+4}\\&=27\left(19q-2^{3k+4}\right)\\&\quad+8\times2^{3k+4}\\&=19\times27q\\&\quad-19\times2^{3k+4}\\&=19\left(27q-2^{3k+4}\right).\end{aligned} Comme 27q−23k+427q-2^{3k+4} est un entier, P(k+1)P(k+1) est vraie.
    Conclusion. Par récurrence, 19 divise AnA_n pour tout n∈Nn\in\mathbb{N}.
  3. Modulo 5 : 27≡227\equiv2 et 8≡38\equiv3, donc An≡3×2n+16×3n≡3×2n+3n [5]A_n\equiv3\times2^n+16\times3^n\equiv3\times2^n+3^n\ [5]. On a 24=16≡12^4=16\equiv1 et 34=81≡1 [5]3^4=81\equiv1\ [5] : on raisonne selon le reste ss de nn dans la division par 4, avec 2s2^s valant 1, 2, 4, 3 et 3s3^s valant 1, 3, 4, 2 modulo 5 pour s=0s=0, 1, 2, 3. On obtient An≡3+1=4A_n\equiv3+1=4, 6+3≡46+3\equiv4, 12+4≡112+4\equiv1 et 9+2≡1 [5]9+2\equiv1\ [5]. Le reste n'est jamais 0 : AnA_n n'est jamais divisible par 5. Contrôle : A0=19A_0=19, A1=209A_1=209, A2=3211A_2=3211.

Équations dans Z/nZ : exercices

Dans Z/nZ\mathbb{Z}/n\mathbb{Z}, on résout une équation en testant les nn classes modulo n, souvent à l'aide d'une table. Une équation peut avoir plusieurs solutions ou aucune, et un produit peut être nul sans qu'un facteur le soit. Chaque solution c‾\overline{c} donne dans Z\mathbb{Z} les entiers x≡c [n]x\equiv c\ [n].

Exercice 15 : Équations dans Z/10Z et Z/5Z, chiffre des unités d’un carré

Moyen
  1. Dresser la table des carrés x2x^2 pour x∈Z/10Zx\in\mathbb{Z}/10\mathbb{Z}. En déduire les chiffres des unités possibles du carré d'un entier naturel. Le nombre 3 257 est-il un carré ?
  2. Résoudre dans Z/10Z\mathbb{Z}/10\mathbb{Z} l'équation 3‾x+7‾=2‾\overline{3}x+\overline{7}=\overline{2}.
  3. Résoudre dans Z/10Z\mathbb{Z}/10\mathbb{Z} l'équation 4‾x=6‾\overline{4}x=\overline{6}, puis en déduire les entiers xx tels que 4x≡6 [10]4x\equiv6\ [10].
  4. Résoudre dans Z/10Z\mathbb{Z}/10\mathbb{Z} l'équation x2+x=0‾x^2+x=\overline{0}. Combien a-t-elle de solutions ?
  5. Dresser la table de multiplication de Z/5Z\mathbb{Z}/5\mathbb{Z}. En déduire que, pour toute classe a‾≠0‾\overline{a}\neq\overline{0} de Z/5Z\mathbb{Z}/5\mathbb{Z}, il existe une classe b‾\overline{b} telle que a‾×b‾=1‾\overline{a}\times\overline{b}=\overline{1}. Est-ce le cas pour 2‾\overline{2} dans Z/10Z\mathbb{Z}/10\mathbb{Z} ?
Voir le corrigé
  1. On calcule k2k^2 modulo 10 pour k=0,…,9k=0,\dots,9 :
    xx0‾\overline{0}1‾\overline{1}2‾\overline{2}3‾\overline{3}4‾\overline{4}
    x2x^20‾\overline{0}1‾\overline{1}4‾\overline{4}9‾\overline{9}6‾\overline{6}
    xx5‾\overline{5}6‾\overline{6}7‾\overline{7}8‾\overline{8}9‾\overline{9}
    x2x^25‾\overline{5}6‾\overline{6}9‾\overline{9}4‾\overline{4}1‾\overline{1}
    Le chiffre des unités d'un entier naturel est son reste modulo 10. Celui d'un carré se lit donc dans la table : 0, 1, 4, 5, 6 ou 9, jamais 2, 3, 7 ou 8. Le nombre 3 257 se termine par 7 : ce n'est pas un carré.
  2. On ajoute 3‾\overline{3} aux deux membres (7‾+3‾=0‾\overline{7}+\overline{3}=\overline{0}) : l'équation équivaut à 3‾x=5‾\overline{3}x=\overline{5}. Les produits 3‾×k‾\overline{3}\times\overline{k} pour k=0,…,9k=0,\dots,9 sont 0‾\overline{0}, 3‾\overline{3}, 6‾\overline{6}, 9‾\overline{9}, 2‾\overline{2}, 5‾\overline{5}, 8‾\overline{8}, 1‾\overline{1}, 4‾\overline{4}, 7‾\overline{7} : seule x=5‾x=\overline{5} convient. Contrôle : 3×5+7=22≡2 [10]3\times5+7=22\equiv2\ [10].
  3. Les produits 4‾×k‾\overline{4}\times\overline{k} sont 0‾\overline{0}, 4‾\overline{4}, 8‾\overline{8}, 2‾\overline{2}, 6‾\overline{6}, 0‾\overline{0}, 4‾\overline{4}, 8‾\overline{8}, 2‾\overline{2}, 6‾\overline{6} : 4‾x=6‾  ⟺  x=4‾\overline{4}x=\overline{6}\iff x=\overline{4} ou x=9‾x=\overline{9}. Dans Z\mathbb{Z} : 4x≡6 [10]  ⟺  x≡4 [10]4x\equiv6\ [10]\iff x\equiv4\ [10] ou x≡9 [10]x\equiv9\ [10]. Contrôle : 4×9=36≡6 [10]4\times9=36\equiv6\ [10].
  4. x2+x=x(x+1‾)x^2+x=x(x+\overline{1}). En testant les dix classes : 0‾×1‾=0‾\overline{0}\times\overline{1}=\overline{0}, 4‾×5‾=20‾=0‾\overline{4}\times\overline{5}=\overline{20}=\overline{0}, 5‾×6‾=30‾=0‾\overline{5}\times\overline{6}=\overline{30}=\overline{0}, 9‾×10‾=0‾\overline{9}\times\overline{10}=\overline{0}, et les six autres produits ne sont pas nuls (par exemple 2‾×3‾=6‾\overline{2}\times\overline{3}=\overline{6}). Les solutions sont 0‾\overline{0}, 4‾\overline{4}, 5‾\overline{5} et 9‾\overline{9} : quatre solutions pour une équation de degré 2, car dans Z/10Z\mathbb{Z}/10\mathbb{Z} un produit peut être nul sans qu'aucun facteur ne le soit.
  5. Chaque produit est calculé modulo 5 :
    ×\times0‾\overline{0}1‾\overline{1}2‾\overline{2}3‾\overline{3}4‾\overline{4}
    0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}
    1‾\overline{1}0‾\overline{0}1‾\overline{1}2‾\overline{2}3‾\overline{3}4‾\overline{4}
    2‾\overline{2}0‾\overline{0}2‾\overline{2}4‾\overline{4}1‾\overline{1}3‾\overline{3}
    3‾\overline{3}0‾\overline{0}3‾\overline{3}1‾\overline{1}4‾\overline{4}2‾\overline{2}
    4‾\overline{4}0‾\overline{0}4‾\overline{4}3‾\overline{3}2‾\overline{2}1‾\overline{1}
    Sur chaque ligne d'une classe non nulle, 1‾\overline{1} apparaît une fois : 1‾×1‾=1‾\overline{1}\times\overline{1}=\overline{1}, 2‾×3‾=6‾=1‾\overline{2}\times\overline{3}=\overline{6}=\overline{1}, 3‾×2‾=1‾\overline{3}\times\overline{2}=\overline{1} et 4‾×4‾=16‾=1‾\overline{4}\times\overline{4}=\overline{16}=\overline{1}. Dans Z/10Z\mathbb{Z}/10\mathbb{Z}, au contraire, 2‾×k‾=2k‾\overline{2}\times\overline{k}=\overline{2k} : si 2k=10q+r2k=10q+r, le reste r=2k−10qr=2k-10q est pair, donc jamais égal à 1. Aucune classe b‾\overline{b} ne vérifie 2‾×b‾=1‾\overline{2}\times\overline{b}=\overline{1} dans Z/10Z\mathbb{Z}/10\mathbb{Z}.

Trouver l’erreur dans une copie

Chaque erreur se repère en revenant à une condition du cours. Un reste est compris entre 0 et b−1b-1, et une congruence ne se simplifie pas en 1re année. L'exposant d'une puissance ne se réduit pas modulo nn ; dans Z/nZ\mathbb{Z}/n\mathbb{Z}, un produit nul n'impose pas un facteur nul.

Exercice 16 : Trouver les erreurs : reste négatif, simplification, exposant

Moyen
Un élève a écrit les quatre affirmations suivantes. Pour chacune, trouver l'erreur et écrire une réponse correcte.
  1. « −29=4×(−7)−1-29=4\times(-7)-1, donc le reste de la division euclidienne de −29-29 par 4 est −1-1. »
  2. « 6x≡6 [9]6x\equiv6\ [9], donc x≡1 [9]x\equiv1\ [9]. »
  3. « 14≡4 [5]14\equiv4\ [5], donc 314≡34≡1 [5]3^{14}\equiv3^4\equiv1\ [5]. »
  4. « Dans Z/8Z\mathbb{Z}/8\mathbb{Z}, 2‾×4‾=0‾\overline{2}\times\overline{4}=\overline{0}, donc 2‾=0‾\overline{2}=\overline{0} ou 4‾=0‾\overline{4}=\overline{0}. »
Voir le corrigé
  1. L'égalité est juste, mais −1<0-1\lt0 : ce n'est pas une division euclidienne. On écrit −29=4×(−8)+3-29=4\times(-8)+3 avec 0≤3<40\leq3\lt4 : le reste est 3.
  2. On ne simplifie pas une congruence par un facteur. 6x≡6 [9]6x\equiv6\ [9] signifie 9∣6(x−1)9\mid6(x-1), soit 6(x−1)=9m6(x-1)=9m, donc 2(x−1)=3m2(x-1)=3m : 3 divise 2(x−1)2(x-1), et comme 3 est premier et ne divise pas 2, il divise x−1x-1 (propriété du cours : un nombre premier qui divise un produit divise l'un des facteurs). Réciproquement, si x−1=3jx-1=3j, alors 6(x−1)=18j6(x-1)=18j est multiple de 9. Donc 6x≡6 [9]  ⟺  x≡1 [3]  ⟺  x≡16x\equiv6\ [9]\iff x\equiv1\ [3]\iff x\equiv1, 4 ou 7 [9]7\ [9]. Contrôle : 6×4=24≡6 [9]6\times4=24\equiv6\ [9], alors que 4≢1 [9]4\not\equiv1\ [9].
  3. L'exposant ne se réduit pas modulo 5. On a bien 34=81≡1 [5]3^4=81\equiv1\ [5], et 14=4×3+214=4\times3+2, donc 314=(34)3×32≡9≡4 [5]3^{14}=\left(3^4\right)^3\times3^2\equiv9\equiv4\ [5].
  4. Le calcul 2‾×4‾=8‾=0‾\overline{2}\times\overline{4}=\overline{8}=\overline{0} est juste, mais la conclusion est fausse : 2‾≠0‾\overline{2}\neq\overline{0} et 4‾≠0‾\overline{4}\neq\overline{0} dans Z/8Z\mathbb{Z}/8\mathbb{Z}. La règle « un produit est nul si et seulement si l'un des facteurs est nul » vaut dans R\mathbb{R}, pas dans Z/8Z\mathbb{Z}/8\mathbb{Z}.

Questions flash avant le devoir

Sans calculatrice, une seule bonne réponse par question.

Question 1 : Reste d’un entier négatif

Flash
Le reste de la division euclidienne de −38-38 par 7 est :
  1. −3-3
  2. 3
  3. 4
  4. 6
Voir le corrigé
Réponse C : −38=7×(−6)+4-38=7\times(-6)+4 avec 0≤4<70\leq4\lt7. A vient de −38=7×(−5)−3-38=7\times(-5)-3, dont le reste est négatif ; B est le reste de 38.

Question 2 : PPCM à partir du PGCD

Flash
Deux entiers naturels non nuls aa et bb vérifient a∧b=4a\wedge b=4 et ab=240ab=240. Alors a∨ba\vee b vaut :
  1. 60
  2. 240
  3. 960
  4. 4
Voir le corrigé
Réponse A : (a∧b)(a∨b)=ab(a\wedge b)(a\vee b)=ab, donc a∨b=2404=60a\vee b=\frac{240}{4}=60 (par exemple a=12a=12 et b=20b=20). B confond le PPCM et le produit.

Question 3 : Chiffre des unités d’une puissance

Flash
Le chiffre des unités de 91239^{123} est :
  1. 1
  2. 3
  3. 7
  4. 9
Voir le corrigé
Réponse D : 9≡−1 [10]9\equiv-1\ [10], donc 9123≡(−1)123=−1≡9 [10]9^{123}\equiv(-1)^{123}=-1\equiv9\ [10]. A serait juste pour un exposant pair.

Question 4 : Produit nul dans Z/12Z

Flash
Dans Z/12Z\mathbb{Z}/12\mathbb{Z}, lequel de ces produits est égal à 0‾\overline{0} ?
  1. 5‾×7‾\overline{5}\times\overline{7}
  2. 3‾×8‾\overline{3}\times\overline{8}
  3. 2‾×5‾\overline{2}\times\overline{5}
  4. 7‾×7‾\overline{7}\times\overline{7}
Voir le corrigé
Réponse B : 3×8=24=2×123\times8=24=2\times12. Les autres produits valent 35‾=11‾\overline{35}=\overline{11}, 10‾\overline{10} et 49‾=1‾\overline{49}=\overline{1}. Deux classes non nulles peuvent avoir un produit nul.

Problème de synthèse type devoir surveillé

Problème : PGCD, puissances de 5 modulo 9 et une suite d’entiers

Type devoir
Sujet d'entraînement de type devoir surveillé. Durée conseillée : 1 h. Barème sur 20 points. Calculatrice non autorisée.
Partie A : PGCD et PPCM (6 points)
On pose a=9537a=9537 et b=3315b=3315.
  1. (1,5 point) Calculer a∧ba\wedge b par l'algorithme d'Euclide.
  2. (1,5 point) Décomposer aa et bb en produit de facteurs premiers, et retrouver a∧ba\wedge b.
  3. (1 point) Calculer a∨ba\vee b et vérifier que (a∧b)(a∨b)=ab(a\wedge b)(a\vee b)=ab.
  4. (2 points) Déterminer le nombre de diviseurs positifs de aa, puis la liste des diviseurs positifs communs à aa et bb.
Partie B : puissances de 5 modulo 9 (7 points)
  1. (1,5 point) Déterminer les restes de 5k5^k dans la division par 9 pour k∈{0 ;1 ;… ;6}k\in\{0\,;1\,;\dots\,;6\}. En déduire que 56q+s≡5s [9]5^{6q+s}\equiv5^s\ [9] pour tous entiers naturels qq et ss.
  2. (1,5 point) Déterminer le reste de 52505^{250}, puis celui de 2325023^{250}, dans la division par 9.
  3. (2 points) Déterminer les entiers naturels nn tels que 9 divise 5n+45^n+4.
  4. (2 points) Vérifier que 2‾×5‾=1‾\overline{2}\times\overline{5}=\overline{1} dans Z/9Z\mathbb{Z}/9\mathbb{Z}, puis résoudre l'équation 5‾x=4‾\overline{5}x=\overline{4} dans Z/9Z\mathbb{Z}/9\mathbb{Z}. En déduire les entiers xx tels que 5x≡4 [9]5x\equiv4\ [9].
Partie C : une suite d'entiers (7 points)
On considère la suite (un)(u_n) définie par u0=1u_0=1 et un+1=3un+4u_{n+1}=3u_n+4 pour tout n∈Nn\in\mathbb{N}.
  1. (1,5 point) On pose vn=un+2v_n=u_n+2. Montrer que (vn)(v_n) est géométrique, puis que un=3n+1−2u_n=3^{n+1}-2 pour tout n∈Nn\in\mathbb{N}.
  2. (1,5 point) Sans utiliser la question 9, montrer par récurrence que unu_n est un entier impair pour tout n∈Nn\in\mathbb{N}.
  3. (2 points) Montrer que un+1∧un=un∧4u_{n+1}\wedge u_n=u_n\wedge4, puis en déduire un+1∧unu_{n+1}\wedge u_n.
  4. (2 points) Déterminer les entiers naturels nn tels que 5 divise unu_n.
Indication
Question 8 : multiplier les deux membres par 2‾\overline{2}. Question 11 : un diviseur commun de un+1u_{n+1} et unu_n divise un+1−3unu_{n+1}-3u_n.
Voir le corrigé
  1. Divisions successives : 9537=3315×2+29073315=2907×1+4082907=408×7+51408=51×8+0\begin{aligned}9537&=3315\times2+2907\\3315&=2907\times1+408\\2907&=408\times7+51\\408&=51\times8+0\end{aligned} Le dernier reste non nul est 51 : a∧b=51a\wedge b=51.
  2. 9537=3×3179=3×11×289=3×11×1729537=3\times3179=3\times11\times289=3\times11\times17^2 ; 3315=5×6633315=5\times663, 663=3×221663=3\times221 et 221=13×17221=13\times17, donc 3315=3×5×13×173315=3\times5\times13\times17. Les nombres premiers communs sont 3 et 17, avec les plus petits exposants 1 et 1 : a∧b=3×17=51a\wedge b=3\times17=51.
  3. Plus grands exposants : a∨b=3×5×11×13×172=619905a\vee b=3\times5\times11\times13\times17^2=619905. Contrôle : 51×619905=3161515551\times619905=31615155 et 9537×3315=316151559537\times3315=31615155.
  4. Les exposants de a=3×11×172a=3\times11\times17^2 sont 1, 1 et 2 : aa a (1+1)(1+1)(2+1)=12(1+1)(1+1)(2+1)=12 diviseurs positifs. Les diviseurs positifs communs sont ceux de a∧b=51=3×17a\wedge b=51=3\times17 : 1, 3, 17 et 51.
  5. 50=15^0=1, 51=55^1=5, 52=25≡75^2=25\equiv7, 53≡35≡85^3\equiv35\equiv8, 54≡40≡45^4\equiv40\equiv4, 55≡20≡25^5\equiv20\equiv2, 56≡10≡1 [9]5^6\equiv10\equiv1\ [9]. Les restes sont 1, 5, 7, 8, 4, 2, 1. Comme 56≡1 [9]5^6\equiv1\ [9], 56q+s=(56)q×5s≡5s [9]5^{6q+s}=\left(5^6\right)^q\times5^s\equiv5^s\ [9].
  6. 250=6×41+4250=6\times41+4, donc 5250≡54≡4 [9]5^{250}\equiv5^4\equiv4\ [9] : reste 4. Comme 23=2×9+5≡5 [9]23=2\times9+5\equiv5\ [9], 23250≡5250≡4 [9]23^{250}\equiv5^{250}\equiv4\ [9] : reste 4 aussi.
  7. 9∣5n+4  ⟺  5n≡−4≡5 [9]9\mid5^n+4\iff5^n\equiv-4\equiv5\ [9]. Écrivons n=6q+sn=6q+s avec 0≤s≤50\leq s\leq5 : 5n≡5s5^n\equiv5^s, et parmi 50,…,555^0,\dots,5^5, seul 515^1 est congru à 5. Donc 9∣5n+4  ⟺  n≡1 [6]9\mid5^n+4\iff n\equiv1\ [6], soit n∈{1 ;7 ;13 ;… }n\in\{1\,;7\,;13\,;\dots\}. Contrôle : 5+4=95+4=9.
  8. 2‾×5‾=10‾=1‾\overline{2}\times\overline{5}=\overline{10}=\overline{1}. Si 5‾x=4‾\overline{5}x=\overline{4}, en multipliant par 2‾\overline{2} : 10‾x=8‾\overline{10}x=\overline{8}, soit x=8‾x=\overline{8}. Réciproquement, 5‾×8‾=40‾=4‾\overline{5}\times\overline{8}=\overline{40}=\overline{4}. L'unique solution est 8‾\overline{8}, et 5x≡4 [9]  ⟺  x≡8 [9]5x\equiv4\ [9]\iff x\equiv8\ [9].
  9. vn+1=un+1+2=3un+6=3(un+2)=3vnv_{n+1}=u_{n+1}+2=3u_n+6=3(u_n+2)=3v_n : (vn)(v_n) est géométrique de raison 3 et de premier terme v0=3v_0=3 (suite auxiliaire). Donc vn=3×3n=3n+1v_n=3\times3^n=3^{n+1} et un=3n+1−2u_n=3^{n+1}-2.
  10. Notons P(n)P(n) : « unu_n est un entier impair ».
    Initialisation. u0=1u_0=1 est impair : P(0)P(0) est vraie.
    Hérédité. Soit k∈Nk\in\mathbb{N} tel que P(k)P(k) soit vraie : uk=2m+1u_k=2m+1 avec m∈Zm\in\mathbb{Z}. Alors uk+1=3(2m+1)+4=2(3m+3)+1u_{k+1}=3(2m+1)+4=2(3m+3)+1 est un entier impair : P(k+1)P(k+1) est vraie.
    Conclusion. Par récurrence, unu_n est un entier impair pour tout n∈Nn\in\mathbb{N}.
  11. un+1=3un+4u_{n+1}=3u_n+4. Un diviseur commun de un+1u_{n+1} et unu_n divise un+1−3un=4u_{n+1}-3u_n=4 ; un diviseur commun de unu_n et 4 divise 3un+43u_n+4. Les deux couples ont les mêmes diviseurs communs : un+1∧un=un∧4u_{n+1}\wedge u_n=u_n\wedge4. Ce PGCD divise 4, donc vaut 1, 2 ou 4 ; comme unu_n est impair, il n'est divisible ni par 2 ni par 4 : un+1∧un=1u_{n+1}\wedge u_n=1.
  12. 5∣un  ⟺  3n+1≡2 [5]5\mid u_n\iff3^{n+1}\equiv2\ [5]. Modulo 5, les puissances 313^1, 323^2, 333^3, 343^4 donnent 3, 4, 2, 1, et 34≡13^4\equiv1 : le reste de 3k3^k ne dépend que du reste de kk par 4, et vaut 2 exactement quand k≡3 [4]k\equiv3\ [4]. Avec k=n+1k=n+1 : n≡2 [4]n\equiv2\ [4], soit n∈{2 ;6 ;10 ;… }n\in\{2\,;6\,;10\,;\dots\}. Contrôle : u2=25u_2=25 et u6=2185u_6=2185, qui se termine par 5.
Barème indicatif : partie A, 1,5 + 1,5 + 1 + 2 = 6 points ; partie B, 1,5 + 1,5 + 2 + 2 = 7 points ; partie C, 1,5 + 1,5 + 2 + 2 = 7 points ; total 20.

Pages liées