Niveaux : 5 exercices faciles, 9 moyens et 2 difficiles, puis quatre questions flash. Aucun calcul ne demande de calculatrice, comme à l'examen national de sciences mathématiques.
Sommaire11 parties
Nombres premiers entre eux et PGCD : exercices
Méthode : pour montrer que a∧b=1, on cherche une combinaison au+bv=1 (théorème de Bézout), souvent en éliminant n entre deux expressions. Pour un PGCD imposé d, on écrit a=dα et b=dβ avec α∧β=1, puis on traduit les autres conditions sur α et β.
Exercice 1 : Montrer que deux entiers sont premiers entre eux
Facile
Dans tout l'exercice, n désigne un entier relatif.
Calculer 3(4n+3)−4(3n+2). En déduire que 4n+3 et 3n+2 sont premiers entre eux.
Calculer (n+1)(2n+1)−n(2n+3). En déduire que (2n+1)∧(2n+3)=1.
Montrer que (n2+n+1)∧(n+1)=1.
En déduire que la fraction 3n+24n+3 est irréductible pour tout n∈Z, et que n+1n2+n+1 l'est pour tout n=−1.
Voir le corrigé
3(4n+3)−4(3n+2)=12n+9−12n−8=1. Avec u=3 et v=−4, on a (4n+3)u+(3n+2)v=1 : d'après le théorème de Bézout, (4n+3)∧(3n+2)=1.
(n+1)(2n+1)=2n2+3n+1 et n(2n+3)=2n2+3n, donc la différence vaut 1. C'est une égalité de Bézout avec u=n+1 et v=−n :(2n+1)∧(2n+3)=1. Deux entiers impairs consécutifs sont donc toujours premiers entre eux.
n2+n+1=n(n+1)+1, donc 1×(n2+n+1)+(−n)×(n+1)=1. Par Bézout, (n2+n+1)∧(n+1)=1.
Une fraction qp d'entiers, avec q=0, est irréductible si et seulement si p∧q=1. Pour tout entier n,3n+2=0 (sinon n=−32), et la question 1 conclut. Pour n=−1,n+1=0 et la question 3 conclut.
Exercice 2 : Couples d’entiers de PGCD donné
Moyen
Déterminer les couples (a;b) d'entiers naturels tels que a≤b,a+b=480 et a∧b=32.
Déterminer les couples (a;b) d'entiers naturels tels que a≤b,ab=6912 et a∧b=12. Calculer a∨b pour chacun.
Indication
Question 1 : un diviseur commun de α et 15−α divise 15, et réciproquement. Question 2 : dans αβ=48, la puissance 24 ne peut pas être partagée entre α et β.
Voir le corrigé
Par la caractérisation du PGCD, a∧b=32 équivaut à a=32α,b=32β avec α∧β=1. La condition a+b=480 devient α+β=15, et a≤b devient α≤β, soit α≤7. De plus α=0, sinon a∧b=b=480. Les diviseurs communs de α et β=15−α sont ceux de α et 15, donc α∧β=α∧15. Parmi 1, …, 7, les entiers premiers avec 15=3×5 sont 1, 2, 4 et 7. Les couples sont :
(32;448),(64;416),(128;352),(224;256).
Contrôle : 224=25×7 et 256=28, donc 224∧256=25=32.
On écrit a=12α,b=12β,α∧β=1,α≤β. Alors 144αβ=6912, soit αβ=48=24×3. Si 2 divisait α et β, ils ne seraient pas premiers entre eux : 24 est entièrement dans α ou dans β, et de même pour 3 (unicité de la décomposition, théorème fondamental de l'arithmétique). Avec α≤β, il reste (α;β)=(1;48) ou (3;16), d'où (a;b)=(12;576) ou (36;192). Dans les deux cas, a∨b=a∧bab=126912=576. Contrôle : 36=22×32 et 192=26×3 donnent bien 36∧192=22×3=12.
Coefficients de Bézout et théorème de Gauss : exercices
Méthode : les coefficients de Bézout s'obtiennent en remontant les divisions de l'algorithme d'Euclide. Avant d'appliquer Gauss, on vérifie explicitement que le diviseur est premier avec le facteur que l'on écarte ; pour un produit de diviseurs, on vérifie qu'ils sont premiers entre eux.
Exercice 3 : Coefficients de Bézout par l’algorithme d’Euclide
Facile
Calculer 437∧152 par l'algorithme d'Euclide.
Déterminer deux entiers u et v tels que 437u+152v=437∧152.
Vérifier que 437=19×23 et 152=19×8, puis en déduire une égalité de Bézout entre 23 et 8.
Trouver un couple (x;y) d'entiers tel que 437x+152y=57.
L'équation 437x+152y=50 a-t-elle des solutions dans Z2 ?
Voir le corrigé
Divisions successives :
437152133=152×2+133=133×1+19=19×7+0
Le dernier reste non nul est 19 : 437∧152=19.
On remonte : 19=152−133=152−(437−2×152)=3×152−437. Donc u=−1 et v=3 conviennent : −437+456=19.
19×23=437 et 19×8=152. En divisant 437×(−1)+152×3=19 par 19 : 23×(−1)+8×3=1. C'est une égalité de Bézout : 23 et 8 sont premiers entre eux, comme l'annonce la caractérisation du PGCD.
57=3×19 : on multiplie l'égalité de la question 2 par 3, 437×(−3)+152×9=57. Le couple (−3;9) convient : −1311+1368=57.
Non : pour tous entiers x et y, 19 divise 437x+152y, mais 19 ne divise pas 50 (50=19×2+12).
Exercice 4 : Théorème de Gauss et produits
Moyen
Résoudre dans Z2 l'équation 18x=39y.
Soit n∈N. Montrer que 24 divise n(n+1)(n+2)(n+3).
Soient a et b deux entiers relatifs non nuls premiers entre eux. Montrer que (a+b)∧a=1 et (a+b)∧b=1, puis que (a+b)∧ab=1.
Voir le corrigé
On divise par 3=18∧39 : l'équation équivaut à 6x=13y. Si (x;y) est solution, 13 divise 6x et 13∧6=1 (13 est premier et ne divise pas 6) : par le théorème de Gauss, 13 divise x, soit x=13k avec k∈Z. Alors 78k=13y donne y=6k. Réciproquement, 18×13k=234k=39×6k. Les solutions sont les couples (13k;6k),k∈Z.
Notons P=n(n+1)(n+2)(n+3). Parmi quatre entiers consécutifs, deux sont pairs et consécutifs parmi les pairs : 2m et 2m+2, de produit 4m(m+1). Comme m(m+1) est pair, 8 divise ce produit, donc P. Parmi n,n+1,n+2, l'un est multiple de 3 (selon le reste de n par 3), donc 3∣P. Comme 8∧3=1, la propriété du produit de deux diviseurs premiers entre eux donne 24∣P.
Un diviseur commun de a+b et a divise (a+b)−a=b ; un diviseur commun de a et b divise a+b. Donc a+b et a ont les mêmes diviseurs communs que a et b, et (a+b)∧a=a∧b=1. De même (a+b)∧b=1. Enfin, un entier premier avec a et avec b est premier avec ab (propriété du cours, obtenue en multipliant deux égalités de Bézout) : (a+b)∧ab=1.
Équations diophantiennes et systèmes de congruences : exercices
Méthode : pour ax+by=c, on vérifie d'abord que d=a∧b divise c, on divise par d, on trouve une solution particulière, puis on applique Gauss à la différence de deux solutions. Un système de deux congruences se ramène à une telle équation en écrivant l'inconnue de deux façons.
Exercice 5 : Résoudre une équation diophantienne
Moyen
On considère l'équation (E) :47x+18y=3, d'inconnue (x;y)∈Z2.
Justifier que (E) admet des solutions.
À l'aide de l'algorithme d'Euclide, déterminer deux entiers u et v tels que 47u+18v=1.
En déduire une solution particulière de (E), puis résoudre (E).
Déterminer les solutions de (E) telles que 0≤x≤50.
Voir le corrigé
47 est premier et ne divise pas 18, donc 47∧18=1, qui divise 3 : (E) admet des solutions.
Divisions successives :
47181174=18×2+11=11×1+7=7×1+4=4×1+3=3×1+1
On remonte :
1=4−3=2×4−7=2×11−3×7=5×11−3×18=5×47−13×18.
Donc u=5 et v=−13 :235−234=1.
En multipliant par 3, 47×15+18×(−39)=3. On simplifie en retranchant 18 à x et en ajoutant 47 à y :(x0;y0)=(−3;8), car −141+144=3. Si (x;y) est solution, par différence 47(x+3)=−18(y−8). Donc 18 divise 47(x+3) et 18∧47=1 : par Gauss, x+3=18k avec k∈Z, puis 47×18k=−18(y−8) donne y=8−47k. Réciproquement, 47(−3+18k)+18(8−47k)=−141+144=3. Les solutions sont les couples (−3+18k;8−47k), k∈Z.
0≤−3+18k≤50⟺3≤18k≤53⟺k∈{1;2}, car k est entier et 1853<3. On obtient (15;−39) et (33;−86). Contrôle : 47×33=1551 et 18×86=1548.
Exercice 6 : Billets à 35 et à 15 dirhams
Moyen
À l'entrée d'un musée de Rabat, le billet adulte coûte 35 DH et le billet enfant 15 DH. Un groupe a payé 1 000 DH en tout. On note x le nombre d'adultes et y le nombre d'enfants du groupe.
Montrer que 7x+3y=200.
Résoudre dans Z2 l'équation 7x+3y=200.
En déduire toutes les compositions possibles du groupe. Combien y en a-t-il ?
Le groupe compte au moins autant d'adultes que d'enfants : quelles sont les possibilités ? Une recette de 1 004 DH était-elle possible ?
Voir le corrigé
La recette donne 35x+15y=1000 ; on divise par 5 : 7x+3y=200.
7∧3=1 divise 200. Solution particulière : 7×2=14 et 200−14=186=3×62, donc (2;62). Si (x;y) est solution, 7(x−2)=−3(y−62) ; 3 divise 7(x−2) et 3∧7=1, donc par Gauss x=2+3k avec k∈Z, puis 21k=−3(y−62) donne y=62−7k. Réciproquement, 7(2+3k)+3(62−7k)=14+186=200. Les solutions sont les couples (2+3k;62−7k), k∈Z.
Ici x et y sont des entiers naturels : 2+3k≥0⟺k≥0 (car k est entier), et 62−7k≥0⟺k≤8, car 762≈8,9. Il y a 9 compositions, pour k=0,1,…,8 :(2;62),(5;55),(8;48),(11;41),(14;34),(17;27),(20;20),(23;13),(26;6).
x≥y⟺2+3k≥62−7k⟺k≥6 : les possibilités sont (20;20),(23;13) et (26;6). Contrôle : 26×35+6×15=910+90=1000. Une recette de 1 004 DH est impossible : 35x+15y=5(7x+3y) est toujours un multiple de 5, et 1 004 ne l'est pas.
Exercice 7 : Système de congruences : des perles en paquets
Difficile
Un artisan de Fès possède N perles, avec 200≤N≤400. S'il les range par paquets de 9, il en reste 4 ; par paquets de 10, il en reste 3.
Montrer qu'il existe des entiers k et k′ tels que N=9k+4=10k′+3 et 10k′−9k=1.
Résoudre dans Z2 l'équation 10u−9v=1.
En déduire que N≡13[90]. Réciproquement, vérifier que tout entier N≡13[90] laisse les restes 4 et 3 dans les divisions par 9 et par 10.
Par paquets de 7, il reste 3 perles. Résoudre le système formé par N≡13[90] et N≡3[7], puis déterminer N.
Indication
Question 4 : écrire N=13+90t et remplacer 90 et 13 par leurs restes modulo 7 ; 6≡−1[7].
Voir le corrigé
Les restes des divisions euclidiennes de N par 9 et par 10 sont 4 et 3 : N=9k+4 et N=10k′+3 avec k,k′∈N. En égalant, 10k′−9k=4−3=1.
10×1−9×1=1 : (1;1) est solution. Si (u;v) est solution, 10(u−1)=9(v−1). Donc 9 divise 10(u−1) et 9∧10=1 : par Gauss, u=1+9t avec t∈Z, puis 90t=9(v−1) donne v=1+10t. Réciproquement, 10(1+9t)−9(1+10t)=1. Les solutions sont les couples (1+9t;1+10t), t∈Z.
D'après la question 1, (k′;k) est solution de l'équation de la question 2, donc k′=1+9t et N=10(1+9t)+3=13+90t : N≡13[90]. Réciproquement, si N=13+90t, alors N=9(1+10t)+4 et N=10(1+9t)+3, avec des restes 4 et 3 qui sont bien inférieurs à 9 et à 10.
On écrit N=13+90t. Modulo 7, 90=7×12+6≡6 et 13≡6, donc la condition devient 6+6t≡3[7], soit 6t≡4[7]. Comme 6≡−1[7], on obtient −t≡4, c'est-à-dire t≡3[7] :t=3+7s et N=283+630s,s∈Z. Réciproquement, 283=7×40+3 et 630=7×90, donc ces entiers conviennent. Le système équivaut à N≡283[630], et le seul entier de [200;400] est N=283. Contrôle : 283=9×31+4=10×28+3.
Congruences linéaires et inverses dans Z/nZ : exercices
Méthode : dans ax≡b[n], on calcule δ=a∧n. S'il ne divise pas b, il n'y a aucune solution ; sinon, la simplification d'une congruence divise a,b et le module par δ, puis on multiplie par un inverse. Dans Z/pZ avec p premier, toute classe non nulle est inversible et un produit nul a un facteur nul.
Exercice 8 : Simplifier et résoudre des congruences linéaires
Facile
Résoudre dans Z les congruences suivantes.
21x≡9[24]
6x≡5[21]
11x≡7[30]
4x≡12[18]
Voir le corrigé
21∧24=3 divise 9. En simplifiant par 3 (et en divisant le module par 3) : 7x≡3[8]. Comme 7≡−1[8], cela s'écrit −x≡3[8], soit x≡5[8]. Contrôle : 21×5=105=4×24+9.
6∧21=3 ne divise pas 5 : aucune solution. En effet, 6x≡5[21] signifie 6x−21y=5 pour un entier y, et le membre de gauche est multiple de 3.
11∧30=1 et 11×11=121=4×30+1 : 11 est son propre inverse modulo 30. En multipliant par 11, x≡77≡17[30]. Contrôle : 11×17=187=6×30+7.
4x≡4×3[18] et 4∧18=2 : la simplification donne x≡3[9]. Modulo 18, les solutions sont x≡3 et x≡12. Contrôle : 4×12=48=2×18+12.
Exercice 9 : Classes inversibles de Z/15Z et de Z/17Z
Moyen
Déterminer les classes inversibles de Z/15Z et l'inverse de chacune.
Résoudre dans Z/15Z l'équation x2=1.
Montrer que l'équation x2=1 n'a que deux solutions dans Z/17Z. D'où vient la différence avec la question 2 ?
Résoudre dans Z/17Z l'équation 7x+4=2.
Voir le corrigé
a est inversible dans Z/15Z si et seulement si a∧15=1, c'est-à-dire si a n'est multiple ni de 3 ni de 5. Les classes inversibles sont 1,2,4,7,8,11,13,14. Leurs inverses : 2×8=16≡1,7×13=91=6×15+1, et 12,42=16,112=121=8×15+1, 142=196=13×15+1 sont congrus à 1. Donc 2 et 8 sont inverses l'un de l'autre, de même 7 et 13, et 1,4,11,14 sont leurs propres inverses.
On teste les 15 classes. Les carrés de 0,1,…,14 modulo 15 sont 0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1. Les solutions sont 1,4,11 et 14 : quatre solutions.
x2−1=(x−1)(x+1). Comme 17 est premier, un produit nul dans Z/17Z a un facteur nul : x=1 ou x=−1=16. Dans Z/15Z, 15 n'est pas premier et un produit peut être nul sans facteur nul : pour x=4,(4−1)(4+1)=3×5=0.
L'équation équivaut à 7x=2−4=−2=15. Comme 7×5=35=2×17+1, l'inverse de 7 est 5, et x=5×15=75=7, car 75=4×17+7. Contrôle : 7×7+4=53=3×17+2.
Congruences et petit théorème de Fermat : exercices
Méthode : avant d'écrire ap−1≡1[p], on vérifie que p est premier et ne divise pas a. On divise ensuite l'exposant par p−1 : seul le reste compte. Pour un module produit de deux nombres premiers distincts, on travaille modulo chacun, puis on conclut avec le produit de deux diviseurs premiers entre eux.
Exercice 10 : Grandes puissances avec le théorème de Fermat
Facile
Déterminer le reste de la division euclidienne de 71003 par 11.
Déterminer le reste de 3122 par 23.
Montrer que 19 divise 52027−6.
Déterminer les entiers naturels n tels que 11 divise 7n−2.
Voir le corrigé
11 est premier et ne divise pas 7 : par le petit théorème de Fermat, 710≡1[11]. Comme 1003=10×100+3, 71003≡73=343=31×11+2[11] : le reste est 2.
23 est premier et ne divise pas 3, donc 322≡1[23]. Comme 122=22×5+12, 3122≡312[23]. Or 33=27≡4,36≡16 et 312≡256=11×23+3≡3[23] : le reste est 3.
19 est premier et ne divise pas 5, donc 518≡1[19] ;2027=18×112+11 donne 52027≡511[19]. Puis 52=25≡6,54≡36≡−2,58≡4, et 511=58×52×5≡4×6×5=120≡6[19], car 120=6×19+6. Donc 52027−6≡0[19].
Écrivons n=10q+s avec 0≤s≤9. Par Fermat, 7n=(710)q×7s≡7s[11]. Les restes de 7s pour s=0,…,9 sont 1, 7, 5, 2, 3, 10, 4, 6, 9, 8 : seul s=3 donne 2. Donc 11∣7n−2⟺n≡3[10], soit n∈{3;13;23;…}. La question 1 en est un cas : 1003≡3[10].
Exercice 11 : Une divisibilité par 77 pour tout entier
Difficile
Dans tout l'exercice, n désigne un entier relatif.
Montrer que 7 divise n31−n.
Montrer que 11 divise n31−n.
En déduire que 77 divise n31−n pour tout entier n.
Montrer que 230≡1[77], puis déterminer le reste de 22027 dans la division par 77.
Indication
Questions 1 et 2 : 31=6×5+1=10×3+1, et distinguer selon que le nombre premier divise n ou non.
Voir le corrigé
Si 7 divise n, alors n31≡0≡n[7]. Sinon, 7 étant premier, Fermat donne n6≡1[7], et n31=(n6)5×n≡n[7]. Dans les deux cas, 7∣n31−n.
De même avec 11, premier : si 11∣n, les deux membres sont congrus à 0 ; sinon n10≡1[11] et n31=(n10)3×n≡n[11].
7 et 11 sont deux nombres premiers distincts, donc 7∧11=1. Comme ils divisent tous deux n31−n, leur produit 77 le divise. On ne pouvait pas appliquer Fermat modulo 77, qui n'est pas premier.
Pour n=2 :231≡2[77], soit 2×230≡2×1[77]. Comme 2∧77=1, on simplifie par 2 sans changer le module : 230≡1[77]. Ensuite 2027=30×67+17, donc 22027≡217[77]. On calcule 27=128≡51,210=1024=13×77+23≡23, puis 217=210×27≡23×51=1173=15×77+18. Le reste est 18.
Numération en base b et critères de divisibilité : exercices
Méthode : les chiffres en base b sont les restes des divisions successives par b, lus du dernier au premier ; on contrôle en développant akbk+⋯+a0. Une opération se pose en base b avec des retenues égales aux quotients par b. Un critère de divisibilité vient d'une congruence de la base : 10≡1[9],10≡−1[11],1000≡0[8].
Exercice 12 : Conversions entre bases
Facile
Écrire en base 10 l'entier N=101101011(2).
Écrire 363 en base 7.
Écrire 3A7(16) en base 10, puis en base 8.
Justifier que l'on passe de la base 2 à la base 16 en groupant les chiffres par quatre à partir de la droite, puis écrire N en base 16.
Voir le corrigé
Les chiffres 1 sont aux rangs 8, 6, 5, 3, 1 et 0 : N=28+26+25+23+2+1=256+64+32+8+3=363.
Divisions successives par 7 : 363=7×51+6,51=7×7+2,7=7×1+0,1=7×0+1. En lisant les restes de bas en haut, 363=1026(7). Contrôle : 343+0+14+6=363.
A vaut 10, donc 3A7(16)=3×256+10×16+7=768+160+7=935. Puis 935=8×116+7, 116=8×14+4,14=8×1+6,1=8×0+1 :935=1647(8). Contrôle : 512+384+32+7=935.
En regroupant les puissances de 2 par paquets de quatre rangs, N=c0+c1×24+c2×(24)2+…, où chaque cj, écrit avec quatre chiffres binaires, est compris entre 0 et 15. Comme 24=16, c'est l'écriture de N en base 16, unique d'après le cours. Ici, N=101101011 en binaire : 1011(2)=11 (chiffre B), 0110(2)=6 et 1. Donc N=16B(16). Contrôle : 256+96+11=363.
Exercice 13 : Retrouver une base, multiplier en base 5
Moyen
Déterminer l'entier b≥2 tel que 231(b)=66.
Calculer en base 5, sans passer par la base 10, le produit 231(5)×13(5). Contrôler le résultat en base 10.
Montrer qu'un entier écrit en base 5 est congru modulo 4 à la somme de ses chiffres. Vérifier cette propriété sur le résultat de la question 2.
Voir le corrigé
Le chiffre 3 impose b≥4. La condition s'écrit 2b2+3b+1=66, soit 2b2+3b−65=0. Le discriminant vaut 9+520=529=232, d'où b=4−3+23=5 ou b=4−3−23<0. Donc b=5, qui vérifie b≥4.
Multiplication par 3(5) :1×3=3 ;3×3=9=1×5+4, on écrit 4 et l'on retient 1 ; 2×3+1=7=1×5+2, on écrit 2 et l'on retient 1. On obtient 1243(5). Multiplication par 1(5), décalée d'un rang : 2310(5). Addition : 3+0=3 ;4+1=5, on écrit 0, retenue 1 ; 2+3+1=6=5+1, on écrit 1, retenue 1 ; 1+2+1=4. Résultat 4103(5). Contrôle : 13(5)=8 et 66×8=528=4×125+1×25+0×5+3.
5≡1[4], donc 5i≡1[4] pour tout i∈N, et ak5k+⋯+a1×5+a0≡ak+⋯+a1+a0[4]. Pour 4103(5), la somme des chiffres vaut 8, et 8≡0[4] ; en effet 528=4×132.
Exercice 14 : Chiffres manquants et critères de divisibilité
Moyen
Les nombres sont écrits en base 10 ; x,y et z désignent des chiffres.
Déterminer les chiffres x et y tels que 6x41y soit divisible par 36.
Déterminer le chiffre z tel que 3z574 soit divisible par 11.
Montrer qu'un entier naturel est divisible par 8 si et seulement si le nombre formé par ses trois derniers chiffres l'est. En déduire les chiffres y tels que 943y2 soit divisible par 8.
Voir le corrigé
36=4×9 avec 4∧9=1 : un entier est divisible par 36 si et seulement s'il l'est par 4 et par 9 (le sens réciproque est la propriété du produit de deux diviseurs premiers entre eux). Par 4 : 1y doit être multiple de 4, donc y=2 ou y=6. Par 9 : 6+x+4+1+y=11+x+y doit être multiple de 9 ; comme 0≤x+y≤18,x+y=7 ou x+y=16. Pour y=2,x=5, car x=14 n'est pas un chiffre ; pour y=6,x=1, car x=10 n'est pas un chiffre. Les nombres sont 65 412 et 61 416. Contrôle : 65412=36×1817 et 61416=36×1706.
Somme alternée depuis les unités : 4−7+5−z+3=5−z. Il faut 5−z≡0[11] avec 0≤z≤9, donc z=5. Contrôle : 35574=11×3234.
Écrivons N=1000q+r, où r est le nombre formé par les trois derniers chiffres. Comme 1000=8×125≡0[8], N≡r[8], donc 8∣N⟺8∣r. Pour 943y2,r=302+10y et 302=8×37+6. Il faut 6+10y≡0[8], soit 10y≡2[8], c'est-à-dire 2×5y≡2×1[8]. Par simplification (2∧8=2),5y≡1[4], soit y≡1[4] car 5≡1[4]. Donc y∈{1;5;9} :312=8×39,352=8×44,392=8×49.
Initiation au cryptage : chiffrement affine
Méthode : un chiffrement affine y≡ax+b[26] ne se déchiffre que si a∧26=1. On multiplie alors par l'inverse de a modulo 26 pour exprimer x en fonction de y, et l'on vérifie l'équivalence dans les deux sens.
Exercice 15 : Chiffrement affine modulo 26
Moyen
On numérote les lettres de l'alphabet de 0 à 25 : A = 0, B = 1, …, Z = 25. Pour chiffrer une lettre de rang x, on calcule le reste y de 9x+2 dans la division par 26, et l'on remplace la lettre par celle de rang y.
Chiffrer le mot MAROC.
Vérifier que 9×3≡1[26]. En déduire que y≡9x+2[26] si et seulement si x≡3y+20[26].
Déchiffrer le mot ICVW.
Expliquer pourquoi la règle y≡13x+2[26] ne permet pas de déchiffrer.
Voir le corrigé
M a le rang 12 : 9×12+2=110=4×26+6, lettre G. A : 2, lettre C. R (17) : 155=5×26+25, lettre Z. O (14) : 128=4×26+24, lettre Y. C (2) : 20, lettre U. Le mot chiffré est GCZYU.
9×3=27=26+1. Si y≡9x+2[26], en multipliant par 3, 3y≡27x+6≡x+6[26], donc x≡3y−6≡3y+20[26]. Réciproquement, si x≡3y+20[26], alors 9x+2≡27y+182[26] ; or 27≡1 et 182=7×26≡0, donc 9x+2≡y[26].
I (8) : 3×8+20=44≡18, lettre S. C (2) : 26≡0, lettre A. V (21) : 83=3×26+5, lettre F. W (22) : 86=3×26+8, lettre I. Le mot clair est SAFI. Contrôle : S (18) donne 164=6×26+8, lettre I.
13∧26=13=1 : la classe 13 n'est pas inversible dans Z/26Z. Concrètement, A (0) donne 2 et C (2) donne 28≡2 : deux lettres différentes ont le même code C, et l'on ne peut pas savoir laquelle a été chiffrée.
Corriger une copie d’arithmétique
Méthode : chaque erreur viole une hypothèse d'un théorème du cours. Bézout ne conclut que pour une combinaison égale à 1, et l'on ne simplifie une congruence qu'en divisant aussi le module. Fermat exige un module premier ; la solution générale de ax+by=c utilise les coefficients divisés par leur PGCD.
Exercice 16 : Trouver les erreurs : Bézout, simplification, Fermat
Moyen
Un élève a écrit les quatre affirmations suivantes. Pour chacune, trouver l'erreur et écrire une réponse correcte.
« 14×2−8×3=4, donc 14∧8=4. »
« 6x≡8[14] ; je simplifie par 2 : 3x≡4[14], donc x≡6[14]. »
« D'après le petit théorème de Fermat, 220≡1[21]. »
« (3;−1) est solution de 6x+14y=4, donc les solutions sont les couples (3+14k;−1−6k), k∈Z. »
Voir le corrigé
Une égalité 14u+8v=4 prouve seulement que 14∧8 divise 4. En réalité 14=2×7 et 8=23, donc 14∧8=2. Le théorème de Bézout ne conclut que lorsque la combinaison vaut 1.
On ne peut pas garder le module 14 : comme 2=2∧14, la simplification donne 3x≡4[7]. Puis 3×5=15≡1[7], donc x≡20≡6[7]. Modulo 14, les solutions sont x≡6 et x≡13 : l'élève a perdu la seconde. Contrôle : 6×13=78=5×14+8.
21 n'est pas premier (21=3×7), donc Fermat ne s'applique pas. On calcule : 26=64=3×21+1≡1[21], donc 220=(26)3×22≡4[21]. L'affirmation est fausse.
La solution particulière est juste (18−14=4), mais 6∧14=2 : il faut d'abord diviser par 2, 3x+7y=2. Gauss donne alors les couples (3+7k;−1−3k), k∈Z. La réponse de l'élève oublie par exemple (10;−4), solution car 60−56=4, obtenu pour k=1.
Questions flash avant l’examen
Sans calculatrice, une seule bonne réponse par question.
Question 1 : Ce que dit une combinaison
Flash
Deux entiers a et b vérifient 5a+7b=3. Alors :
a∧b=3
a∧b=1
a∧b divise 3
a et b sont premiers
Voir le corrigé
Réponse C : a∧b divise a et b, donc 5a+7b=3. Les deux cas existent : a=2,b=−1 donne a∧b=1, et a=9,b=−6 donne 45−42=3 avec a∧b=3. A et B ne sont donc pas toujours vraies, et D est fausse pour a=9.
Question 2 : Une puissance modulo 23
Flash
Le reste de la division euclidienne de 622 par 23 est :
0
1
6
22
Voir le corrigé
Réponse B : 23 est premier et ne divise pas 6, donc 622≡1[23] par le petit théorème de Fermat. C correspondrait à 623≡6.
Question 3 : Lire un nombre binaire
Flash
L'entier 11010(2) s'écrit en base 10 :
11010
24
13
26
Voir le corrigé
Réponse D : 24+23+2=16+8+2=26. C est la valeur de 1101(2), lu sans le dernier chiffre.
Question 4 : Inverse d’une classe modulo 11
Flash
Dans Z/11Z, l'inverse de 3 est :
4
3
8
10
Voir le corrigé
Réponse A : 3×4=12≡1[11]. Les autres produits valent 9,24≡2 et 30≡8 modulo 11.
Problème de synthèse type examen national
Cet exercice est rédigé dans la forme de l'exercice d'arithmétique de l'examen national de 2 bac sciences mathématiques (questions notées, barème sur 3 points) : une équation diophantienne et le petit théorème de Fermat servent à résoudre une congruence de degré 7. Il a été écrit pour cette page et n'est pas un sujet officiel.
Examen : équation diophantienne et Fermat
Type examen national
Exercice noté sur 3 points. Durée conseillée : 36 min. Calculatrice non autorisée.
On considère dans Z2 l'équation (E) :7x−10y=1. a) (0,25 point) Vérifier que (3;2) est solution de (E). b) (0,5 point) Résoudre (E).
Soit a un entier relatif. a) (0,5 point) En utilisant la question 1 a), montrer que, si 11 ne divise pas a, alors a21≡a[11]. b) (0,25 point) Vérifier que a21≡a[11] reste vrai si 11 divise a.
Soient a et b deux entiers tels que a7≡b[11]. a) (0,5 point) Montrer que b3≡a[11]. b) (0,5 point) En déduire les solutions dans Z de l'équation x7≡6[11].
(0,5 point) Montrer que, pour tous entiers a et c, si a7≡c7[11], alors a≡c[11].
Voir le corrigé
a) 7×3−10×2=21−20=1. b) Si (x;y) est solution, par différence avec (3;2),7(x−3)=10(y−2). Donc 10 divise 7(x−3) et 10∧7=1 : par le théorème de Gauss, x−3=10k avec k∈Z. Alors 70k=10(y−2) donne y=2+7k. Réciproquement, 7(3+10k)−10(2+7k)=21−20=1. Les solutions sont les couples (3+10k;2+7k), k∈Z.
a) 11 est premier et ne divise pas a : d'après le petit théorème de Fermat, a10≡1[11]. La question 1 a) donne 7×3=1+10×2, soit 21=1+2×10, donc a21=a×(a10)2≡a[11]. b) Si 11∣a, alors a≡0[11] et a21≡0≡a[11].
a) Par compatibilité avec les puissances, b3≡(a7)3=a21[11], et a21≡a[11] pour tout entier a d'après la question 2. Donc b3≡a[11]. b) Si x7≡6[11], la question 3 a) avec a=x et b=6 donne x≡63=216=19×11+7≡7[11]. Réciproquement, si x≡7[11], alors x≡63 et x7≡621≡6[11] d'après la question 2. Les solutions sont les entiers x=7+11k,k∈Z.
On applique la question 3 a) avec b=c7, puisque a7≡c7[11] :a≡(c7)3=c21[11]. Or c21≡c[11] d'après la question 2, donc a≡c[11]. Deux entiers non congrus modulo 11 ont donc des puissances septièmes non congrues.