Aller au contenu

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

Type
Exercices corrigés
Exercices
16

Entiers premiers entre eux, coefficients de Bézout, théorème de Gauss, équation ax+by=cax+by=c, congruences linéaires et systèmes, petit théorème de Fermat, numération. Ces 16 exercices corrigés couvrent le chapitre « Arithmétique dans ℤ » de la 2e année du bac sciences mathématiques, dans l'ordre du cours et résumé d'arithmétique dans Z de 2 bac SM.

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=1a\wedge b=1, on cherche une combinaison au+bv=1au+bv=1 (théorème de Bézout), souvent en éliminant nn entre deux expressions. Pour un PGCD imposé dd, on écrit a=dαa=d\alpha et b=dβb=d\beta avec α∧β=1\alpha\wedge\beta=1, puis on traduit les autres conditions sur α\alpha et β\beta.

Exercice 1 : Montrer que deux entiers sont premiers entre eux

Facile
Dans tout l'exercice, nn désigne un entier relatif.
  1. Calculer 3(4n+3)−4(3n+2)3(4n+3)-4(3n+2). En déduire que 4n+34n+3 et 3n+23n+2 sont premiers entre eux.
  2. Calculer (n+1)(2n+1)−n(2n+3)(n+1)(2n+1)-n(2n+3). En déduire que (2n+1)∧(2n+3)=1(2n+1)\wedge(2n+3)=1.
  3. Montrer que (n2+n+1)∧(n+1)=1(n^2+n+1)\wedge(n+1)=1.
  4. En déduire que la fraction 4n+33n+2\dfrac{4n+3}{3n+2} est irréductible pour tout n∈Zn\in\mathbb{Z}, et que n2+n+1n+1\dfrac{n^2+n+1}{n+1} l'est pour tout n≠−1n\neq-1.
Voir le corrigé
  1. 3(4n+3)−4(3n+2)=12n+9−12n−8=13(4n+3)-4(3n+2)=12n+9-12n-8=1. Avec u=3u=3 et v=−4v=-4, on a (4n+3)u+(3n+2)v=1(4n+3)u+(3n+2)v=1 : d'après le théorème de Bézout, (4n+3)∧(3n+2)=1(4n+3)\wedge(3n+2)=1.
  2. (n+1)(2n+1)=2n2+3n+1(n+1)(2n+1)=2n^2+3n+1 et n(2n+3)=2n2+3nn(2n+3)=2n^2+3n, donc la différence vaut 1. C'est une égalité de Bézout avec u=n+1u=n+1 et v=−nv=-n : (2n+1)∧(2n+3)=1(2n+1)\wedge(2n+3)=1. Deux entiers impairs consécutifs sont donc toujours premiers entre eux.
  3. n2+n+1=n(n+1)+1n^2+n+1=n(n+1)+1, donc 1×(n2+n+1)+(−n)×(n+1)=11\times(n^2+n+1)+(-n)\times(n+1)=1. Par Bézout, (n2+n+1)∧(n+1)=1(n^2+n+1)\wedge(n+1)=1.
  4. Une fraction pq\dfrac pq d'entiers, avec q≠0q\neq0, est irréductible si et seulement si p∧q=1p\wedge q=1. Pour tout entier nn, 3n+2≠03n+2\neq0 (sinon n=−23n=-\frac23), et la question 1 conclut. Pour n≠−1n\neq-1, n+1≠0n+1\neq0 et la question 3 conclut.

Exercice 2 : Couples d’entiers de PGCD donné

Moyen
  1. Déterminer les couples (a ;b)(a\,;b) d'entiers naturels tels que a≤ba\leq b, a+b=480a+b=480 et a∧b=32a\wedge b=32.
  2. Déterminer les couples (a ;b)(a\,;b) d'entiers naturels tels que a≤ba\leq b, ab=6912ab=6912 et a∧b=12a\wedge b=12. Calculer a∨ba\vee b pour chacun.
Indication
Question 1 : un diviseur commun de α\alpha et 15−α15-\alpha divise 15, et réciproquement. Question 2 : dans αβ=48\alpha\beta=48, la puissance 242^4 ne peut pas être partagée entre α\alpha et β\beta.
Voir le corrigé
  1. Par la caractérisation du PGCD, a∧b=32a\wedge b=32 équivaut à a=32αa=32\alpha, b=32βb=32\beta avec α∧β=1\alpha\wedge\beta=1. La condition a+b=480a+b=480 devient α+β=15\alpha+\beta=15, et a≤ba\leq b devient α≤β\alpha\leq\beta, soit α≤7\alpha\leq7. De plus α≠0\alpha\neq0, sinon a∧b=b=480a\wedge b=b=480. Les diviseurs communs de α\alpha et β=15−α\beta=15-\alpha sont ceux de α\alpha et 15, donc α∧β=α∧15\alpha\wedge\beta=\alpha\wedge15. Parmi 1, …, 7, les entiers premiers avec 15=3×515=3\times5 sont 1, 2, 4 et 7. Les couples sont : (32 ;448), (64 ;416),(128 ;352), (224 ;256).\begin{aligned}&(32\,;448),\ (64\,;416),\\&(128\,;352),\ (224\,;256).\end{aligned} Contrôle : 224=25×7224=2^5\times7 et 256=28256=2^8, donc 224∧256=25=32224\wedge256=2^5=32.
  2. On écrit a=12αa=12\alpha, b=12βb=12\beta, α∧β=1\alpha\wedge\beta=1, α≤β\alpha\leq\beta. Alors 144 αβ=6912144\,\alpha\beta=6912, soit αβ=48=24×3\alpha\beta=48=2^4\times3. Si 2 divisait α\alpha et β\beta, ils ne seraient pas premiers entre eux : 242^4 est entièrement dans α\alpha ou dans β\beta, et de même pour 3 (unicité de la décomposition, théorème fondamental de l'arithmétique). Avec α≤β\alpha\leq\beta, il reste (α ;β)=(1 ;48)(\alpha\,;\beta)=(1\,;48) ou (3 ;16)(3\,;16), d'où (a ;b)=(12 ;576)(a\,;b)=(12\,;576) ou (36 ;192)(36\,;192). Dans les deux cas, a∨b=aba∧b=691212=576a\vee b=\dfrac{ab}{a\wedge b}=\dfrac{6912}{12}=576. Contrôle : 36=22×3236=2^2\times3^2 et 192=26×3192=2^6\times3 donnent bien 36∧192=22×3=1236\wedge192=2^2\times3=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
  1. Calculer 437∧152437\wedge152 par l'algorithme d'Euclide.
  2. Déterminer deux entiers uu et vv tels que 437u+152v=437∧152437u+152v=437\wedge152.
  3. Vérifier que 437=19×23437=19\times23 et 152=19×8152=19\times8, puis en déduire une égalité de Bézout entre 23 et 8.
  4. Trouver un couple (x ;y)(x\,;y) d'entiers tel que 437x+152y=57437x+152y=57.
  5. L'équation 437x+152y=50437x+152y=50 a-t-elle des solutions dans Z2\mathbb{Z}^2 ?
Voir le corrigé
  1. Divisions successives : 437=152×2+133152=133×1+19133=19×7+0\begin{aligned}437&=152\times2+133\\152&=133\times1+19\\133&=19\times7+0\end{aligned} Le dernier reste non nul est 19 : 437∧152=19437\wedge152=19.
  2. On remonte : 19=152−133=152−(437−2×152)=3×152−43719=152-133=152-(437-2\times152)=3\times152-437. Donc u=−1u=-1 et v=3v=3 conviennent : −437+456=19-437+456=19.
  3. 19×23=43719\times23=437 et 19×8=15219\times8=152. En divisant 437×(−1)+152×3=19437\times(-1)+152\times3=19 par 19 : 23×(−1)+8×3=123\times(-1)+8\times3=1. C'est une égalité de Bézout : 23 et 8 sont premiers entre eux, comme l'annonce la caractérisation du PGCD.
  4. 57=3×1957=3\times19 : on multiplie l'égalité de la question 2 par 3, 437×(−3)+152×9=57437\times(-3)+152\times9=57. Le couple (−3 ;9)(-3\,;9) convient : −1311+1368=57-1311+1368=57.
  5. Non : pour tous entiers xx et yy, 19 divise 437x+152y437x+152y, mais 19 ne divise pas 50 (50=19×2+1250=19\times2+12).

Exercice 4 : Théorème de Gauss et produits

Moyen
  1. Résoudre dans Z2\mathbb{Z}^2 l'équation 18x=39y18x=39y.
  2. Soit n∈Nn\in\mathbb{N}. Montrer que 2424 divise n(n+1)(n+2)(n+3)n(n+1)(n+2)(n+3).
  3. Soient aa et bb deux entiers relatifs non nuls premiers entre eux. Montrer que (a+b)∧a=1(a+b)\wedge a=1 et (a+b)∧b=1(a+b)\wedge b=1, puis que (a+b)∧ab=1(a+b)\wedge ab=1.
Voir le corrigé
  1. On divise par 3=18∧393=18\wedge39 : l'équation équivaut à 6x=13y6x=13y. Si (x ;y)(x\,;y) est solution, 13 divise 6x6x et 13∧6=113\wedge6=1 (13 est premier et ne divise pas 6) : par le théorème de Gauss, 13 divise xx, soit x=13kx=13k avec k∈Zk\in\mathbb{Z}. Alors 78k=13y78k=13y donne y=6ky=6k. Réciproquement, 18×13k=234k=39×6k18\times13k=234k=39\times6k. Les solutions sont les couples (13k ;6k)(13k\,;6k), k∈Zk\in\mathbb{Z}.
  2. Notons P=n(n+1)(n+2)(n+3)P=n(n+1)(n+2)(n+3). Parmi quatre entiers consécutifs, deux sont pairs et consécutifs parmi les pairs : 2m2m et 2m+22m+2, de produit 4m(m+1)4m(m+1). Comme m(m+1)m(m+1) est pair, 8 divise ce produit, donc PP. Parmi nn, n+1n+1, n+2n+2, l'un est multiple de 3 (selon le reste de nn par 3), donc 3∣P3\mid P. Comme 8∧3=18\wedge3=1, la propriété du produit de deux diviseurs premiers entre eux donne 24∣P24\mid P.
  3. Un diviseur commun de a+ba+b et aa divise (a+b)−a=b(a+b)-a=b ; un diviseur commun de aa et bb divise a+ba+b. Donc a+ba+b et aa ont les mêmes diviseurs communs que aa et bb, et (a+b)∧a=a∧b=1(a+b)\wedge a=a\wedge b=1. De même (a+b)∧b=1(a+b)\wedge b=1. Enfin, un entier premier avec aa et avec bb est premier avec abab (propriété du cours, obtenue en multipliant deux égalités de Bézout) : (a+b)∧ab=1(a+b)\wedge ab=1.

Équations diophantiennes et systèmes de congruences : exercices

Méthode : pour ax+by=cax+by=c, on vérifie d'abord que d=a∧bd=a\wedge b divise cc, on divise par dd, 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)(E) : 47x+18y=347x+18y=3, d'inconnue (x ;y)∈Z2(x\,;y)\in\mathbb{Z}^2.
  1. Justifier que (E)(E) admet des solutions.
  2. À l'aide de l'algorithme d'Euclide, déterminer deux entiers uu et vv tels que 47u+18v=147u+18v=1.
  3. En déduire une solution particulière de (E)(E), puis résoudre (E)(E).
  4. Déterminer les solutions de (E)(E) telles que 0≤x≤500\leq x\leq50.
Voir le corrigé
  1. 47 est premier et ne divise pas 18, donc 47∧18=147\wedge18=1, qui divise 3 : (E)(E) admet des solutions.
  2. Divisions successives : 47=18×2+1118=11×1+711=7×1+47=4×1+34=3×1+1\begin{aligned}47&=18\times2+11\\18&=11\times1+7\\11&=7\times1+4\\7&=4\times1+3\\4&=3\times1+1\end{aligned} On remonte : 1=4−3=2×4−7=2×11−3×7=5×11−3×18=5×47−13×18.\begin{aligned}1&=4-3=2\times4-7\\&=2\times11-3\times7\\&=5\times11-3\times18\\&=5\times47-13\times18.\end{aligned} Donc u=5u=5 et v=−13v=-13 : 235−234=1235-234=1.
  3. En multipliant par 3, 47×15+18×(−39)=347\times15+18\times(-39)=3. On simplifie en retranchant 18 à xx et en ajoutant 47 à yy : (x0 ;y0)=(−3 ;8)(x_0\,;y_0)=(-3\,;8), car −141+144=3-141+144=3. Si (x ;y)(x\,;y) est solution, par différence 47(x+3)=−18(y−8)47(x+3)=-18(y-8). Donc 18 divise 47(x+3)47(x+3) et 18∧47=118\wedge47=1 : par Gauss, x+3=18kx+3=18k avec k∈Zk\in\mathbb{Z}, puis 47×18k=−18(y−8)47\times18k=-18(y-8) donne y=8−47ky=8-47k. Réciproquement, 47(−3+18k)+18(8−47k)=−141+144=347(-3+18k)+18(8-47k)=-141+144=3. Les solutions sont les couples (−3+18k ;8−47k)(-3+18k\,;8-47k), k∈Zk\in\mathbb{Z}.
  4. 0≤−3+18k≤50  ⟺  3≤18k≤53  ⟺  k∈{1 ;2}0\leq-3+18k\leq50\iff3\leq18k\leq53\iff k\in\{1\,;2\}, car kk est entier et 5318<3\frac{53}{18}\lt3. On obtient (15 ;−39)(15\,;-39) et (33 ;−86)(33\,;-86). Contrôle : 47×33=155147\times33=1551 et 18×86=154818\times86=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 xx le nombre d'adultes et yy le nombre d'enfants du groupe.
  1. Montrer que 7x+3y=2007x+3y=200.
  2. Résoudre dans Z2\mathbb{Z}^2 l'équation 7x+3y=2007x+3y=200.
  3. En déduire toutes les compositions possibles du groupe. Combien y en a-t-il ?
  4. 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é
  1. La recette donne 35x+15y=100035x+15y=1000 ; on divise par 5 : 7x+3y=2007x+3y=200.
  2. 7∧3=17\wedge3=1 divise 200. Solution particulière : 7×2=147\times2=14 et 200−14=186=3×62200-14=186=3\times62, donc (2 ;62)(2\,;62). Si (x ;y)(x\,;y) est solution, 7(x−2)=−3(y−62)7(x-2)=-3(y-62) ; 3 divise 7(x−2)7(x-2) et 3∧7=13\wedge7=1, donc par Gauss x=2+3kx=2+3k avec k∈Zk\in\mathbb{Z}, puis 21k=−3(y−62)21k=-3(y-62) donne y=62−7ky=62-7k. Réciproquement, 7(2+3k)+3(62−7k)=14+186=2007(2+3k)+3(62-7k)=14+186=200. Les solutions sont les couples (2+3k ;62−7k)(2+3k\,;62-7k), k∈Zk\in\mathbb{Z}.
  3. Ici xx et yy sont des entiers naturels : 2+3k≥0  ⟺  k≥02+3k\geq0\iff k\geq0 (car kk est entier), et 62−7k≥0  ⟺  k≤862-7k\geq0\iff k\leq8, car 627≈8,9\frac{62}{7}\approx8{,}9. Il y a 9 compositions, pour k=0,1,…,8k=0,1,\dots,8 : (2 ;62), (5 ;55),(8 ;48), (11 ;41),(14 ;34), (17 ;27),(20 ;20), (23 ;13),(26 ;6).\begin{aligned}&(2\,;62),\ (5\,;55),\\&(8\,;48),\ (11\,;41),\\&(14\,;34),\ (17\,;27),\\&(20\,;20),\ (23\,;13),\\&(26\,;6).\end{aligned}
  4. x≥y  ⟺  2+3k≥62−7k  ⟺  k≥6x\geq y\iff2+3k\geq62-7k\iff k\geq6 : les possibilités sont (20 ;20)(20\,;20), (23 ;13)(23\,;13) et (26 ;6)(26\,;6). Contrôle : 26×35+6×15=910+90=100026\times35+6\times15=910+90=1000. Une recette de 1 004 DH est impossible : 35x+15y=5(7x+3y)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 NN perles, avec 200≤N≤400200\leq N\leq400. S'il les range par paquets de 9, il en reste 4 ; par paquets de 10, il en reste 3.
  1. Montrer qu'il existe des entiers kk et k′k^{\prime} tels que N=9k+4=10k′+3N=9k+4=10k^{\prime}+3 et 10k′−9k=110k^{\prime}-9k=1.
  2. Résoudre dans Z2\mathbb{Z}^2 l'équation 10u−9v=110u-9v=1.
  3. En déduire que N≡13 [90]N\equiv13\ [90]. Réciproquement, vérifier que tout entier N≡13 [90]N\equiv13\ [90] laisse les restes 4 et 3 dans les divisions par 9 et par 10.
  4. Par paquets de 7, il reste 3 perles. Résoudre le système formé par N≡13 [90]N\equiv13\ [90] et N≡3 [7]N\equiv3\ [7], puis déterminer NN.
Indication
Question 4 : écrire N=13+90tN=13+90t et remplacer 90 et 13 par leurs restes modulo 7 ; 6≡−1 [7]6\equiv-1\ [7].
Voir le corrigé
  1. Les restes des divisions euclidiennes de NN par 9 et par 10 sont 4 et 3 : N=9k+4N=9k+4 et N=10k′+3N=10k^{\prime}+3 avec k,k′∈Nk,k^{\prime}\in\mathbb{N}. En égalant, 10k′−9k=4−3=110k^{\prime}-9k=4-3=1.
  2. 10×1−9×1=110\times1-9\times1=1 : (1 ;1)(1\,;1) est solution. Si (u ;v)(u\,;v) est solution, 10(u−1)=9(v−1)10(u-1)=9(v-1). Donc 9 divise 10(u−1)10(u-1) et 9∧10=19\wedge10=1 : par Gauss, u=1+9tu=1+9t avec t∈Zt\in\mathbb{Z}, puis 90t=9(v−1)90t=9(v-1) donne v=1+10tv=1+10t. Réciproquement, 10(1+9t)−9(1+10t)=110(1+9t)-9(1+10t)=1. Les solutions sont les couples (1+9t ;1+10t)(1+9t\,;1+10t), t∈Zt\in\mathbb{Z}.
  3. D'après la question 1, (k′ ;k)(k^{\prime}\,;k) est solution de l'équation de la question 2, donc k′=1+9tk^{\prime}=1+9t et N=10(1+9t)+3=13+90tN=10(1+9t)+3=13+90t : N≡13 [90]N\equiv13\ [90]. Réciproquement, si N=13+90tN=13+90t, alors N=9(1+10t)+4N=9(1+10t)+4 et N=10(1+9t)+3N=10(1+9t)+3, avec des restes 4 et 3 qui sont bien inférieurs à 9 et à 10.
  4. On écrit N=13+90tN=13+90t. Modulo 7, 90=7×12+6≡690=7\times12+6\equiv6 et 13≡613\equiv6, donc la condition devient 6+6t≡3 [7]6+6t\equiv3\ [7], soit 6t≡4 [7]6t\equiv4\ [7]. Comme 6≡−1 [7]6\equiv-1\ [7], on obtient −t≡4-t\equiv4, c'est-à-dire t≡3 [7]t\equiv3\ [7] : t=3+7st=3+7s et N=283+630sN=283+630s, s∈Zs\in\mathbb{Z}. Réciproquement, 283=7×40+3283=7\times40+3 et 630=7×90630=7\times90, donc ces entiers conviennent. Le système équivaut à N≡283 [630]N\equiv283\ [630], et le seul entier de [200 ;400][200\,;400] est N=283N=283. Contrôle : 283=9×31+4=10×28+3283=9\times31+4=10\times28+3.

Congruences linéaires et inverses dans Z/nZ : exercices

Méthode : dans ax≡b [n]ax\equiv b\ [n], on calcule δ=a∧n\delta=a\wedge n. S'il ne divise pas bb, il n'y a aucune solution ; sinon, la simplification d'une congruence divise aa, bb et le module par δ\delta, puis on multiplie par un inverse. Dans Z/pZ\mathbb{Z}/p\mathbb{Z} avec pp 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\mathbb{Z} les congruences suivantes.
  1. 21x≡9 [24]21x\equiv9\ [24]
  2. 6x≡5 [21]6x\equiv5\ [21]
  3. 11x≡7 [30]11x\equiv7\ [30]
  4. 4x≡12 [18]4x\equiv12\ [18]
Voir le corrigé
  1. 21∧24=321\wedge24=3 divise 9. En simplifiant par 3 (et en divisant le module par 3) : 7x≡3 [8]7x\equiv3\ [8]. Comme 7≡−1 [8]7\equiv-1\ [8], cela s'écrit −x≡3 [8]-x\equiv3\ [8], soit x≡5 [8]x\equiv5\ [8]. Contrôle : 21×5=105=4×24+921\times5=105=4\times24+9.
  2. 6∧21=36\wedge21=3 ne divise pas 5 : aucune solution. En effet, 6x≡5 [21]6x\equiv5\ [21] signifie 6x−21y=56x-21y=5 pour un entier yy, et le membre de gauche est multiple de 3.
  3. 11∧30=111\wedge30=1 et 11×11=121=4×30+111\times11=121=4\times30+1 : 11 est son propre inverse modulo 30. En multipliant par 11, x≡77≡17 [30]x\equiv77\equiv17\ [30]. Contrôle : 11×17=187=6×30+711\times17=187=6\times30+7.
  4. 4x≡4×3 [18]4x\equiv4\times3\ [18] et 4∧18=24\wedge18=2 : la simplification donne x≡3 [9]x\equiv3\ [9]. Modulo 18, les solutions sont x≡3x\equiv3 et x≡12x\equiv12. Contrôle : 4×12=48=2×18+124\times12=48=2\times18+12.

Exercice 9 : Classes inversibles de Z/15Z et de Z/17Z

Moyen
  1. Déterminer les classes inversibles de Z/15Z\mathbb{Z}/15\mathbb{Z} et l'inverse de chacune.
  2. Résoudre dans Z/15Z\mathbb{Z}/15\mathbb{Z} l'équation x2=1‾x^2=\overline{1}.
  3. Montrer que l'équation x2=1‾x^2=\overline{1} n'a que deux solutions dans Z/17Z\mathbb{Z}/17\mathbb{Z}. D'où vient la différence avec la question 2 ?
  4. Résoudre dans Z/17Z\mathbb{Z}/17\mathbb{Z} l'équation 7‾x+4‾=2‾\overline{7}x+\overline{4}=\overline{2}.
Voir le corrigé
  1. a‾\overline{a} est inversible dans Z/15Z\mathbb{Z}/15\mathbb{Z} si et seulement si a∧15=1a\wedge15=1, c'est-à-dire si aa n'est multiple ni de 3 ni de 5. Les classes inversibles sont 1‾\overline{1}, 2‾\overline{2}, 4‾\overline{4}, 7‾\overline{7}, 8‾\overline{8}, 11‾\overline{11}, 13‾\overline{13}, 14‾\overline{14}. Leurs inverses : 2×8=16≡12\times8=16\equiv1, 7×13=91=6×15+17\times13=91=6\times15+1, et 121^2, 42=164^2=16, 112=121=8×15+111^2=121=8\times15+1, 142=196=13×15+114^2=196=13\times15+1 sont congrus à 1. Donc 2‾\overline{2} et 8‾\overline{8} sont inverses l'un de l'autre, de même 7‾\overline{7} et 13‾\overline{13}, et 1‾\overline{1}, 4‾\overline{4}, 11‾\overline{11}, 14‾\overline{14} sont leurs propres inverses.
  2. On teste les 15 classes. Les carrés de 0,1,…,140,1,\dots,14 modulo 15 sont 0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1. Les solutions sont 1‾\overline{1}, 4‾\overline{4}, 11‾\overline{11} et 14‾\overline{14} : quatre solutions.
  3. x2−1‾=(x−1‾)(x+1‾)x^2-\overline{1}=(x-\overline{1})(x+\overline{1}). Comme 17 est premier, un produit nul dans Z/17Z\mathbb{Z}/17\mathbb{Z} a un facteur nul : x=1‾x=\overline{1} ou x=−1‾=16‾x=-\overline{1}=\overline{16}. Dans Z/15Z\mathbb{Z}/15\mathbb{Z}, 15 n'est pas premier et un produit peut être nul sans facteur nul : pour x=4‾x=\overline{4}, (4‾−1‾)(4‾+1‾)=3‾×5‾=0‾(\overline{4}-\overline{1})(\overline{4}+\overline{1})=\overline{3}\times\overline{5}=\overline{0}.
  4. L'équation équivaut à 7‾x=2‾−4‾=−2‾=15‾\overline{7}x=\overline{2}-\overline{4}=\overline{-2}=\overline{15}. Comme 7×5=35=2×17+17\times5=35=2\times17+1, l'inverse de 7‾\overline{7} est 5‾\overline{5}, et x=5‾×15‾=75‾=7‾x=\overline{5}\times\overline{15}=\overline{75}=\overline{7}, car 75=4×17+775=4\times17+7. Contrôle : 7×7+4=53=3×17+27\times7+4=53=3\times17+2.

Congruences et petit théorème de Fermat : exercices

Méthode : avant d'écrire ap−1≡1 [p]a^{p-1}\equiv1\ [p], on vérifie que pp est premier et ne divise pas aa. On divise ensuite l'exposant par p−1p-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
  1. Déterminer le reste de la division euclidienne de 710037^{1003} par 11.
  2. Déterminer le reste de 31223^{122} par 23.
  3. Montrer que 19 divise 52027−65^{2027}-6.
  4. Déterminer les entiers naturels nn tels que 11 divise 7n−27^n-2.
Voir le corrigé
  1. 11 est premier et ne divise pas 7 : par le petit théorème de Fermat, 710≡1 [11]7^{10}\equiv1\ [11]. Comme 1003=10×100+31003=10\times100+3, 71003≡73=343=31×11+2 [11]7^{1003}\equiv7^3=343=31\times11+2\ [11] : le reste est 2.
  2. 23 est premier et ne divise pas 3, donc 322≡1 [23]3^{22}\equiv1\ [23]. Comme 122=22×5+12122=22\times5+12, 3122≡312 [23]3^{122}\equiv3^{12}\ [23]. Or 33=27≡43^3=27\equiv4, 36≡163^6\equiv16 et 312≡256=11×23+3≡3 [23]3^{12}\equiv256=11\times23+3\equiv3\ [23] : le reste est 3.
  3. 19 est premier et ne divise pas 5, donc 518≡1 [19]5^{18}\equiv1\ [19] ; 2027=18×112+112027=18\times112+11 donne 52027≡511 [19]5^{2027}\equiv5^{11}\ [19]. Puis 52=25≡65^2=25\equiv6, 54≡36≡−25^4\equiv36\equiv-2, 58≡45^8\equiv4, et 511=58×52×5≡4×6×5=120≡6 [19]5^{11}=5^8\times5^2\times5\equiv4\times6\times5=120\equiv6\ [19], car 120=6×19+6120=6\times19+6. Donc 52027−6≡0 [19]5^{2027}-6\equiv0\ [19].
  4. Écrivons n=10q+sn=10q+s avec 0≤s≤90\leq s\leq9. Par Fermat, 7n=(710)q×7s≡7s [11]7^n=\left(7^{10}\right)^q\times7^s\equiv7^s\ [11]. Les restes de 7s7^s pour s=0,…,9s=0,\dots,9 sont 1, 7, 5, 2, 3, 10, 4, 6, 9, 8 : seul s=3s=3 donne 2. Donc 11∣7n−2  ⟺  n≡3 [10]11\mid7^n-2\iff n\equiv3\ [10], soit n∈{3 ;13 ;23 ;… }n\in\{3\,;13\,;23\,;\dots\}. La question 1 en est un cas : 1003≡3 [10]1003\equiv3\ [10].

Exercice 11 : Une divisibilité par 77 pour tout entier

Difficile
Dans tout l'exercice, nn désigne un entier relatif.
  1. Montrer que 7 divise n31−nn^{31}-n.
  2. Montrer que 11 divise n31−nn^{31}-n.
  3. En déduire que 77 divise n31−nn^{31}-n pour tout entier nn.
  4. Montrer que 230≡1 [77]2^{30}\equiv1\ [77], puis déterminer le reste de 220272^{2027} dans la division par 77.
Indication
Questions 1 et 2 : 31=6×5+1=10×3+131=6\times5+1=10\times3+1, et distinguer selon que le nombre premier divise nn ou non.
Voir le corrigé
  1. Si 7 divise nn, alors n31≡0≡n [7]n^{31}\equiv0\equiv n\ [7]. Sinon, 7 étant premier, Fermat donne n6≡1 [7]n^6\equiv1\ [7], et n31=(n6)5×n≡n [7]n^{31}=\left(n^6\right)^5\times n\equiv n\ [7]. Dans les deux cas, 7∣n31−n7\mid n^{31}-n.
  2. De même avec 11, premier : si 11∣n11\mid n, les deux membres sont congrus à 0 ; sinon n10≡1 [11]n^{10}\equiv1\ [11] et n31=(n10)3×n≡n [11]n^{31}=\left(n^{10}\right)^3\times n\equiv n\ [11].
  3. 7 et 11 sont deux nombres premiers distincts, donc 7∧11=17\wedge11=1. Comme ils divisent tous deux n31−nn^{31}-n, leur produit 77 le divise. On ne pouvait pas appliquer Fermat modulo 77, qui n'est pas premier.
  4. Pour n=2n=2 : 231≡2 [77]2^{31}\equiv2\ [77], soit 2×230≡2×1 [77]2\times2^{30}\equiv2\times1\ [77]. Comme 2∧77=12\wedge77=1, on simplifie par 2 sans changer le module : 230≡1 [77]2^{30}\equiv1\ [77]. Ensuite 2027=30×67+172027=30\times67+17, donc 22027≡217 [77]2^{2027}\equiv2^{17}\ [77]. On calcule 27=128≡512^7=128\equiv51, 210=1024=13×77+23≡232^{10}=1024=13\times77+23\equiv23, puis 217=210×27≡23×51=1173=15×77+182^{17}=2^{10}\times2^7\equiv23\times51=1173=15\times77+18. Le reste est 18.

Numération en base b et critères de divisibilité : exercices

Méthode : les chiffres en base bb sont les restes des divisions successives par bb, lus du dernier au premier ; on contrôle en développant akbk+⋯+a0a_kb^k+\dots+a_0. Une opération se pose en base bb avec des retenues égales aux quotients par bb. Un critère de divisibilité vient d'une congruence de la base : 10≡1 [9]10\equiv1\ [9], 10≡−1 [11]10\equiv-1\ [11], 1000≡0 [8]1000\equiv0\ [8].

Exercice 12 : Conversions entre bases

Facile
  1. Écrire en base 10 l'entier N=101101011‾(2)N=\overline{101101011}_{(2)}.
  2. Écrire 363 en base 7.
  3. Écrire 3A7‾(16)\overline{3A7}_{(16)} en base 10, puis en base 8.
  4. Justifier que l'on passe de la base 2 à la base 16 en groupant les chiffres par quatre à partir de la droite, puis écrire NN en base 16.
Voir le corrigé
  1. 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=363N=2^8+2^6+2^5+2^3+2+1=256+64+32+8+3=363.
  2. Divisions successives par 7 : 363=7×51+6363=7\times51+6, 51=7×7+251=7\times7+2, 7=7×1+07=7\times1+0, 1=7×0+11=7\times0+1. En lisant les restes de bas en haut, 363=1026‾(7)363=\overline{1026}_{(7)}. Contrôle : 343+0+14+6=363343+0+14+6=363.
  3. A vaut 10, donc 3A7‾(16)=3×256+10×16+7=768+160+7=935\overline{3A7}_{(16)}=3\times256+10\times16+7=768+160+7=935. Puis 935=8×116+7935=8\times116+7, 116=8×14+4116=8\times14+4, 14=8×1+614=8\times1+6, 1=8×0+11=8\times0+1 : 935=1647‾(8)935=\overline{1647}_{(8)}. Contrôle : 512+384+32+7=935512+384+32+7=935.
  4. En regroupant les puissances de 2 par paquets de quatre rangs, N=c0+c1×24+c2×(24)2+…N=c_0+c_1\times2^4+c_2\times\left(2^4\right)^2+\dots, où chaque cjc_j, écrit avec quatre chiffres binaires, est compris entre 0 et 15. Comme 24=162^4=16, c'est l'écriture de NN en base 16, unique d'après le cours. Ici, N=1 0110 1011N=1\ 0110\ 1011 en binaire : 1011‾(2)=11\overline{1011}_{(2)}=11 (chiffre B), 0110‾(2)=6\overline{0110}_{(2)}=6 et 1. Donc N=16B‾(16)N=\overline{16B}_{(16)}. Contrôle : 256+96+11=363256+96+11=363.

Exercice 13 : Retrouver une base, multiplier en base 5

Moyen
  1. Déterminer l'entier b≥2b\geq2 tel que 231‾(b)=66\overline{231}_{(b)}=66.
  2. Calculer en base 5, sans passer par la base 10, le produit 231‾(5)×13‾(5)\overline{231}_{(5)}\times\overline{13}_{(5)}. Contrôler le résultat en base 10.
  3. 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é
  1. Le chiffre 3 impose b≥4b\geq4. La condition s'écrit 2b2+3b+1=662b^2+3b+1=66, soit 2b2+3b−65=02b^2+3b-65=0. Le discriminant vaut 9+520=529=2329+520=529=23^2, d'où b=−3+234=5b=\frac{-3+23}{4}=5 ou b=−3−234<0b=\frac{-3-23}{4}\lt0. Donc b=5b=5, qui vérifie b≥4b\geq4.
  2. Multiplication par 3‾(5)\overline{3}_{(5)} : 1×3=31\times3=3 ; 3×3=9=1×5+43\times3=9=1\times5+4, on écrit 4 et l'on retient 1 ; 2×3+1=7=1×5+22\times3+1=7=1\times5+2, on écrit 2 et l'on retient 1. On obtient 1243‾(5)\overline{1243}_{(5)}. Multiplication par 1‾(5)\overline{1}_{(5)}, décalée d'un rang : 2310‾(5)\overline{2310}_{(5)}. Addition : 3+0=33+0=3 ; 4+1=54+1=5, on écrit 0, retenue 1 ; 2+3+1=6=5+12+3+1=6=5+1, on écrit 1, retenue 1 ; 1+2+1=41+2+1=4. Résultat 4103‾(5)\overline{4103}_{(5)}. Contrôle : 13‾(5)=8\overline{13}_{(5)}=8 et 66×8=528=4×125+1×25+0×5+366\times8=528=4\times125+1\times25+0\times5+3.
  3. 5≡1 [4]5\equiv1\ [4], donc 5i≡1 [4]5^i\equiv1\ [4] pour tout i∈Ni\in\mathbb{N}, et ak5k+⋯+a1×5+a0≡ak+⋯+a1+a0 [4]a_k5^k+\dots+a_1\times5+a_0\equiv a_k+\dots+a_1+a_0\ [4]. Pour 4103‾(5)\overline{4103}_{(5)}, la somme des chiffres vaut 8, et 8≡0 [4]8\equiv0\ [4] ; en effet 528=4×132528=4\times132.

Exercice 14 : Chiffres manquants et critères de divisibilité

Moyen
Les nombres sont écrits en base 10 ; xx, yy et zz désignent des chiffres.
  1. Déterminer les chiffres xx et yy tels que 6x41y‾\overline{6x41y} soit divisible par 36.
  2. Déterminer le chiffre zz tel que 3z574‾\overline{3z574} soit divisible par 11.
  3. 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 yy tels que 943y2‾\overline{943y2} soit divisible par 8.
Voir le corrigé
  1. 36=4×936=4\times9 avec 4∧9=14\wedge9=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‾\overline{1y} doit être multiple de 4, donc y=2y=2 ou y=6y=6. Par 9 : 6+x+4+1+y=11+x+y6+x+4+1+y=11+x+y doit être multiple de 9 ; comme 0≤x+y≤180\leq x+y\leq18, x+y=7x+y=7 ou x+y=16x+y=16. Pour y=2y=2, x=5x=5, car x=14x=14 n'est pas un chiffre ; pour y=6y=6, x=1x=1, car x=10x=10 n'est pas un chiffre. Les nombres sont 65 412 et 61 416. Contrôle : 65412=36×181765412=36\times1817 et 61416=36×170661416=36\times1706.
  2. Somme alternée depuis les unités : 4−7+5−z+3=5−z4-7+5-z+3=5-z. Il faut 5−z≡0 [11]5-z\equiv0\ [11] avec 0≤z≤90\leq z\leq9, donc z=5z=5. Contrôle : 35574=11×323435574=11\times3234.
  3. Écrivons N=1000q+rN=1000q+r, où rr est le nombre formé par les trois derniers chiffres. Comme 1000=8×125≡0 [8]1000=8\times125\equiv0\ [8], N≡r [8]N\equiv r\ [8], donc 8∣N  ⟺  8∣r8\mid N\iff8\mid r. Pour 943y2‾\overline{943y2}, r=302+10yr=302+10y et 302=8×37+6302=8\times37+6. Il faut 6+10y≡0 [8]6+10y\equiv0\ [8], soit 10y≡2 [8]10y\equiv2\ [8], c'est-à-dire 2×5y≡2×1 [8]2\times5y\equiv2\times1\ [8]. Par simplification (2∧8=22\wedge8=2), 5y≡1 [4]5y\equiv1\ [4], soit y≡1 [4]y\equiv1\ [4] car 5≡1 [4]5\equiv1\ [4]. Donc y∈{1 ;5 ;9}y\in\{1\,;5\,;9\} : 312=8×39312=8\times39, 352=8×44352=8\times44, 392=8×49392=8\times49.

Initiation au cryptage : chiffrement affine

Méthode : un chiffrement affine y≡ax+b [26]y\equiv ax+b\ [26] ne se déchiffre que si a∧26=1a\wedge26=1. On multiplie alors par l'inverse de aa modulo 26 pour exprimer xx en fonction de yy, 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 xx, on calcule le reste yy de 9x+29x+2 dans la division par 26, et l'on remplace la lettre par celle de rang yy.
  1. Chiffrer le mot MAROC.
  2. Vérifier que 9×3≡1 [26]9\times3\equiv1\ [26]. En déduire que y≡9x+2 [26]y\equiv9x+2\ [26] si et seulement si x≡3y+20 [26]x\equiv3y+20\ [26].
  3. Déchiffrer le mot ICVW.
  4. Expliquer pourquoi la règle y≡13x+2 [26]y\equiv13x+2\ [26] ne permet pas de déchiffrer.
Voir le corrigé
  1. M a le rang 12 : 9×12+2=110=4×26+69\times12+2=110=4\times26+6, lettre G. A : 22, lettre C. R (17) : 155=5×26+25155=5\times26+25, lettre Z. O (14) : 128=4×26+24128=4\times26+24, lettre Y. C (2) : 2020, lettre U. Le mot chiffré est GCZYU.
  2. 9×3=27=26+19\times3=27=26+1. Si y≡9x+2 [26]y\equiv9x+2\ [26], en multipliant par 3, 3y≡27x+6≡x+6 [26]3y\equiv27x+6\equiv x+6\ [26], donc x≡3y−6≡3y+20 [26]x\equiv3y-6\equiv3y+20\ [26]. Réciproquement, si x≡3y+20 [26]x\equiv3y+20\ [26], alors 9x+2≡27y+182 [26]9x+2\equiv27y+182\ [26] ; or 27≡127\equiv1 et 182=7×26≡0182=7\times26\equiv0, donc 9x+2≡y [26]9x+2\equiv y\ [26].
  3. I (8) : 3×8+20=44≡183\times8+20=44\equiv18, lettre S. C (2) : 26≡026\equiv0, lettre A. V (21) : 83=3×26+583=3\times26+5, lettre F. W (22) : 86=3×26+886=3\times26+8, lettre I. Le mot clair est SAFI. Contrôle : S (18) donne 164=6×26+8164=6\times26+8, lettre I.
  4. 13∧26=13≠113\wedge26=13\neq1 : la classe 13‾\overline{13} n'est pas inversible dans Z/26Z\mathbb{Z}/26\mathbb{Z}. Concrètement, A (0) donne 2 et C (2) donne 28≡228\equiv2 : 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=cax+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.
  1. « 14×2−8×3=414\times2-8\times3=4, donc 14∧8=414\wedge8=4. »
  2. « 6x≡8 [14]6x\equiv8\ [14] ; je simplifie par 2 : 3x≡4 [14]3x\equiv4\ [14], donc x≡6 [14]x\equiv6\ [14]. »
  3. « D'après le petit théorème de Fermat, 220≡1 [21]2^{20}\equiv1\ [21]. »
  4. « (3 ;−1)(3\,;-1) est solution de 6x+14y=46x+14y=4, donc les solutions sont les couples (3+14k ;−1−6k)(3+14k\,;-1-6k), k∈Zk\in\mathbb{Z}. »
Voir le corrigé
  1. Une égalité 14u+8v=414u+8v=4 prouve seulement que 14∧814\wedge8 divise 4. En réalité 14=2×714=2\times7 et 8=238=2^3, donc 14∧8=214\wedge8=2. Le théorème de Bézout ne conclut que lorsque la combinaison vaut 1.
  2. On ne peut pas garder le module 14 : comme 2=2∧142=2\wedge14, la simplification donne 3x≡4 [7]3x\equiv4\ [7]. Puis 3×5=15≡1 [7]3\times5=15\equiv1\ [7], donc x≡20≡6 [7]x\equiv20\equiv6\ [7]. Modulo 14, les solutions sont x≡6x\equiv6 et x≡13x\equiv13 : l'élève a perdu la seconde. Contrôle : 6×13=78=5×14+86\times13=78=5\times14+8.
  3. 21 n'est pas premier (21=3×721=3\times7), donc Fermat ne s'applique pas. On calcule : 26=64=3×21+1≡1 [21]2^6=64=3\times21+1\equiv1\ [21], donc 220=(26)3×22≡4 [21]2^{20}=\left(2^6\right)^3\times2^2\equiv4\ [21]. L'affirmation est fausse.
  4. La solution particulière est juste (18−14=418-14=4), mais 6∧14=26\wedge14=2 : il faut d'abord diviser par 2, 3x+7y=23x+7y=2. Gauss donne alors les couples (3+7k ;−1−3k)(3+7k\,;-1-3k), k∈Zk\in\mathbb{Z}. La réponse de l'élève oublie par exemple (10 ;−4)(10\,;-4), solution car 60−56=460-56=4, obtenu pour k=1k=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 aa et bb vérifient 5a+7b=35a+7b=3. Alors :
  1. a∧b=3a\wedge b=3
  2. a∧b=1a\wedge b=1
  3. a∧ba\wedge b divise 3
  4. aa et bb sont premiers
Voir le corrigé
Réponse C : a∧ba\wedge b divise aa et bb, donc 5a+7b=35a+7b=3. Les deux cas existent : a=2a=2, b=−1b=-1 donne a∧b=1a\wedge b=1, et a=9a=9, b=−6b=-6 donne 45−42=345-42=3 avec a∧b=3a\wedge b=3. A et B ne sont donc pas toujours vraies, et D est fausse pour a=9a=9.

Question 2 : Une puissance modulo 23

Flash
Le reste de la division euclidienne de 6226^{22} par 23 est :
  1. 0
  2. 1
  3. 6
  4. 22
Voir le corrigé
Réponse B : 23 est premier et ne divise pas 6, donc 622≡1 [23]6^{22}\equiv1\ [23] par le petit théorème de Fermat. C correspondrait à 623≡66^{23}\equiv6.

Question 3 : Lire un nombre binaire

Flash
L'entier 11010‾(2)\overline{11010}_{(2)} s'écrit en base 10 :
  1. 11010
  2. 24
  3. 13
  4. 26
Voir le corrigé
Réponse D : 24+23+2=16+8+2=262^4+2^3+2=16+8+2=26. C est la valeur de 1101‾(2)\overline{1101}_{(2)}, lu sans le dernier chiffre.

Question 4 : Inverse d’une classe modulo 11

Flash
Dans Z/11Z\mathbb{Z}/11\mathbb{Z}, l'inverse de 3‾\overline{3} est :
  1. 4‾\overline{4}
  2. 3‾\overline{3}
  3. 8‾\overline{8}
  4. 10‾\overline{10}
Voir le corrigé
Réponse A : 3×4=12≡1 [11]3\times4=12\equiv1\ [11]. Les autres produits valent 99, 24≡224\equiv2 et 30≡830\equiv8 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.
  1. On considère dans Z2\mathbb{Z}^2 l'équation (E)(E) : 7x−10y=1{7x-10y=1}.
    a) (0,25 point) Vérifier que (3 ;2)(3\,;2) est solution de (E)(E).
    b) (0,5 point) Résoudre (E)(E).
  2. Soit aa un entier relatif.
    a) (0,5 point) En utilisant la question 1 a), montrer que, si 11 ne divise pas aa, alors a21≡a [11]a^{21}\equiv a\ [11].
    b) (0,25 point) Vérifier que a21≡a [11]a^{21}\equiv a\ [11] reste vrai si 11 divise aa.
  3. Soient aa et bb deux entiers tels que a7≡b [11]a^7\equiv b\ [11].
    a) (0,5 point) Montrer que b3≡a [11]b^3\equiv a\ [11].
    b) (0,5 point) En déduire les solutions dans Z\mathbb{Z} de l'équation x7≡6 [11]x^7\equiv6\ [11].
  4. (0,5 point) Montrer que, pour tous entiers aa et cc, si a7≡c7 [11]a^7\equiv c^7\ [11], alors a≡c [11]a\equiv c\ [11].
Voir le corrigé
  1. a) 7×3−10×2=21−20=17\times3-10\times2=21-20=1.
    b) Si (x ;y)(x\,;y) est solution, par différence avec (3 ;2)(3\,;2), 7(x−3)=10(y−2)7(x-3)=10(y-2). Donc 10 divise 7(x−3)7(x-3) et 10∧7=110\wedge7=1 : par le théorème de Gauss, x−3=10kx-3=10k avec k∈Zk\in\mathbb{Z}. Alors 70k=10(y−2)70k=10(y-2) donne y=2+7ky=2+7k. Réciproquement, 7(3+10k)−10(2+7k)=21−20=17(3+10k)-10(2+7k)=21-20=1. Les solutions sont les couples (3+10k ;2+7k)(3+10k\,;2+7k), k∈Zk\in\mathbb{Z}.
  2. a) 11 est premier et ne divise pas aa : d'après le petit théorème de Fermat, a10≡1 [11]a^{10}\equiv1\ [11]. La question 1 a) donne 7×3=1+10×27\times3=1+10\times2, soit 21=1+2×1021=1+2\times10, donc a21=a×(a10)2≡a [11]a^{21}=a\times\left(a^{10}\right)^2\equiv a\ [11].
    b) Si 11∣a11\mid a, alors a≡0 [11]a\equiv0\ [11] et a21≡0≡a [11]a^{21}\equiv0\equiv a\ [11].
  3. a) Par compatibilité avec les puissances, b3≡(a7)3=a21 [11]b^3\equiv\left(a^7\right)^3=a^{21}\ [11], et a21≡a [11]a^{21}\equiv a\ [11] pour tout entier aa d'après la question 2. Donc b3≡a [11]b^3\equiv a\ [11].
    b) Si x7≡6 [11]x^7\equiv6\ [11], la question 3 a) avec a=xa=x et b=6b=6 donne x≡63=216=19×11+7≡7 [11]x\equiv6^3=216=19\times11+7\equiv7\ [11]. Réciproquement, si x≡7 [11]x\equiv7\ [11], alors x≡63x\equiv6^3 et x7≡621≡6 [11]x^7\equiv6^{21}\equiv6\ [11] d'après la question 2. Les solutions sont les entiers x=7+11kx=7+11k, k∈Zk\in\mathbb{Z}.
  4. On applique la question 3 a) avec b=c7b=c^7, puisque a7≡c7 [11]a^7\equiv c^7\ [11] : a≡(c7)3=c21 [11].a\equiv\left(c^7\right)^3=c^{21}\ [11]. Or c21≡c [11]c^{21}\equiv c\ [11] d'après la question 2, donc a≡c [11]a\equiv c\ [11]. Deux entiers non congrus modulo 11 ont donc des puissances septièmes non congrues.
Barème : 0,25 + 0,5 + 0,5 + 0,25 + 0,5 + 0,5 + 0,5 = 3 points.

Pages liées