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 n et résoudre une équation dans Z/nZ. 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+α divise une expression, on écrit l'expression comme un multiple de n+α plus une constante : n+α doit diviser cette constante. Une équation produit dans Z2, le produit cartésienZ×Z, se ramène à une liste de couples de diviseurs.
Exercice 1 : Diviseurs d’un entier relatif
Facile
On considère l'entier a=−234.
Décomposer 234 en produit de facteurs premiers.
Lister les diviseurs positifs de 234.
Combien a a-t-il de diviseurs dans Z ?
Vrai ou faux : a) −18∣a ; b) a∣−18 ; c) 26∣a et 9∣a, donc 26×9∣a ; d) 4∣a.
Voir le corrigé
234=2×117=2×32×13.
Les diviseurs positifs sont les 2α×3β×13γ avec α∈{0;1},β∈{0;1;2},γ∈{0;1}, soit (1+1)(2+1)(1+1)=12 diviseurs : 1, 2, 3, 6, 9, 13, 18, 26, 39, 78, 117, 234.
a et −a=234 ont les mêmes diviseurs ; chaque diviseur positif donne aussi son opposé : a a 24 diviseurs dans Z.
a) Vrai : −234=(−18)×13. b) Faux : un diviseur de −18 a une valeur absolue au plus 18, or ∣a∣=234. c) Vrai ici, car 26×9=234 ; mais le raisonnement est faux en général : 6∣12 et 4∣12, alors que 24∤12. d) Faux : l'exposant de 2 dans 234 est 1, et 4=22.
Exercice 2 : Trouver n pour qu’un entier en divise un autre
Moyen
Dans tout l'exercice, n désigne un entier relatif.
Déterminer les entiers n=1 tels que n−1 divise 4n+11.
Vérifier que n2+10=(n+3)(n−3)+19, puis déterminer les entiers n=−3 tels que n+3 divise n2+10.
En déduire les entiers n pour lesquels n−14n+11 et n+3n2+10 sont tous les deux des entiers relatifs.
Voir le corrigé
4n+11=4(n−1)+15. Comme n−1 divise 4(n−1), la propriété de combinaison donne n−1∣4n+11⟺n−1∣15. Les diviseurs de 15 sont ±1,±3,±5,±15, donc n∈{−14;−4;−2;0} ou n∈{2;4;6;16}. Contrôle : n=16 donne 1575=5.
(n+3)(n−3)=n2−9, donc n2+10=(n+3)(n−3)+19. De même, n+3∣n2+10⟺n+3∣19. 19 est premier, donc n+3∈{−19;−1;1;19}, soit n∈{−22;−4;−2;16}.
On prend l'intersection des deux ensembles : n∈{−4;−2;16}. Contrôle : pour n=−4,−5−5=1 et −126=−26 ; pour n=−2,−33=−1 et 114=14 ; pour n=16, 5 et 19266=14.
Exercice 3 : Équation produit à deux inconnues entières
Moyen
Développer (x+2)(y−3), puis résoudre dans Z2 l'équation xy−3x+2y=13.
Montrer que, pour x et y entiers, xy=2x+3y⟺(x−3)(y−2)=6.
En déduire les couples (x;y) d'entiers naturels non nuls tels que x3+y2=1.
Indication
Question 3 : multiplier par xy. Les facteurs x−3 et y−2 peuvent être négatifs, mais x−3≥−2 et y−2≥−1.
Voir le corrigé
(x+2)(y−3)=xy−3x+2y−6, donc l'équation équivaut à (x+2)(y−3)=7. Les entiers x+2 et y−3 forment un couple de diviseurs de 7 dont le produit vaut 7 : (1;7),(7;1),(−1;−7),(−7;−1). Les solutions sont (−1;10),(5;4),(−3;−4) et (−9;2). Contrôle : 5×4−15+8=13.
(x−3)(y−2)=xy−2x−3y+6, donc (x−3)(y−2)=6⟺xy−2x−3y=0⟺xy=2x+3y.
Pour x,y∈N∗, on multiplie par xy=0 :x3+y2=1⟺3y+2x=xy⟺(x−3)(y−2)=6. Comme x≥1 et y≥1,x−3≥−2 et y−2≥−1. Un produit positif à facteurs négatifs exigerait x−3∈{−2;−1} et y−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) est l'un des couples (1;6),(2;3),(3;2),(6;1), d'où les solutions (x;y) :(4;8),(5;5),(6;4) et (9;3). Contrôle : 93+32=31+32=1.
Division euclidienne et restes : exercices
Pour a∈Z et b∈N∗, on écrit a=bq+r et l'on vérifie toujours 0≤r<b : un reste n'est jamais négatif. Quand les nombres dépendent de n, la condition r<b impose une condition sur n. Pour une propriété de tous les entiers, on raisonne selon les restes possibles.
Exercice 4 : Division euclidienne avec des entiers négatifs
Facile
Effectuer la division euclidienne de 345 par 17, puis celle de −345 par 17.
Écrire 345=(−17)q+r avec 0≤r<17.
Le reste de la division euclidienne d'un entier a par 11 est 6. Déterminer les restes de −a, de a+27 et de 3a dans la division par 11.
Déterminer les entiers relatifs a dont le quotient dans la division euclidienne par 7 est −4.
Voir le corrigé
345=17×20+5 avec 0≤5<17 : quotient 20, reste 5. Donc −345=17×(−20)−5=17×(−21)+12, avec 0≤12<17 : quotient −21, reste 12, et non −5.
345=(−17)×(−20)+5 : q=−20 et r=5.
a=11q+6 avec q∈Z. Alors −a=11(−q)−6=11(−q−1)+5 : reste 5. a+27=11q+33=11(q+3)+0 : reste 0, donc 11 divise a+27.3a=33q+18=11(3q+1)+7 : reste 7. Chaque fois, le reste obtenu est bien compris entre 0 et 10.
a=7×(−4)+r avec r∈{0;1;…;6}, donc −28≤a≤−22 :a est l'un des sept entiers −28,−27,−26,−25,−24,−23,−22.
Exercice 5 : Division euclidienne dont les termes dépendent de n
Moyen
Dans cet exercice, n est un entier naturel.
Vérifier que n2+5n+9=(n+2)(n+3)+3. Pour quels entiers n peut-on en déduire le quotient et le reste de la division euclidienne de n2+5n+9 par n+2 ?
Effectuer cette division pour n=0 et pour n=1.
Déterminer les entiers naturels n tels que le reste de la division euclidienne de 2n+31 par n+4 soit égal à 5.
Voir le corrigé
(n+2)(n+3)+3=n2+5n+6+3=n2+5n+9. L'écriture est la division euclidienne par n+2 si et seulement si 0≤3<n+2, soit n≥2 : alors le quotient est n+3 et le reste 3 (unicité du couple). Exemple : n=4 donne 45=6×7+3.
Pour n=0 :9=2×4+1, reste 1. Pour n=1 :15=3×5+0, reste 0. Dans les deux cas, 3 n'est pas inférieur au diviseur, donc ce n'est pas le reste.
Si le reste vaut 5, il existe un quotient q tel que 2n+31=(n+4)q+5, avec 5<n+4, soit n≥2. Alors n+4 divise 2n+26, donc aussi 2n+26−2(n+4)=18. Les diviseurs de 18 supérieurs à 5 sont 6, 9 et 18, d'où n∈{2;5;14}. Réciproquement : 35=6×5+5,41=9×4+5 et 59=18×3+5, avec un reste 5 inférieur au diviseur à chaque fois.
Exercice 6 : Raisonner sur les restes : cubes et division par 9
Moyen
Soit n∈Z, écrit n=3q+r avec q∈Z et r∈{0;1;2}. Montrer qu'il existe un entier k tel que n3=9k+r3.
En déduire que le reste de la division euclidienne de n3 par 9 est 0, 1 ou 8.
Quels restes la division de x3+y3 par 9 peut-elle donner, pour x et y entiers ? L'équation x3+y3=220 a-t-elle des solutions dans Z2 ?
Voir le corrigé
Par la formule du cube d'une somme :
n3=27q3+27q2r+9qr2+r3=9(3q3+3q2r+qr2)+r3,
et k=3q3+3q2r+qr2 est un entier.
Selon la valeur de r (disjonction des cas) : r=0 donne n3=9k, reste 0 ; r=1 donne n3=9k+1, reste 1 ; r=2 donne n3=9k+8, reste 8, car 0≤8<9.
x3=9k+s et y3=9k′+t avec s,t∈{0;1;8}, donc x3+y3 a le même reste que s+t∈{0;1;2;8;9;16} : les restes possibles sont 0, 1, 2, 7 et 8. Or 220=9×24+4 : le reste 4 est impossible, donc l'équation x3+y3=220 n'a aucune solution dans Z2.
Nombres premiers et décomposition en facteurs premiers : exercices
Pour tester si n est premier, on essaie les nombres premiers p tels que p2≤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
Le nombre 523 est-il premier ?
Le nombre 851 est-il premier ?
Décomposer 3 528 en produit de facteurs premiers et donner le nombre de ses diviseurs positifs.
Déterminer le plus petit entier naturel non nul m tel que 3528m soit le carré d'un entier.
Voir le corrigé
222=484≤523<529=232 : 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+10. Aucun reste n'est nul : 523 est premier.
292=841≤851<900 : on teste jusqu'à 29. Les essais 2, 3, 5, 7, 11, 13, 17 et 19 échouent, puis 851=23×37 : 851 n'est pas premier.
3528=2×1764=22×882=23×441=23×32×72. Le nombre de diviseurs positifs est (3+1)(2+1)(2+1)=36.
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 3528m, l'exposant de 2 vaut 3 plus celui de m : pour qu'il soit pair, m doit être pair, donc m≥2. Et m=2 convient : 7056=24×32×72=(22×3×7)2=842.
Exercice 8 : Nombres premiers, restes et infinité de premiers
Difficile
Déterminer les nombres premiers p tels que p+10 et p+20 soient aussi premiers.
Factoriser n3+1 par n+1. Pour quels entiers naturels n le nombre n3+1 est-il premier ?
Montrer qu'un nombre premier impair s'écrit 4k+1 ou 4k+3 (k∈N), et que le produit de deux entiers de la forme 4k+1 est encore de cette forme.
On suppose qu'il n'existe qu'un nombre fini de nombres premiers de la forme 4k+3, notés p1,…,pm, et l'on pose N=4p1p2⋯pm−1. Montrer que N a un diviseur premier de la forme 4k+3, puis aboutir à une contradiction.
Indication
Question 1 : raisonner selon le reste de p dans la division par 3. Question 4 : si tous les facteurs premiers de N étaient de la forme 4k+1, quel serait le reste de N dans la division par 4 ?
Voir le corrigé
Écrivons p=3q+r avec r∈{0;1;2}. Si r=1,p+20=3(q+7) est un multiple de 3 strictement supérieur à 3 : il n'est pas premier. Si r=2,p+10=3(q+4) n'est pas premier pour la même raison. Il reste r=0 :p est un nombre premier multiple de 3, donc p=3. Réciproquement, 3, 13 et 23 sont premiers. La seule solution est p=3.
n3+1=(n+1)(n2−n+1) (développer pour vérifier). Pour n=0,n3+1=1 n'est pas premier ; pour n=1, il vaut 2, premier. Pour n≥2,n+1≥3 et n2−n+1=n(n−1)+1≥3 : n3+1 est le produit de deux entiers supérieurs à 1, il n'est pas premier. Seul n=1 convient.
Un entier s'écrit 4k+r avec r∈{0;1;2;3} ;4k et 4k+2 sont pairs, donc un premier impair est de la forme 4k+1 ou 4k+3. Ensuite (4k+1)(4k′+1)=4(4kk′+k+k′)+1. Par récurrence sur le nombre de facteurs, tout produit d'entiers de la forme 4k+1 est de la forme 4k+1.
N=4(p1⋯pm−1)+3 est de la forme 4k+3, donc impair, et N≥4×3−1=11, car 3 est l'un des pi. Ses facteurs premiers sont impairs ; s'ils étaient tous de la forme 4k+1, leur produit N le serait aussi (question 3), alors que son reste par 4 est 3 (unicité du reste). Donc N a un diviseur premier q de la forme 4k+3, qui est l'un des pi. Alors q divise N et 4p1⋯pm, donc leur différence 1 : impossible. Il existe donc une infinité de nombres premiers de la forme 4k+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∣. Avec les décompositions, on prend le plus petit exposant pour le PGCD et le plus grand pour le PPCM. Pour des expressions en n, on remplace a∧b par b∧(a−kb), qui a les mêmes diviseurs communs.
Exercice 9 : Algorithme d’Euclide, diviseurs communs et PPCM
Facile
Calculer 3289∧1173 par l'algorithme d'Euclide.
Donner l'ensemble des diviseurs communs de 3 289 et 1 173 dans Z.
En déduire 3289∨1173.
Calculer (−3289)∧1173 et 6578∧2346.
Voir le corrigé
Divisions successives :
32891173943230=1173×2+943=943×1+230=230×4+23=23×10+0
Le dernier reste non nul est 23 : 3289∧1173=23.
Les diviseurs communs sont les diviseurs de 23, nombre premier : {−23;−1;1;23}.
3289=23×143 et 1173=23×51, donc 3289∨1173=233289×1173=143×1173=167739.
(−3289)∧1173=3289∧1173=23, car le PGCD ne dépend que des valeurs absolues. 6578=2×3289 et 2346=2×1173, donc 6578∧2346=2×23=46.
Exercice 10 : PGCD et PPCM par la décomposition en facteurs premiers
Moyen
Décomposer 2 250 et 1 320, puis calculer 2250∧1320 et 2250∨1320. Vérifier que leur produit vaut 2250×1320.
Déterminer les couples (a;b) d'entiers naturels tels que a≤b,a∧b=10 et a∨b=1300.
Parmi ces couples, lequel vérifie a+b=230 ?
Indication
Question 2 : pour chaque nombre premier, les exposants dans a et b sont le plus petit et le plus grand exposant lus dans 10 et 1 300.
Voir le corrigé
2250=2×32×53 et 1320=23×3×5×11. Plus petits exposants : 2250∧1320=2×3×5=30. Plus grands exposants : 2250∨1320=23×32×53×11=99000. Contrôle : 30×99000=2970000=2250×1320.
10=2×5 et 1300=22×52×13. Pour 2, les exposants de a et b 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 a ou b, puisque a et b divisent 1 300. Cela donne 2×2×2=8 couples ordonnés, donc 4 avec a≤b :(a;b)∈{(10;1300);(20;650);(50;260);(100;130)}.
Contrôle : 100=22×52 et 130=2×5×13 donnent bien 100∧130=10 et 100∨130=1300.
100+130=230 : c'est le couple (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, n est un entier naturel.
Montrer que (4n+9)∧(n+1)=(n+1)∧5. En déduire les valeurs possibles de (4n+9)∧(n+1).
Pour quels entiers n ce PGCD vaut-il 5 ?
On pose A=n2+2n+6 et B=n+3. Montrer que A∧B=B∧9, puis déterminer A∧B selon les valeurs de n.
Voir le corrigé
4n+9=4(n+1)+5. Un diviseur commun de 4n+9 et n+1 divise (4n+9)−4(n+1)=5 ; un diviseur commun de n+1 et 5 divise 4(n+1)+5. Les deux couples ont donc les mêmes diviseurs communs, et (4n+9)∧(n+1)=(n+1)∧5. Ce PGCD est un diviseur positif de 5 : il vaut 1 ou 5.
Il vaut 5 si et seulement si 5∣n+1, c'est-à-dire n=5j+4 avec j∈N :n∈{4;9;14;…}. Contrôle : n=9 donne 45∧10=5, et n=3 donne 21∧4=1.
(n+3)(n−1)=n2+2n−3, donc A=B(n−1)+9 et, comme à la question 1, A∧B=B∧9. Les diviseurs positifs de 9 sont 1, 3 et 9 :
si 9∣n+3, c'est-à-dire n=9j+6 avec j∈N, alors A∧B=9 (par exemple n=6 :54∧9=9) ;
si 3∣n+3 sans que 9 le divise, c'est-à-dire n=9j ou n=9j+3, alors A∧B=3 (n=0 :6∧3=3) ;
sinon, c'est-à-dire si n n'est pas multiple de 3, A∧B=1 (n=1 :9∧4=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, ce qui introduit un facteur (−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 n. Le chiffre des unités est le reste modulo 10. Une divisibilité pour tout n se démontre par congruences ou par récurrence.
Exercice 12 : Calculer des restes avec les congruences
Facile
Les entiers a et b vérifient a≡4[12] et b≡9[12].
Déterminer les restes de a+b,ab et −a dans la division euclidienne par 12.
Déterminer les restes de a2−3b et de a3 par 12.
Déterminer le chiffre des unités de 19345+2478.
Voir le corrigé
Par compatibilité : a+b≡13≡1[12], reste 1 ; ab≡36=3×12, reste 0, alors que ni a ni b n'est multiple de 12 ; −a≡−4≡8[12], reste 8 (un reste est entre 0 et 11).
a2−3b≡16−27=−11≡1[12], reste 1. a2≡16≡4[12], donc a3=a2×a≡4×4=16≡4[12], reste 4.
On travaille modulo 10. 19≡−1[10] et 345 est impair, donc 19345≡(−1)345=−1≡9[10]. 24≡4[10] et 42=16≡6[10], puis 6×6=36≡6, donc toute puissance de 6 d'exposant non nul est congrue à 6 : 2478≡(42)39≡639≡6[10]. La somme est congrue à 9+6=15≡5[10] : son chiffre des unités est 5.
Exercice 13 : Reste d’une grande puissance : puissances de 7 modulo 15
Moyen
Déterminer les restes de 71,72,73 et 74 dans la division par 15.
En déduire le reste de 7n par 15 selon le reste de n dans la division par 4.
Déterminer les restes de 7305 et de 22102 par 15.
Déterminer les entiers naturels n tels que 15 divise 7n+11.
Voir le corrigé
71=7 ;72=49=3×15+4≡4 ; 73≡4×7=28≡13 ; 74≡13×7=91=6×15+1≡1[15]. Les restes sont 7, 4, 13 et 1.
Écrivons n=4k+s avec s∈{0;1;2;3}. Alors 7n=(74)k×7s≡1k×7s[15]. Le reste de 7n est 1, 7, 4 ou 13 selon que s vaut 0, 1, 2 ou 3.
305=4×76+1, donc 7305≡7[15] : reste 7. 22≡7[15], donc 22102≡7102, et 102=4×25+2 : reste 4.
15∣7n+11⟺7n≡−11≡4[15]. D'après la question 2, cela équivaut à s=2, soit n≡2[4] :n∈{2;6;10;…}. Contrôle : 72+11=60=15×4.
Exercice 14 : Divisibilité pour tout entier n : congruences et récurrence
Difficile
Pour n∈N, on pose An=33n+1+23n+4.
Calculer A0 et A1. Comparer 33 et 23 modulo 19, puis démontrer avec les congruences que 19 divise An pour tout n∈N.
Démontrer le même résultat par récurrence, en exprimant Ak+1 à l'aide de Ak.
Montrer que An n'est jamais divisible par 5.
Indication
Question 2 : Ak+1=27×33k+1+8×23k+4 ; remplacer 33k+1 par Ak−23k+4. Question 3 : étudier les restes de 2n et 3n modulo 5.
Voir le corrigé
A0=3+16=19 et A1=81+128=209=19×11. De plus 33=27=19+8≡8=23[19]. Donc
An=3×27n+16×8n≡3×8n+16×8n=19×8n≡0[19].
Ainsi 19 divise An pour tout n∈N.
On raisonne par récurrence ; notons P(n) : « 19 divise An ».
Initialisation.A0=19, donc P(0) est vraie.
Hérédité. Soit k∈N tel que P(k) soit vraie : Ak=19q avec q∈Z. Alors 33k+1=19q−23k+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).
Comme 27q−23k+4 est un entier, P(k+1) est vraie.
Conclusion. Par récurrence, 19 divise An pour tout n∈N.
Modulo 5 : 27≡2 et 8≡3, donc An≡3×2n+16×3n≡3×2n+3n[5]. On a 24=16≡1 et 34=81≡1[5] : on raisonne selon le reste s de n dans la division par 4, avec 2s valant 1, 2, 4, 3 et 3s valant 1, 3, 4, 2 modulo 5 pour s=0, 1, 2, 3. On obtient An≡3+1=4,6+3≡4,12+4≡1 et 9+2≡1[5]. Le reste n'est jamais 0 : An n'est jamais divisible par 5. Contrôle : A0=19,A1=209,A2=3211.
Équations dans Z/nZ : exercices
Dans Z/nZ, on résout une équation en testant les nclasses 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 donne dans Z les entiers x≡c[n].
Exercice 15 : Équations dans Z/10Z et Z/5Z, chiffre des unités d’un carré
Moyen
Dresser la table des carrés x2 pour x∈Z/10Z. En déduire les chiffres des unités possibles du carré d'un entier naturel. Le nombre 3 257 est-il un carré ?
Résoudre dans Z/10Z l'équation 3x+7=2.
Résoudre dans Z/10Z l'équation 4x=6, puis en déduire les entiers x tels que 4x≡6[10].
Résoudre dans Z/10Z l'équation x2+x=0. Combien a-t-elle de solutions ?
Dresser la table de multiplication de Z/5Z. En déduire que, pour toute classe a=0 de Z/5Z, il existe une classe b telle que a×b=1. Est-ce le cas pour 2 dans Z/10Z ?
Voir le corrigé
On calcule k2 modulo 10 pour k=0,…,9 :
x
0
1
2
3
4
x2
0
1
4
9
6
x
5
6
7
8
9
x2
5
6
9
4
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é.
On ajoute 3 aux deux membres (7+3=0) : l'équation équivaut à 3x=5. Les produits 3×k pour k=0,…,9 sont 0,3,6,9,2,5,8,1,4,7 : seule x=5 convient. Contrôle : 3×5+7=22≡2[10].
Les produits 4×k sont 0,4,8,2,6,0,4,8,2,6 :4x=6⟺x=4 ou x=9. Dans Z :4x≡6[10]⟺x≡4[10] ou x≡9[10]. Contrôle : 4×9=36≡6[10].
x2+x=x(x+1). En testant les dix classes : 0×1=0,4×5=20=0,5×6=30=0,9×10=0, et les six autres produits ne sont pas nuls (par exemple 2×3=6). Les solutions sont 0,4,5 et 9 : quatre solutions pour une équation de degré 2, car dans Z/10Z un produit peut être nul sans qu'aucun facteur ne le soit.
Chaque produit est calculé modulo 5 :
×
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
Sur chaque ligne d'une classe non nulle, 1 apparaît une fois : 1×1=1,2×3=6=1,3×2=1 et 4×4=16=1. Dans Z/10Z, au contraire, 2×k=2k : si 2k=10q+r, le reste r=2k−10q est pair, donc jamais égal à 1. Aucune classe b ne vérifie 2×b=1 dans Z/10Z.
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−1, et une congruence ne se simplifie pas en 1re année. L'exposant d'une puissance ne se réduit pas modulo n ; dans Z/nZ, 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.
« −29=4×(−7)−1, donc le reste de la division euclidienne de −29 par 4 est −1. »
« 6x≡6[9], donc x≡1[9]. »
« 14≡4[5], donc 314≡34≡1[5]. »
« Dans Z/8Z,2×4=0, donc 2=0 ou 4=0. »
Voir le corrigé
L'égalité est juste, mais −1<0 : ce n'est pas une division euclidienne. On écrit −29=4×(−8)+3 avec 0≤3<4 : le reste est 3.
On ne simplifie pas une congruence par un facteur. 6x≡6[9] signifie 9∣6(x−1), soit 6(x−1)=9m, donc 2(x−1)=3m : 3 divise 2(x−1), et comme 3 est premier et ne divise pas 2, il divise x−1 (propriété du cours : un nombre premier qui divise un produit divise l'un des facteurs). Réciproquement, si x−1=3j, alors 6(x−1)=18j est multiple de 9. Donc 6x≡6[9]⟺x≡1[3]⟺x≡1, 4 ou 7[9]. Contrôle : 6×4=24≡6[9], alors que 4≡1[9].
L'exposant ne se réduit pas modulo 5. On a bien 34=81≡1[5], et 14=4×3+2, donc 314=(34)3×32≡9≡4[5].
Le calcul 2×4=8=0 est juste, mais la conclusion est fausse : 2=0 et 4=0 dans Z/8Z. La règle « un produit est nul si et seulement si l'un des facteurs est nul » vaut dans R, pas dans Z/8Z.
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 par 7 est :
−3
3
4
6
Voir le corrigé
Réponse C : −38=7×(−6)+4 avec 0≤4<7. A vient de −38=7×(−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 a et b vérifient a∧b=4 et ab=240. Alors a∨b vaut :
60
240
960
4
Voir le corrigé
Réponse A : (a∧b)(a∨b)=ab, donc a∨b=4240=60 (par exemple a=12 et b=20). B confond le PPCM et le produit.
Question 3 : Chiffre des unités d’une puissance
Flash
Le chiffre des unités de 9123 est :
1
3
7
9
Voir le corrigé
Réponse D : 9≡−1[10], donc 9123≡(−1)123=−1≡9[10]. A serait juste pour un exposant pair.
Question 4 : Produit nul dans Z/12Z
Flash
Dans Z/12Z, lequel de ces produits est égal à 0 ?
5×7
3×8
2×5
7×7
Voir le corrigé
Réponse B : 3×8=24=2×12. Les autres produits valent 35=11,10 et 49=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=9537 et b=3315.
(1,5 point) Calculer a∧b par l'algorithme d'Euclide.
(1,5 point) Décomposer a et b en produit de facteurs premiers, et retrouver a∧b.
(1 point) Calculer a∨b et vérifier que (a∧b)(a∨b)=ab.
(2 points) Déterminer le nombre de diviseurs positifs de a, puis la liste des diviseurs positifs communs à a et b.
Partie B : puissances de 5 modulo 9 (7 points)
(1,5 point) Déterminer les restes de 5k dans la division par 9 pour k∈{0;1;…;6}. En déduire que 56q+s≡5s[9] pour tous entiers naturels q et s.
(1,5 point) Déterminer le reste de 5250, puis celui de 23250, dans la division par 9.
(2 points) Déterminer les entiers naturels n tels que 9 divise 5n+4.
(2 points) Vérifier que 2×5=1 dans Z/9Z, puis résoudre l'équation 5x=4 dans Z/9Z. En déduire les entiers x tels que 5x≡4[9].
Partie C : une suite d'entiers (7 points)
On considère la suite (un) définie par u0=1 et un+1=3un+4 pour tout n∈N.
(1,5 point) On pose vn=un+2. Montrer que (vn) est géométrique, puis que un=3n+1−2 pour tout n∈N.
(1,5 point) Sans utiliser la question 9, montrer par récurrence que un est un entier impair pour tout n∈N.
(2 points) Montrer que un+1∧un=un∧4, puis en déduire un+1∧un.
(2 points) Déterminer les entiers naturels n tels que 5 divise un.
Indication
Question 8 : multiplier les deux membres par 2. Question 11 : un diviseur commun de un+1 et un divise un+1−3un.
Voir le corrigé
Divisions successives :
953733152907408=3315×2+2907=2907×1+408=408×7+51=51×8+0
Le dernier reste non nul est 51 : a∧b=51.
9537=3×3179=3×11×289=3×11×172 ; 3315=5×663,663=3×221 et 221=13×17, donc 3315=3×5×13×17. Les nombres premiers communs sont 3 et 17, avec les plus petits exposants 1 et 1 : a∧b=3×17=51.
Plus grands exposants : a∨b=3×5×11×13×172=619905. Contrôle : 51×619905=31615155 et 9537×3315=31615155.
Les exposants de a=3×11×172 sont 1, 1 et 2 : a a (1+1)(1+1)(2+1)=12 diviseurs positifs. Les diviseurs positifs communs sont ceux de a∧b=51=3×17 : 1, 3, 17 et 51.
50=1,51=5,52=25≡7,53≡35≡8,54≡40≡4,55≡20≡2,56≡10≡1[9]. Les restes sont 1, 5, 7, 8, 4, 2, 1. Comme 56≡1[9],56q+s=(56)q×5s≡5s[9].
250=6×41+4, donc 5250≡54≡4[9] : reste 4. Comme 23=2×9+5≡5[9], 23250≡5250≡4[9] : reste 4 aussi.
9∣5n+4⟺5n≡−4≡5[9]. Écrivons n=6q+s avec 0≤s≤5 :5n≡5s, et parmi 50,…,55, seul 51 est congru à 5. Donc 9∣5n+4⟺n≡1[6], soit n∈{1;7;13;…}. Contrôle : 5+4=9.
2×5=10=1. Si 5x=4, en multipliant par 2 :10x=8, soit x=8. Réciproquement, 5×8=40=4. L'unique solution est 8, et 5x≡4[9]⟺x≡8[9].
vn+1=un+1+2=3un+6=3(un+2)=3vn : (vn) est géométrique de raison 3 et de premier terme v0=3 (suite auxiliaire). Donc vn=3×3n=3n+1 et un=3n+1−2.
Notons P(n) : « un est un entier impair ».
Initialisation.u0=1 est impair : P(0) est vraie.
Hérédité. Soit k∈N tel que P(k) soit vraie : uk=2m+1 avec m∈Z. Alors uk+1=3(2m+1)+4=2(3m+3)+1 est un entier impair : P(k+1) est vraie.
Conclusion. Par récurrence, un est un entier impair pour tout n∈N.
un+1=3un+4. Un diviseur commun de un+1 et un divise un+1−3un=4 ; un diviseur commun de un et 4 divise 3un+4. Les deux couples ont les mêmes diviseurs communs : un+1∧un=un∧4. Ce PGCD divise 4, donc vaut 1, 2 ou 4 ; comme un est impair, il n'est divisible ni par 2 ni par 4 : un+1∧un=1.
5∣un⟺3n+1≡2[5]. Modulo 5, les puissances 31,32,33,34 donnent 3, 4, 2, 1, et 34≡1 : le reste de 3k ne dépend que du reste de k par 4, et vaut 2 exactement quand k≡3[4]. Avec k=n+1 :n≡2[4], soit n∈{2;6;10;…}. Contrôle : u2=25 et u6=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.