Accueil › 1BAC SM › Chapitre 14 — Arithmétique dans ℤ

Chapitre 14 — Arithmétique dans ℤ

Semestre 2

Chargement du PDF…

Cours

Plan du chapitre. I. Divisibilité dans Z\Z — II. Division euclidienne — III. Congruences modulo nn — IV. Nombres premiers — V. PGCD et PPCM — VI. L’ensemble Z/nZ\Z/n\Z — Résumé.

Prérequis. Ensembles N\N et Z\Z, raisonnement par récurrence, par contraposée et par l’absurde (Ch. 01), dénombrement (Ch. 13) pour compter les diviseurs. Notation : on écrit « aa divise bb » en toutes lettres.

I. Divisibilité dans Z\Z

1) Définition

Définition 1

Soient a,b∈Za,b\in\Z. On dit que aa divise bb (ou que bb est un multiple de aa) s’il existe k∈Zk\in\Z tel que b=kab=ka. L’ensemble des multiples de aa est noté aZa\Z.

Exemple 1

Montrer que 33 divise −12-12. Que dire de 00, de 11 et de −1-1 vis-à-vis de la divisibilité ?

Voir la solution

33 divise −12-12 car −12=(−4)×3-12=(-4)\times3 ; 00 est multiple de tout entier ; 11 et −1-1 divisent tout entier.

2) Propriétés

Propriété 1

Soient a,b,c∈Za,b,c\in\Z.

  • aa divise aa ; si aa divise bb et bb divise cc, alors aa divise cc (transitivité).
  • Si aa divise bb et bb divise aa, alors ∣a∣=∣b∣|a|=|b|.
  • Si aa divise bb et aa divise cc, alors pour tous u,v∈Zu,v\in\Z, aa divise ub+vcub+vc (combinaison linéaire).
  • Si aa divise bb et b≠0b\neq0, alors ∣a∣≤∣b∣|a|\le|b|.
Voir la solution

Preuve de la combinaison linéaire (raisonnement direct). aa divise bb et aa divise cc ⟹\Longrightarrow il existe k,k′∈Zk,k'\in\Z tels que b=kab=ka et c=k′ac=k'a ⟹\Longrightarrow ub+vc=(uk+vk′)aub+vc=(uk+vk')a avec uk+vk′∈Zuk+vk'\in\Z ⟹\Longrightarrow aa divise ub+vcub+vc.

Exemple 2

Déterminer les entiers n∈Zn\in\Z tels que n+2n+2 divise 3n+13n+1.

Voir la solution

Soit n∈Zn\in\Z tel que n+2n+2 divise 3n+13n+1. Comme n+2n+2 divise 3(n+2)3(n+2), il divise 3(n+2)−(3n+1)=53(n+2)-(3n+1)=5 : donc n+2∈{−5;−1;1;5}n+2\in\{-5;-1;1;5\}, soit n∈{−7;−3;−1;3}n\in\{-7;-3;-1;3\} (on vérifie que ces valeurs conviennent).

II. Division euclidienne

1) Théorème

Théorème 1 (admis)

Soient a∈Za\in\Z et b∈N∗b\in\N^*. Il existe un unique couple (q;r)∈Z×N(q;r)\in\Z\times\N tel que a=bq+ra=bq+r et 0≤r<b0\le r<b. qq est le quotient et rr le reste de la division euclidienne de aa par bb.

Exemple 3

Déterminer le quotient et le reste de la division euclidienne de −23-23 par 55.

Voir la solution

−23=5×(−5)+2-23=5\times(-5)+2 : le quotient de −23-23 par 55 est −5-5 et le reste 22 (et non −3-3, car il faut 0≤r<50\le r<5).

2) Conséquence

Propriété 2

Soit b∈N∗b\in\N^*. Tout entier aa s’écrit sous l’une des formes bkbk, bk+1bk+1, …, bk+(b−1)bk+(b-1) avec k∈Zk\in\Z. En particulier tout entier est de la forme 2k2k ou 2k+12k+1, et de la forme 3k3k, 3k+13k+1 ou 3k+23k+2.

Exemple 4

Montrer que, pour tout n∈Zn\in\Z, n(n+1)(n+2)n(n+1)(n+2) est divisible par 33.

Voir la solution

Pour tout n∈Zn\in\Z, n(n+1)(n+2)n(n+1)(n+2) est divisible par 33 : on traite les trois cas n=3kn=3k, n=3k+1n=3k+1, n=3k+2n=3k+2 ; dans chaque cas l’un des trois facteurs est multiple de 33.

III. Congruences modulo nn

1) Définition

Définition 2

Soient n∈N∗n\in\N^* et a,b∈Za,b\in\Z. On dit que aa est congru à bb modulo nn, et on note a≡b [n]a\equiv b\,[n], si nn divise a−ba-b. Cela équivaut à : aa et bb ont le même reste dans la division euclidienne par nn.

Propriété 3

Si rr est le reste de la division euclidienne de aa par nn, alors a≡r [n]a\equiv r\,[n] et 0≤r<n0\le r<n. Réciproquement, si a≡r [n]a\equiv r\,[n] et 0≤r<n0\le r<n, alors rr est ce reste.

2) Compatibilité avec les opérations

Propriété 4

Soient n∈N∗n\in\N^* et a,b,c,d∈Za,b,c,d\in\Z tels que a≡b [n]a\equiv b\,[n] et c≡d [n]c\equiv d\,[n]. Alors :

  • a+c≡b+d [n]a+c\equiv b+d\,[n] et a−c≡b−d [n]a-c\equiv b-d\,[n] ;
  • ac≡bd [n]ac\equiv bd\,[n] ;
  • pour tout k∈Nk\in\N : ak≡bk [n]a^k\equiv b^k\,[n] ;
  • la relation ≡\equiv est réflexive, symétrique et transitive.
Voir la solution

Preuve de ak≡bk [n]a^k\equiv b^k\,[n] (raisonnement par récurrence sur kk). Initialisation : pour k=0k=0, on a a0=1≡1=b0 [n]a^0=1\equiv1=b^0\,[n]. Hérédité : soit k∈Nk\in\N, on suppose ak≡bk [n]a^k\equiv b^k\,[n] ; comme a≡b [n]a\equiv b\,[n], la compatibilité avec le produit donne ak+1=ak a≡bk b=bk+1 [n]a^{k+1}=a^k\,a\equiv b^k\,b=b^{k+1}\,[n]. Conclusion : d’après le principe du raisonnement par récurrence, ak≡bk [n]a^k\equiv b^k\,[n] pour tout k∈Nk\in\N.

Exemple 5

Déterminer le reste de 220272^{2027} dans la division par 77.

Voir la solution

Reste de 220272^{2027} dans la division par 77 : 23=8≡1 [7]2^3=8\equiv1\,[7] et 2027=3×675+22027=3\times675+2, donc 22027=(23)675×22≡1×4=4 [7]2^{2027}=(2^3)^{675}\times2^2\equiv1\times4=4\,[7]. Le reste est 44.

IV. Nombres premiers

1) Définition et critère

Définition 3

Un entier naturel pp est premier s’il admet exactement deux diviseurs dans N\N : 11 et pp. (11 n’est pas premier.)

Propriété 5

  • Tout entier naturel n≥2n\ge2 admet au moins un diviseur premier.
  • Si n≥2n\ge2 n’est pas premier, il admet un diviseur premier pp tel que p2≤np^2\le n. Donc si aucun nombre premier pp tel que p2≤np^2\le n ne divise nn, alors nn est premier.
  • L’ensemble des nombres premiers est infini.
Voir la solution

Preuve du dernier point (raisonnement par l’absurde). Supposons qu’il n’y ait qu’un nombre fini de nombres premiers p1,…,pkp_1,\dots,p_k et posons N=p1p2⋯pk+1≥2N=p_1p_2\cdots p_k+1\ge2. NN admet un diviseur premier, donc un pip_i divise NN ; comme pip_i divise aussi p1⋯pkp_1\cdots p_k, il divise la différence 11 : contradiction avec pi≥2p_i\ge2.

2) Décomposition en facteurs premiers

Théorème 2 (admis)

Tout entier n≥2n\ge2 s’écrit de façon unique (à l’ordre près) n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} où p1<⋯<pkp_1<\dots<p_k sont premiers et αi∈N∗\alpha_i\in\N^*.

Propriété 6 : nombre de diviseurs

Avec la décomposition ci-dessus, les diviseurs positifs de nn sont les p1β1⋯pkβkp_1^{\beta_1}\cdots p_k^{\beta_k} avec 0≤βi≤αi0\le\beta_i\le\alpha_i ; leur nombre est (principe multiplicatif, Ch. 13) (α1+1)(α2+1)⋯(αk+1)(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1).

Exemple 6

Combien 360360 possède-t-il de diviseurs positifs ?

Voir la solution

360=23×32×5360=2^3\times3^2\times5 possède 4×3×2=244\times3\times2=24 diviseurs positifs.

Propriété 7 (lemme d’Euclide, admis)

Si un nombre premier pp divise un produit abab (a,b∈Za,b\in\Z), alors pp divise aa ou pp divise bb.

V. PGCD et PPCM

1) Définitions

Définition 4

Soient a,b∈Za,b\in\Z non tous deux nuls. Le PGCD de aa et bb, noté PGCD⁡(a;b)\pgcd(a;b) ou a∧ba\wedge b, est le plus grand diviseur commun de aa et bb. Pour a,b∈Z∗a,b\in\Z^*, le PPCM, noté PPCM⁡(a;b)\operatorname{PPCM}(a;b) ou a∨ba\vee b, est le plus petit multiple commun strictement positif. On dit que aa et bb sont premiers entre eux si a∧b=1a\wedge b=1.

2) Propriétés et algorithme d’Euclide

Propriété 8

Soient a,b∈Z∗a,b\in\Z^*.

  • Pour tout k∈Zk\in\Z : a∧b=b∧(a−kb)a\wedge b=b\wedge(a-kb). En particulier, si a=bq+ra=bq+r (division euclidienne), a∧b=b∧ra\wedge b=b\wedge r.
  • Algorithme d’Euclide : on effectue des divisions successives ; le PGCD est le dernier reste non nul.
  • Les diviseurs communs à aa et bb sont exactement les diviseurs de a∧ba\wedge b ; les multiples communs sont les multiples de a∨ba\vee b.
  • (a∧b)×(a∨b)=∣ab∣(a\wedge b)\times(a\vee b)=|ab| ; pour k∈N∗k\in\N^* : (ka)∧(kb)=k(a∧b)(ka)\wedge(kb)=k(a\wedge b).
  • Si d=a∧bd=a\wedge b, alors a=da′a=da' et b=db′b=db' avec a′∧b′=1a'\wedge b'=1.
  • Avec les décompositions en facteurs premiers : a∧ba\wedge b (resp. a∨ba\vee b) est le produit des facteurs premiers communs (resp. de tous les facteurs) affectés du plus petit (resp. plus grand) exposant.

Exemple 7

Calculer PGCD⁡(1071;462)\pgcd(1071;462) par l’algorithme d’Euclide, puis 1071∨4621071\vee462.

Voir la solution

PGCD⁡(1071;462)\pgcd(1071;462) : 1071=462×2+1471071=462\times2+147, 462=147×3+21462=147\times3+21, 147=21×7+0147=21\times7+0 : 1071∧462=211071\wedge462=21 et 1071∨462=1071×46221=23 5621071\vee462=\frac{1071\times462}{21}=23\,562.

VI. L’ensemble Z/nZ\Z/n\Z

1) Classes d’équivalence

Définition 5

Soit n∈N∗n\in\N^*, n≥2n\ge2. La classe de a∈Za\in\Z modulo nn est a‾={b∈Z / b≡a [n]}=a+nZ\overline a=\{b\in\Z\ /\ b\equiv a\,[n]\}=a+n\Z. On a a‾=b‾  ⟺  a≡b [n]\overline a=\overline b\iff a\equiv b\,[n]. L’ensemble des classes est Z/nZ={0‾;1‾;… ;n−1‾}\Z/n\Z=\{\overline0;\overline1;\dots;\overline{n-1}\} ; il a nn éléments.

2) Opérations

Propriété 9

On définit a‾+b‾=a+b‾\overline a+\overline b=\overline{a+b} et a‾×b‾=ab‾\overline a\times\overline b=\overline{ab} (ces définitions ne dépendent pas des représentants choisis, d’après la propriété 4). On résout une équation dans Z/nZ\Z/n\Z en testant les nn classes, à l’aide d’une table d’addition ou de multiplication.

Exemple 8

Résoudre dans Z/5Z\Z/5\Z l’équation 3‾×x‾=2‾\overline3\times\overline x=\overline2.

Voir la solution

Dans Z/5Z\Z/5\Z : 3‾×x‾=2‾\overline3\times\overline x=\overline2. Les produits 3‾×0‾,…,3‾×4‾\overline3\times\overline0,\dots,\overline3\times\overline4 valent 0‾,3‾,1‾,4‾,2‾\overline0,\overline3,\overline1,\overline4,\overline2 : l’unique solution est x‾=4‾\overline x=\overline4.

Résumé

Remarque — l’essentiel

  • aa divise bb   ⟺  \iff ∃k∈Z\exists k\in\Z, b=kab=ka ; un diviseur commun divise toute combinaison linéaire.
  • Division euclidienne : a=bq+ra=bq+r, 0≤r<b0\le r<b ; a≡b [n]  ⟺  na\equiv b\,[n]\iff n divise a−ba-b ; congruences compatibles avec ++, ×\times, puissances.
  • Décomposition en facteurs premiers ; nombre de diviseurs ∏(αi+1)\prod(\alpha_i+1).
  • a∧b=b∧(a−kb)a\wedge b=b\wedge(a-kb) ; algorithme d’Euclide ; (a∧b)(a∨b)=∣ab∣(a\wedge b)(a\vee b)=|ab|.
  • Z/nZ={0‾;… ;n−1‾}\Z/n\Z=\{\overline0;\dots;\overline{n-1}\}, opérations sur les représentants.

Série d’exercices

Remarque — méthodes utilisées

  • Raisonnement direct : chaîne d’implications ⟹\Longrightarrow ; un diviseur commun de deux entiers divise toute combinaison linéaire de ces entiers.
  • Restes de puissances : on cherche une petite puissance congrue à 11 (ou −1-1), puis on écrit la D.E. de l’exposant.
  • Disjonction de cas : on examine tous les restes possibles modulo nn (Cas 1, Cas 2, …).
  • Récurrence en trois étapes : Initialisation, Hérédité, Conclusion.
  • Tous les résultats ont été contrôlés par Python/sympy (build/verif_lot3.py).

Cadre. Toute réponse doit être justifiée. On écrit « aa divise bb » en toutes lettres ; « D.E. » abrège « division euclidienne ». Pour chaque raisonnement, on annoncera son type (direct, par disjonction de cas, par récurrence, par contraposée, par l’absurde). Difficulté : de ★\bigstar à ★★★★★\bigstar\bigstar\bigstar\bigstar\bigstar.

Exercice 1 — Diviseurs Facile ★☆☆☆☆

  1. Déterminer et dénombrer les diviseurs positifs de 156156.
  2. Déterminer tous les diviseurs de −8-8 dans Z\Z.
Voir la solution

1. 156=22×3×13156=2^2\times3\times13, donc 156156 a (2+1)(1+1)(1+1)=12(2+1)(1+1)(1+1)=12 diviseurs positifs : 1,2,3,4,6,12,13,26,39,52,78,1561,2,3,4,6,12,13,26,39,52,78,156.

2. Les diviseurs positifs de 8=238=2^3 sont 1,2,4,81,2,4,8 ; les diviseurs de −8-8 dans Z\Z sont donc ±1,±2,±4,±8\pm1,\pm2,\pm4,\pm8 (huit diviseurs).

Exercice 2 — Combinaisons linéaires Facile ★★☆☆☆

  1. Soient a,b,c,x,y∈Za,b,c,x,y\in\Z. Montrer que : a. si aa divise 2b+c2b+c et aa divise b+cb+c, alors aa divise cc ; b. si aa divise 2b+3c2b+3c et aa divise b+cb+c, alors aa divise cc ; c. si aa divise x−yx-y et aa divise b−cb-c, alors aa divise xb−cyxb-cy.
  2. Soient a,n∈Za,n\in\Z tels que aa divise 12n+112n+1 et aa divise −2n+3-2n+3. Montrer que aa divise 1919.
  3. Soient d,n∈Zd,n\in\Z tels que dd divise n2+3n^2+3 et dd divise 2n−12n-1. Montrer que dd divise 1313.
Voir la solution

Raisonnement direct, par combinaisons linéaires.

1. a. aa divise 2b+c2b+c et aa divise b+cb+c ⟹\Longrightarrow aa divise 2(b+c)−(2b+c)=c2(b+c)-(2b+c)=c.

1. b. aa divise 2b+3c2b+3c et aa divise b+cb+c ⟹\Longrightarrow aa divise (2b+3c)−2(b+c)=c(2b+3c)-2(b+c)=c.

1. c. On remarque que xb−cy=x(b−c)+c(x−y)xb-cy=x(b-c)+c(x-y). Donc aa divise b−cb-c et aa divise x−yx-y ⟹\Longrightarrow aa divise x(b−c)+c(x−y)=xb−cyx(b-c)+c(x-y)=xb-cy.

2. aa divise 12n+112n+1 et aa divise −2n+3-2n+3 ⟹\Longrightarrow aa divise (12n+1)+6(−2n+3)=19(12n+1)+6(-2n+3)=19.

3. dd divise n2+3n^2+3 et dd divise 2n−12n-1 ⟹\Longrightarrow dd divise 4(n2+3)4(n^2+3) et dd divise (2n−1)(2n+1)=4n2−1(2n-1)(2n+1)=4n^2-1 ⟹\Longrightarrow dd divise 4(n2+3)−(4n2−1)=134(n^2+3)-(4n^2-1)=13.

Exercice 3 — Combinaisons linéaires Facile ★☆☆☆☆

Soient a,x∈Za,x\in\Z. Montrer que si aa divise 5x+75x+7 et aa divise 2x−32x-3, alors aa divise 2929.

Voir la solution

aa divise 5x+75x+7 et aa divise 2x−32x-3 ⟹\Longrightarrow aa divise 2(5x+7)−5(2x−3)=14+15=292(5x+7)-5(2x-3)=14+15=29.

Exercice 4 — Récurrence et divisibilité Facile ★★☆☆☆

Montrer que pour tout n∈Nn\in\N, 33 divise 4n−14^n-1.

Voir la solution

Raisonnement par récurrence. Pour n∈Nn\in\N, notons P(n)P(n) : « 33 divise 4n−14^n-1 ».

  • Initialisation. Pour n=0n=0, on a 40−1=0=3×04^0-1=0=3\times0 : 33 divise 00, donc P(0)P(0) est vraie.
  • Hérédité. Soit n∈Nn\in\N, on suppose que 33 divise 4n−14^n-1 : il existe k∈Nk\in\N tel que 4n−1=3k4^n-1=3k, soit 4n=3k+14^n=3k+1. Alors 4n+1−1=4(3k+1)−1=12k+3=3(4k+1)4^{n+1}-1=4(3k+1)-1=12k+3=3(4k+1) avec 4k+1∈N4k+1\in\N : 33 divise 4n+1−14^{n+1}-1.
  • Conclusion. D’après le principe du raisonnement par récurrence, 33 divise 4n−14^n-1 pour tout n∈Nn\in\N.

Exercice 5 — Recherche d’entiers Facile ★★☆☆☆

Déterminer les entiers relatifs nn, n≠1n\neq1, tels que n−1n-1 divise 2n+72n+7.

Voir la solution

n−1n-1 divise 2n+72n+7   ⟺  \iff n−1n-1 divise (2n+7)−2(n−1)=9(2n+7)-2(n-1)=9 (car n−1n-1 divise 2(n−1)2(n-1) ; l’équivalence vient de ce que 2n+7=2(n−1)+92n+7=2(n-1)+9)   ⟺  \iff n−1∈{−9;−3;−1;1;3;9}n-1\in\{-9;-3;-1;1;3;9\}   ⟺  \iff n∈{−8;−2;0;2;4;10}n\in\{-8;-2;0;2;4;10\}.

Exercice 6 — Fraction entière Moyen ★★★☆☆

Déterminer les entiers relatifs nn, n≠−4n\neq-4, tels que n3+8n+4\dfrac{n^3+8}{n+4} soit un entier relatif.

Voir la solution

Par division : n3+8=(n+4)(n2−4n+16)−56n^3+8=(n+4)(n^2-4n+16)-56. Donc n3+8n+4=n2−4n+16−56n+4\frac{n^3+8}{n+4}=n^2-4n+16-\frac{56}{n+4} et n3+8n+4∈Z  ⟺  n+4\frac{n^3+8}{n+4}\in\Z\iff n+4 divise 5656. Les diviseurs de 56=23×756=2^3\times7 sont ±1,±2,±4,±7,±8,±14,±28,±56\pm1,\pm2,\pm4,\pm7,\pm8,\pm14,\pm28,\pm56. Donc n=d−4n=d-4 avec dd l’un de ces diviseurs : n∈{−60;−32;−18;−12;−11;−8;−6;−5;−3;−2;0;3;4;10;24;52}n\in\{-60;-32;-18;-12;-11;-8;-6;-5;-3;-2;0;3;4;10;24;52\} (seize valeurs).

Exercice 7 — Équations dans N2\N^2 Moyen ★★★☆☆

Résoudre dans N2\N^2 les équations suivantes, d’inconnue (x;y)(x;y) :

  1. x2−y2=32x^2-y^2=32 avec x>yx>y ;
  2. 2xy+2x+y=992xy+2x+y=99.
Voir la solution

1. x2−y2=32  ⟺  (x−y)(x+y)=32x^2-y^2=32\iff(x-y)(x+y)=32, avec 0<x−y<x+y0<x-y<x+y (car x>y≥0x>y\ge0). De plus x−yx-y et x+yx+y ont la même parité (leur somme 2x2x est paire) ; leur produit étant pair, ils sont tous deux pairs. Les factorisations 32=2×16=4×832=2\times16=4\times8 donnent : {x−y=2x+y=16  ⟺  (x;y)=(9;7)\begin{cases}x-y=2\\x+y=16\end{cases}\iff(x;y)=(9;7) et {x−y=4x+y=8  ⟺  (x;y)=(6;2)\begin{cases}x-y=4\\x+y=8\end{cases}\iff(x;y)=(6;2). S={(9;7);(6;2)}S=\{(9;7);(6;2)\}.

2. 2xy+2x+y=99  ⟺  2x(y+1)+(y+1)=100  ⟺  (2x+1)(y+1)=1002xy+2x+y=99\iff2x(y+1)+(y+1)=100\iff(2x+1)(y+1)=100. 2x+12x+1 est un diviseur impair de 100100 : 11, 55 ou 2525. Cas 1 : 2x+1=12x+1=1, y+1=100y+1=100 : (0;99)(0;99). Cas 2 : 2x+1=52x+1=5, y+1=20y+1=20 : (2;19)(2;19). Cas 3 : 2x+1=252x+1=25, y+1=4y+1=4 : (12;3)(12;3). S={(0;99);(2;19);(12;3)}S=\{(0;99);(2;19);(12;3)\}.

Exercice 8 — Restes modulo 9 Facile ★★☆☆☆

Déterminer le reste de la D.E. par 99 de chacun des nombres 2345110023451^{100} et 10023451+23451100100^{23451}+23451^{100}.

Voir la solution

2345123451 a pour somme des chiffres 1515, donc 23451≡15≡6 [9]23451\equiv15\equiv6\,[9]. Or 62=36≡0 [9]6^2=36\equiv0\,[9], donc 23451100≡6100=(62)50≡0 [9]23451^{100}\equiv6^{100}=\left(6^2\right)^{50}\equiv0\,[9] : le reste est 00. 100≡1 [9]100\equiv1\,[9] donc 10023451≡1 [9]100^{23451}\equiv1\,[9] et 10023451+23451100≡1+0=1 [9]100^{23451}+23451^{100}\equiv1+0=1\,[9] : le reste est 11.

Exercice 9 — Puissances de 5 modulo 17 Facile ★★☆☆☆

  1. Montrer que 58≡−1 [17]5^8\equiv-1\,[17].
  2. Déterminer les restes de la D.E. par 1717 des nombres 5165^{16} et 55005^{500}.
Voir la solution

1. 52=25≡8 [17]5^2=25\equiv8\,[17], 54≡64≡13≡−4 [17]5^4\equiv64\equiv13\equiv-4\,[17], 58≡(−4)2=16≡−1 [17]5^8\equiv(-4)^2=16\equiv-1\,[17].

2. 516=(58)2≡(−1)2=1 [17]5^{16}=\left(5^8\right)^2\equiv(-1)^2=1\,[17] : reste 11. 500=16×31+4500=16\times31+4, donc 5500=(516)31×54≡1×13 [17]5^{500}=\left(5^{16}\right)^{31}\times5^4\equiv1\times13\,[17] : reste 1313.

Exercice 10 — Opérations sur les restes Facile ★★☆☆☆

Soient a,b∈Za,b\in\Z tels que le reste de la D.E. de aa par 1919 est 1717 et celui de bb par 1919 est 1515. Déterminer le reste de la D.E. par 1919 de :

  1. a+ba+b ;
  2. a2+b2a^2+b^2 ;
  3. 2a−5b2a-5b.
Voir la solution

a≡17≡−2 [19]a\equiv17\equiv-2\,[19] et b≡15≡−4 [19]b\equiv15\equiv-4\,[19].

1. a+b≡−6≡13 [19]a+b\equiv-6\equiv13\,[19] : reste 1313. 2. a2+b2≡4+16=20≡1 [19]a^2+b^2\equiv4+16=20\equiv1\,[19] : reste 11. 3. 2a−5b≡−4+20=16 [19]2a-5b\equiv-4+20=16\,[19] : reste 1616.

Exercice 11 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de 320073^{2007} par 22, puis par 1313.

Voir la solution

320073^{2007} est impair : le reste par 22 est 11. 33=27≡1 [13]3^3=27\equiv1\,[13] et 2007=3×6692007=3\times669, donc 32007=(33)669≡1 [13]3^{2007}=\left(3^3\right)^{669}\equiv1\,[13] : reste 11.

Exercice 12 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de 73201973^{2019} par 77.

Voir la solution

73=7×10+373=7\times10+3, donc 73≡3 [7]73\equiv3\,[7] ; 33=27≡−1 [7]3^3=27\equiv-1\,[7], donc 36≡1 [7]3^6\equiv1\,[7]. 2019=6×336+32019=6\times336+3 : 732019≡(36)336×33≡−1≡6 [7]73^{2019}\equiv\left(3^6\right)^{336}\times3^3\equiv-1\equiv6\,[7]. Reste 66.

Exercice 13 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. de 1952×234119^{52}\times23^{41} par 77.

Voir la solution

19≡5≡−2 [7]19\equiv5\equiv-2\,[7] et 23≡2 [7]23\equiv2\,[7] ; 23≡1 [7]2^3\equiv1\,[7]. 1952≡(−2)52=252=(23)17×2≡2 [7]19^{52}\equiv(-2)^{52}=2^{52}=\left(2^3\right)^{17}\times2\equiv2\,[7] et 2341≡241=(23)13×22≡4 [7]23^{41}\equiv2^{41}=\left(2^3\right)^{13}\times2^2\equiv4\,[7]. Donc 1952×2341≡8≡1 [7]19^{52}\times23^{41}\equiv8\equiv1\,[7] : reste 11.

Exercice 14 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. par 55 du nombre 2233+332222^{33}+33^{22}.

Voir la solution

22≡2 [5]22\equiv2\,[5], 24=16≡1 [5]2^4=16\equiv1\,[5], 33=4×8+133=4\times8+1 : 2233≡2 [5]22^{33}\equiv2\,[5]. 33≡3≡−2 [5]33\equiv3\equiv-2\,[5], 22=4×5+222=4\times5+2 : 3322≡(−2)22=(24)5×4≡4 [5]33^{22}\equiv(-2)^{22}=\left(2^4\right)^5\times4\equiv4\,[5]. Somme : 6≡1 [5]6\equiv1\,[5], reste 11.

Exercice 15 — Discussion suivant nn Moyen ★★★☆☆

  1. Déterminer, suivant les valeurs de n∈Nn\in\N, le reste de la D.E. de 3n3^n par 77.
  2. En déduire le reste de la D.E. de 201920192019^{2019} par 77.
Voir la solution

1. 31≡33^1\equiv3, 32≡23^2\equiv2, 33≡63^3\equiv6, 34≡43^4\equiv4, 35≡53^5\equiv5, 36≡1 [7]3^6\equiv1\,[7]. Soit n=6k+rn=6k+r (k∈Nk\in\N, 0≤r≤50\le r\le5) : 3n=(36)k3r≡3r [7]3^n=\left(3^6\right)^k3^r\equiv3^r\,[7]. Le reste vaut 1,3,2,6,4,51,3,2,6,4,5 selon que r=0,1,2,3,4,5r=0,1,2,3,4,5.

2. 2019=7×288+32019=7\times288+3 : 2019≡3 [7]2019\equiv3\,[7] donc 20192019≡32019 [7]2019^{2019}\equiv3^{2019}\,[7] ; 2019=6×336+32019=6\times336+3, donc r=3r=3 et le reste est 66.

Exercice 16 — Équations dans Z/4Z\Z/4\Z Facile ★★☆☆☆

Résoudre dans Z/4Z\Z/4\Z les équations suivantes, d’inconnue xx :

  1. 2‾x=3‾\overline2x=\overline3 ;
  2. x2+3‾x=0‾x^2+\overline3x=\overline0 ;
  3. 2013‾x3+2‾x=k‾\overline{2013}x^3+\overline2x=\overline k, en discutant suivant k‾∈Z/4Z\overline k\in\Z/4\Z.
Voir la solution

Dans Z/4Z={0‾;1‾;2‾;3‾}\Z/4\Z=\{\overline0;\overline1;\overline2;\overline3\}, on teste les quatre classes (disjonction de cas).

1. 2‾x\overline2x prend les valeurs 0‾,2‾,0‾,2‾\overline0,\overline2,\overline0,\overline2 : jamais 3‾\overline3. S=∅S=\emptyset.

2. x2+3‾xx^2+\overline3x vaut 0‾,0‾,10‾=2‾,18‾=2‾\overline0,\overline0,\overline{10}=\overline2,\overline{18}=\overline2 pour x=0‾,1‾,2‾,3‾x=\overline0,\overline1,\overline2,\overline3. S={0‾;1‾}S=\{\overline0;\overline1\}.

3. 2013‾=1‾\overline{2013}=\overline1 (car 2013=4×503+12013=4\times503+1). x3+2‾xx^3+\overline2x vaut 0‾,3‾,12‾=0‾,33‾=1‾\overline0,\overline3,\overline{12}=\overline0,\overline{33}=\overline1. D’où : si k‾=0‾\overline k=\overline0, S={0‾;2‾}S=\{\overline0;\overline2\} ; si k‾=1‾\overline k=\overline1, S={3‾}S=\{\overline3\} ; si k‾=2‾\overline k=\overline2, S=∅S=\emptyset ; si k‾=3‾\overline k=\overline3, S={1‾}S=\{\overline1\}.

Exercice 17 — Équation dans (Z/5Z)2(\Z/5\Z)^2 Facile ★★☆☆☆

Résoudre dans (Z/5Z)2(\Z/5\Z)^2 l’équation x+3‾y=1‾x+\overline3y=\overline1, d’inconnue (x;y)(x;y).

Voir la solution

x+3‾y=1‾  ⟺  x=1‾−3‾yx+\overline3y=\overline1\iff x=\overline1-\overline3y. Pour chaque yy, xx est unique : S={(1‾;0‾);(3‾;1‾);(0‾;2‾);(2‾;3‾);(4‾;4‾)}S=\{(\overline1;\overline0);(\overline3;\overline1);(\overline0;\overline2);(\overline2;\overline3);(\overline4;\overline4)\} (cinq couples).

Exercice 18 — Système dans (Z/5Z)2(\Z/5\Z)^2 Moyen ★★★☆☆

Résoudre dans (Z/5Z)2(\Z/5\Z)^2 le système {3‾x+2‾y=1‾2‾x+4‾y=3‾\begin{cases}\overline3x+\overline2y=\overline1\\\overline2x+\overline4y=\overline3\end{cases}.

Voir la solution

Raisonnement par équivalences. On multiplie la 2e équation par 3‾\overline3 (inverse de 2‾\overline2 car 2‾×3‾=1‾\overline2\times\overline3=\overline1) : 2‾x+4‾y=3‾  ⟺  x+12‾y=9‾  ⟺  x+2‾y=4‾  ⟺  x=4‾−2‾y=4‾+3‾y\overline2x+\overline4y=\overline3\iff x+\overline{12}y=\overline9\iff x+\overline2y=\overline4\iff x=\overline4-\overline2y=\overline4+\overline3y. En reportant dans la 1re : 3‾(4‾+3‾y)+2‾y=1‾  ⟺  12‾+11‾y=1‾  ⟺  2‾+y=1‾  ⟺  y=4‾\overline3(\overline4+\overline3y)+\overline2y=\overline1\iff\overline{12}+\overline{11}y=\overline1\iff\overline2+y=\overline1\iff y=\overline4, puis x=4‾+12‾=16‾=1‾x=\overline4+\overline{12}=\overline{16}=\overline1. S={(1‾;4‾)}S=\{(\overline1;\overline4)\}. Vérification : 3‾+8‾=11‾=1‾\overline3+\overline8=\overline{11}=\overline1 et 2‾+16‾=18‾=3‾\overline2+\overline{16}=\overline{18}=\overline3.

Exercice 19 — Modulo 10 Moyen ★★★☆☆

  1. Déterminer, suivant les valeurs de n∈Nn\in\N, le reste de la D.E. de 3n3^n par 1010.
  2. En déduire le chiffre des unités du nombre 202920202029^{2020}.
  3. Déterminer les entiers n∈Nn\in\N tels que 3n+5n+2≡0 [10]3^n+5n+2\equiv0\,[10].
Voir la solution

1. 30≡13^0\equiv1, 31≡33^1\equiv3, 32≡93^2\equiv9, 33≡73^3\equiv7, 34≡1 [10]3^4\equiv1\,[10]. Pour n=4k+rn=4k+r (0≤r≤30\le r\le3) : 3n≡3r [10]3^n\equiv3^r\,[10] ; le reste vaut 1,3,9,71,3,9,7 pour r=0,1,2,3r=0,1,2,3.

2. 2029≡9≡−1 [10]2029\equiv9\equiv-1\,[10] et 20202020 est pair : 20292020≡1 [10]2029^{2020}\equiv1\,[10]. Le chiffre des unités est 11.

3. Disjonction de cas suivant nn modulo 44 (on a 5n≡0 [10]5n\equiv0\,[10] si nn pair, 5n≡5 [10]5n\equiv5\,[10] si nn impair). Cas 1 : n=4kn=4k : 1+0+2=3≢01+0+2=3\not\equiv0. Cas 2 : n=4k+1n=4k+1 : 3+5+2=10≡03+5+2=10\equiv0 : convient. Cas 3 : n=4k+2n=4k+2 : 9+0+2=11≢09+0+2=11\not\equiv0. Cas 4 : n=4k+3n=4k+3 : 7+5+2=14≢07+5+2=14\not\equiv0. Les solutions sont les n∈Nn\in\N tels que n≡1 [4]n\equiv1\,[4].

Exercice 20 — Chiffre des unités Facile ★★☆☆☆

Déterminer le chiffre des unités du nombre 24537201824537^{2018}.

Voir la solution

24537≡7 [10]24537\equiv7\,[10] ; 72≡97^2\equiv9, 74≡81≡1 [10]7^4\equiv81\equiv1\,[10] ; 2018=4×504+22018=4\times504+2 : 245372018≡72≡9 [10]24537^{2018}\equiv7^2\equiv9\,[10]. Chiffre des unités : 99.

Exercice 21 — Congruence à deux périodes Difficile ★★★★☆

Déterminer tous les entiers naturels nn tels que 2n≡n2 [9]2^n\equiv n^2\,[9].

Voir la solution

26=64≡1 [9]2^6=64\equiv1\,[9] : 2n [9]2^n\,[9] ne dépend que de nn modulo 66 ; n2 [9]n^2\,[9] ne dépend que de nn modulo 99. On étudie donc nn modulo 18=PPCM⁡(6;9)18=\operatorname{PPCM}(6;9) : pour n=18k+rn=18k+r, 2n≡2r2^n\equiv2^r et n2≡r2 [9]n^2\equiv r^2\,[9]. On teste r∈{0;… ;17}r\in\{0;\dots;17\} : les restes de 2r2^r sont 1,2,4,8,7,51,2,4,8,7,5 (période 66) et ceux de r2r^2 sont 0,1,4,0,7,7,0,4,10,1,4,0,7,7,0,4,1 (période 99). L’égalité n’a lieu que pour r=2r=2 (4=44=4) et r=4r=4 (7=77=7). Les solutions sont les n∈Nn\in\N tels que n≡2 [18]n\equiv2\,[18] ou n≡4 [18]n\equiv4\,[18].

Exercice 22 — Congruence à deux périodes Moyen ★★★☆☆

Résoudre dans N\N l’équation 3n+5n+1≡0 [8]3^n+5n+1\equiv0\,[8].

Voir la solution

32=9≡1 [8]3^2=9\equiv1\,[8]. Disjonction de cas. Cas 1 : nn pair : 3n≡1 [8]3^n\equiv1\,[8], l’équation devient 5n+2≡0 [8]  ⟺  5n≡6 [8]  ⟺  25n≡30 [8]  ⟺  n≡6 [8]5n+2\equiv0\,[8]\iff5n\equiv6\,[8]\iff25n\equiv30\,[8]\iff n\equiv6\,[8] (car 25≡125\equiv1 et 30≡630\equiv6), ce qui est compatible avec nn pair. Cas 2 : nn impair : 3n≡3 [8]3^n\equiv3\,[8] et 5n+4≡0 [8]  ⟺  n≡20≡4 [8]5n+4\equiv0\,[8]\iff n\equiv20\equiv4\,[8] : nn serait pair, contradiction ; pas de solution. S={n∈N / n≡6 [8]}S=\{n\in\N\ /\ n\equiv6\,[8]\}.

Exercice 23 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de 2233×332222^{33}\times33^{22} par 55.

Voir la solution

D’après l’exercice 14 : 2233≡222^{33}\equiv2 et 3322≡4 [5]33^{22}\equiv4\,[5] ; le produit est ≡8≡3 [5]\equiv8\equiv3\,[5] : reste 33.

Exercice 24 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de 320193^{2019} par 22 et par 1313.

Voir la solution

320193^{2019} est impair : reste 11 par 22. 33≡1 [13]3^3\equiv1\,[13] et 2019=3×6732019=3\times673 : 32019≡1 [13]3^{2019}\equiv1\,[13], reste 11.

Exercice 25 — Récurrence Moyen ★★★☆☆

  1. Montrer que pour tout n∈N∗n\in\N^*, 22n+6n−12^{2n}+6n-1 est divisible par 99.
  2. En déduire que pour tout n∈N∗n\in\N^*, 4n≡3n+1 [9]4^n\equiv3n+1\,[9].
Voir la solution

1. Raisonnement par récurrence.

  • Initialisation. Pour n=1n=1, on a 22+6−1=92^2+6-1=9 : 99 divise 99.
  • Hérédité. Soit n∈N∗n\in\N^*, on suppose que 99 divise 22n+6n−12^{2n}+6n-1 : il existe k∈Nk\in\N tel que 22n+6n−1=9k2^{2n}+6n-1=9k, soit 22n=9k−6n+12^{2n}=9k-6n+1. Alors 22(n+1)+6(n+1)−1=4×22n+6n+5=4(9k−6n+1)+6n+5=36k−18n+9=9(4k−2n+1)2^{2(n+1)}+6(n+1)-1=4\times2^{2n}+6n+5=4(9k-6n+1)+6n+5=36k-18n+9=9(4k-2n+1) avec 4k−2n+1∈Z4k-2n+1\in\Z (et même dans N\N puisque le nombre est positif) : 99 divise 22(n+1)+6(n+1)−12^{2(n+1)}+6(n+1)-1.
  • Conclusion. D’après le principe du raisonnement par récurrence, 99 divise 22n+6n−12^{2n}+6n-1 pour tout n∈N∗n\in\N^*.

2. Soit n∈N∗n\in\N^* : 4n+6n−1≡0 [9]⟹4n≡1−6n [9]⟹4n≡1−6n+9n=3n+1 [9]4^n+6n-1\equiv0\,[9]\Longrightarrow4^n\equiv1-6n\,[9]\Longrightarrow4^n\equiv1-6n+9n=3n+1\,[9].

Exercice 26 — Restes modulo 11 Facile ★★☆☆☆

Déterminer le reste de la D.E. par 1111 du nombre 1653351+431371653^{351}+43^{137}.

Voir la solution

1653=11×150+31653=11\times150+3, donc 1653≡3 [11]1653\equiv3\,[11] ; 35=243=11×22+1≡1 [11]3^5=243=11\times22+1\equiv1\,[11] et 351=5×70+1351=5\times70+1 : 1653351≡3 [11]1653^{351}\equiv3\,[11]. 43≡−1 [11]43\equiv-1\,[11] et 137137 est impair : 43137≡−1 [11]43^{137}\equiv-1\,[11]. Somme : 3−1=23-1=2 ; reste 22.

Exercice 27 — Somme de puissances Moyen ★★★☆☆

Montrer que 77 divise 12019+22019+32019+42019+52019+620191^{2019}+2^{2019}+3^{2019}+4^{2019}+5^{2019}+6^{2019}.

Voir la solution

Pour k∈{1;2;3}k\in\{1;2;3\} : 7−k≡−k [7]7-k\equiv-k\,[7] et 20192019 est impair, donc (7−k)2019≡(−k)2019=−k2019 [7](7-k)^{2019}\equiv(-k)^{2019}=-k^{2019}\,[7]. En groupant 11 avec 66, 22 avec 55, 33 avec 44 : la somme est ≡0 [7]\equiv0\,[7], donc 77 la divise.

Exercice 28 — Entiers consécutifs Facile ★☆☆☆☆

Montrer que pour tout n∈Zn\in\Z, PGCD⁡(n;n+1)=1\pgcd(n;n+1)=1.

Voir la solution

Raisonnement direct. Soit d=PGCD⁡(n;n+1)d=\pgcd(n;n+1) : dd divise nn et dd divise n+1n+1 ⟹\Longrightarrow dd divise (n+1)−n=1(n+1)-n=1 ⟹\Longrightarrow d=1d=1 (car d≥1d\ge1).

Exercice 29 — Suite et divisibilité Moyen ★★★☆☆

Pour n∈Nn\in\N, on pose Un=4n−3n−1U_n=4^n-3n-1.

  1. Montrer que pour tout n∈Nn\in\N, Un+1=4Un+9nU_{n+1}=4U_n+9n.
  2. En déduire que pour tout n∈Nn\in\N, 99 divise 4n−3n−14^n-3n-1.
Voir la solution

1. Soit n∈Nn\in\N : 4Un+9n=4n+1−12n−4+9n=4n+1−3(n+1)−1=Un+14U_n+9n=4^{n+1}-12n-4+9n=4^{n+1}-3(n+1)-1=U_{n+1}.

2. Raisonnement par récurrence.

  • Initialisation. Pour n=0n=0, on a 40−0−1=04^0-0-1=0 et 99 divise 00.
  • Hérédité. Soit n∈Nn\in\N, on suppose que 99 divise 4n−3n−14^n-3n-1 : il existe k∈Nk\in\N tel que 4n−3n−1=9k4^n-3n-1=9k. D’après 1., 4n+1−3(n+1)−1=4×9k+9n=9(4k+n)4^{n+1}-3(n+1)-1=4\times9k+9n=9(4k+n) avec 4k+n∈N4k+n\in\N.
  • Conclusion. D’après le principe du raisonnement par récurrence, 99 divise 4n−3n−14^n-3n-1 pour tout n∈Nn\in\N.

Exercice 30 — Nombre non premier Moyen ★★★☆☆

Pour n∈Nn\in\N, on pose αn=n4−n2+16\alpha_n=n^4-n^2+16.

  1. Montrer que n2+3n+4n^2+3n+4 et n2−3n+4n^2-3n+4 sont des entiers naturels pairs, et que αn=(n2+3n+4)(n2−3n+4)\alpha_n=(n^2+3n+4)(n^2-3n+4).
  2. En déduire que αn\alpha_n n’est pas premier.
Voir la solution

1. n2+3n=n(n+3)n^2+3n=n(n+3) : l’un des facteurs nn, n+3n+3 est pair (ils sont de parités différentes), donc n2+3n+4n^2+3n+4 est pair ; de même n2−3n=n(n−3)n^2-3n=n(n-3) est pair. Ce sont des entiers naturels car n2−3n+4=(n−32)2+74>0n^2-3n+4=\left(n-\frac32\right)^2+\frac74>0. Enfin (n2+4)2−(3n)2=n4+8n2+16−9n2=αn(n^2+4)^2-(3n)^2=n^4+8n^2+16-9n^2=\alpha_n.

2. Raisonnement direct. Les deux facteurs sont pairs et non nuls, donc chacun est ≥2\ge2 et le produit αn\alpha_n est divisible par 44 ; comme αn≥16>4\alpha_n\ge16>4 (car n4−n2=n2(n2−1)≥0n^4-n^2=n^2(n^2-1)\ge0), 44 est un diviseur de αn\alpha_n différent de 11 et de αn\alpha_n : αn\alpha_n n’est pas premier.

Exercice 31 — PGCD et fraction Moyen ★★★☆☆

Pour n∈Nn\in\N, on considère A=n2+3A=n^2+3 et B=n+2B=n+2.

  1. Montrer que PGCD⁡(A;B)=PGCD⁡(n+2;7)\pgcd(A;B)=\pgcd(n+2;7).
  2. Déterminer l’entier naturel nn tel que n2+3n+2∈N\dfrac{n^2+3}{n+2}\in\N.
Voir la solution

1. n2+3=(n+2)(n−2)+7n^2+3=(n+2)(n-2)+7, donc PGCD⁡(n2+3;n+2)=PGCD⁡(n+2;7)\pgcd(n^2+3;n+2)=\pgcd(n+2;7) (propriété a∧b=b∧(a−kb)a\wedge b=b\wedge(a-kb)).

2. n2+3n+2∈N  ⟺  n+2\frac{n^2+3}{n+2}\in\N\iff n+2 divise n2+3  ⟺  n+2n^2+3\iff n+2 divise 77 (car n+2n+2 divise (n+2)(n−2)(n+2)(n-2))   ⟺  n+2=7\iff n+2=7 (car n+2≥2n+2\ge2)   ⟺  n=5\iff n=5. Vérification : 287=4\frac{28}7=4.

Exercice 32 — PGCD Moyen ★★★☆☆

Pour n∈N∗n\in\N^*, on pose an=(25n−1)(36n−1)a_n=\left(25^n-1\right)\left(36^n-1\right) et bn=(5n−1)(6n−1)b_n=\left(5^n-1\right)\left(6^n-1\right). Calculer PGCD⁡(an;bn)\pgcd(a_n;b_n).

Voir la solution

an=(5n−1)(5n+1)(6n−1)(6n+1)=bn×(5n+1)(6n+1)a_n=(5^n-1)(5^n+1)(6^n-1)(6^n+1)=b_n\times(5^n+1)(6^n+1) : bnb_n divise ana_n et bn>0b_n>0 (pour n≥1n\ge1). Donc PGCD⁡(an;bn)=bn=(5n−1)(6n−1)\pgcd(a_n;b_n)=b_n=(5^n-1)(6^n-1).

Exercice 33 — Équations dans N2\N^2 Moyen ★★★☆☆

Résoudre dans N2\N^2 les équations suivantes :

  1. x2−y2=45x^2-y^2=45 avec x>yx>y ;
  2. xy+2x+3y=24xy+2x+3y=24.
Voir la solution

1. (x−y)(x+y)=45(x-y)(x+y)=45 avec 0<x−y<x+y0<x-y<x+y : 1×451\times45, 3×153\times15, 5×95\times9 donnent (23;22)(23;22), (9;6)(9;6), (7;2)(7;2). S={(23;22);(9;6);(7;2)}S=\{(23;22);(9;6);(7;2)\}.

2. xy+2x+3y=24  ⟺  (x+3)(y+2)=30xy+2x+3y=24\iff(x+3)(y+2)=30 avec x+3≥3x+3\ge3 et y+2≥2y+2\ge2 : (x+3;y+2)∈{(3;10);(5;6);(6;5);(10;3);(15;2)}(x+3;y+2)\in\{(3;10);(5;6);(6;5);(10;3);(15;2)\}. S={(0;8);(2;4);(3;3);(7;1);(12;0)}S=\{(0;8);(2;4);(3;3);(7;1);(12;0)\}.

Exercice 34 — Recherche d’entiers Facile ★★☆☆☆

Déterminer tous les entiers n∈Zn\in\Z, n≠−3n\neq-3, tels que n+3n+3 divise 2n+132n+13.

Voir la solution

2n+13=2(n+3)+72n+13=2(n+3)+7 : n+3n+3 divise 2n+13  ⟺  n+32n+13\iff n+3 divise 7  ⟺  n+3∈{−7;−1;1;7}  ⟺  n∈{−10;−4;−2;4}7\iff n+3\in\{-7;-1;1;7\}\iff n\in\{-10;-4;-2;4\}.

Exercice 35 — Fraction entière Facile ★★☆☆☆

Déterminer les entiers n∈Zn\in\Z, n≠−4n\neq-4, tels que 3n+8n+4\dfrac{3n+8}{n+4} soit un entier relatif.

Voir la solution

3n+8n+4=3−4n+4\frac{3n+8}{n+4}=3-\frac4{n+4} ; il est entier   ⟺  n+4\iff n+4 divise 4  ⟺  n+4∈{±1;±2;±4}  ⟺  n∈{−8;−6;−5;−3;−2;0}4\iff n+4\in\{\pm1;\pm2;\pm4\}\iff n\in\{-8;-6;-5;-3;-2;0\}.

Exercice 36 — PGCD, PPCM Facile ★★☆☆☆

Déterminer d=PGCD⁡(−8316;1080)d=\pgcd(-8316;1080) et m=PPCM⁡(8316;1980)m=\operatorname{PPCM}(8316;1980).

Voir la solution

8316=22×33×7×118316=2^2\times3^3\times7\times11, 1080=23×33×51080=2^3\times3^3\times5, 1980=22×32×5×111980=2^2\times3^2\times5\times11. d=PGCD⁡(8316;1080)=22×33=108d=\pgcd(8316;1080)=2^2\times3^3=108 ; m=22×33×5×7×11=41 580m=2^2\times3^3\times5\times7\times11=41\,580.

Exercice 37 — PGCD et PPCM Facile ★★☆☆☆

Soient a,b∈N∗a,b\in\N^* tels que PGCD⁡(a;b)=2\pgcd(a;b)=2 et ab=12ab=12. Déterminer PPCM⁡(a;b)\operatorname{PPCM}(a;b), puis les couples (a;b)(a;b) possibles.

Voir la solution

PGCD⁡(a;b)×PPCM⁡(a;b)=ab\pgcd(a;b)\times\operatorname{PPCM}(a;b)=ab donc PPCM⁡(a;b)=122=6\operatorname{PPCM}(a;b)=\frac{12}2=6. On écrit a=2a′a=2a', b=2b′b=2b' avec PGCD⁡(a′;b′)=1\pgcd(a';b')=1 : 4a′b′=124a'b'=12, a′b′=3a'b'=3, d’où (a;b)∈{(2;6);(6;2)}(a;b)\in\{(2;6);(6;2)\}.

Exercice 38 — Quotients successifs Difficile ★★★★☆

Soient n∈Nn\in\N et a,b∈N∗a,b\in\N^*. Montrer que si qq est le quotient de la D.E. de nn par aa et q′q' celui de la D.E. de qq par bb, alors q′q' est aussi le quotient de la D.E. de nn par abab.

Voir la solution

Raisonnement direct. n=aq+rn=aq+r avec 0≤r≤a−10\le r\le a-1 et q=bq′+r′q=bq'+r' avec 0≤r′≤b−10\le r'\le b-1. Alors n=abq′+(ar′+r)n=abq'+(ar'+r) et 0≤ar′+r≤a(b−1)+a−1=ab−1<ab0\le ar'+r\le a(b-1)+a-1=ab-1<ab. Par unicité de la D.E. de nn par abab, le quotient est q′q' (et le reste ar′+rar'+r).

Exercice 39 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. de 1941×235219^{41}\times23^{52} par 77.

Voir la solution

19≡−219\equiv-2 et 23≡2 [7]23\equiv2\,[7] : 1941≡−241=−(23)1322≡−4 [7]19^{41}\equiv-2^{41}=-\left(2^3\right)^{13}2^2\equiv-4\,[7] et 2352≡252≡2 [7]23^{52}\equiv2^{52}\equiv2\,[7]. Produit : −8≡−1≡6 [7]-8\equiv-1\equiv6\,[7] ; reste 66.

Exercice 40 — Congruences Facile ★★☆☆☆

  1. Montrer que pour tout n∈N∗n\in\N^*, (n+1)2019−1≡0 [n](n+1)^{2019}-1\equiv0\,[n].
  2. Montrer que pour tout n∈Nn\in\N, 42n+2≡1 [15]4^{2n+2}\equiv1\,[15].
Voir la solution

1. Soit n∈N∗n\in\N^* : n+1≡1 [n]⟹(n+1)2019≡1 [n]⟹(n+1)2019−1≡0 [n]n+1\equiv1\,[n]\Longrightarrow(n+1)^{2019}\equiv1\,[n]\Longrightarrow(n+1)^{2019}-1\equiv0\,[n].

2. Soit n∈Nn\in\N : 42=16≡1 [15]⟹42n+2=(42)n+1≡1 [15]4^2=16\equiv1\,[15]\Longrightarrow4^{2n+2}=\left(4^2\right)^{n+1}\equiv1\,[15].

Exercice 41 — Équation dans Z/5Z\Z/5\Z Facile ★★☆☆☆

Résoudre dans Z/5Z\Z/5\Z l’équation x2−x−2‾=0‾x^2-x-\overline2=\overline0.

Voir la solution

On teste les cinq classes : x2−x−2‾x^2-x-\overline2 vaut −2‾=3‾\overline{-2}=\overline3, 3‾\overline3, 0‾\overline0, 4‾\overline4, 10‾=0‾\overline{10}=\overline0 pour x=0‾,…,4‾x=\overline0,\dots,\overline4. S={2‾;4‾}S=\{\overline2;\overline4\}.

Exercice 42 — PGCD Facile ★★☆☆☆

Soient a,b,c,d∈Za,b,c,d\in\Z, avec b≠0b\neq0, tels que a=bc+da=bc+d.

  1. Montrer que PGCD⁡(a;b)=PGCD⁡(b;d)\pgcd(a;b)=\pgcd(b;d).
  2. En déduire que PGCD⁡(a;b)=PGCD⁡(b;a−bc)\pgcd(a;b)=\pgcd(b;a-bc).
Voir la solution

1. Raisonnement par double inclusion des diviseurs communs. Si δ\delta divise aa et bb, alors δ\delta divise a−bc=da-bc=d ; si δ\delta divise bb et dd, alors δ\delta divise bc+d=abc+d=a. Les couples (a;b)(a;b) et (b;d)(b;d) ont les mêmes diviseurs communs, donc le même plus grand : PGCD⁡(a;b)=PGCD⁡(b;d)\pgcd(a;b)=\pgcd(b;d).

2. On applique 1. avec d=a−bcd=a-bc.

Exercice 43 — PGCD Moyen ★★★☆☆

Soit a∈Na\in\N. On considère A=35a+57A=35a+57 et B=45a+76B=45a+76. Montrer que PGCD⁡(A;B)=1\pgcd(A;B)=1 ou PGCD⁡(A;B)=19\pgcd(A;B)=19.

Voir la solution

Soit δ=PGCD⁡(A;B)\delta=\pgcd(A;B) : δ\delta divise AA et BB ⟹\Longrightarrow δ\delta divise 7B−9A=(315a+532)−(315a+513)=197B-9A=(315a+532)-(315a+513)=19. Comme 1919 est premier, δ∈{1;19}\delta\in\{1;19\}.

Exercice 44 — PGCD avec paramètre Difficile ★★★★☆

  1. Soient x,y∈N∗x,y\in\N^*, a=9x+4ya=9x+4y et b=2x+yb=2x+y. Montrer que PGCD⁡(x;y)=PGCD⁡(a;b)\pgcd(x;y)=\pgcd(a;b).
  2. Soit n∈Nn\in\N ; on pose a=n2+5n+13a=n^2+5n+13 et b=n+3b=n+3. a. Montrer que PGCD⁡(a;b)=PGCD⁡(b;7)\pgcd(a;b)=\pgcd(b;7). b. En déduire les valeurs possibles de PGCD⁡(a;b)\pgcd(a;b). c. Montrer que n≡4 [7]  ⟺  PGCD⁡(a;b)=7n\equiv4\,[7]\iff\pgcd(a;b)=7. d. En déduire les valeurs de nn telles que PGCD⁡(a;b)=1\pgcd(a;b)=1.
Voir la solution

1. a−4b=xa-4b=x et 9b−2a=y9b-2a=y. Tout diviseur commun de x,yx,y divise a=9x+4ya=9x+4y et b=2x+yb=2x+y ; tout diviseur commun de a,ba,b divise x=a−4bx=a-4b et y=9b−2ay=9b-2a. Mêmes diviseurs communs, donc PGCD⁡(x;y)=PGCD⁡(a;b)\pgcd(x;y)=\pgcd(a;b).

2. a. n2+5n+13=(n+3)(n+2)+7n^2+5n+13=(n+3)(n+2)+7, donc PGCD⁡(a;b)=PGCD⁡(b;7)\pgcd(a;b)=\pgcd(b;7).

2. b. PGCD⁡(b;7)\pgcd(b;7) divise 77, premier : PGCD⁡(a;b)∈{1;7}\pgcd(a;b)\in\{1;7\}.

2. c. PGCD⁡(a;b)=7  ⟺  7\pgcd(a;b)=7\iff7 divise n+3  ⟺  n≡−3 [7]  ⟺  n≡4 [7]n+3\iff n\equiv-3\,[7]\iff n\equiv4\,[7].

2. d. D’après b. et c. : PGCD⁡(a;b)=1  ⟺  n≢4 [7]\pgcd(a;b)=1\iff n\not\equiv4\,[7], c’est-à-dire n∈Nn\in\N et n≠7k+4n\neq7k+4 pour tout k∈Nk\in\N.

Exercice 45 — PGCD avec paramètre Moyen ★★★☆☆

Soit n∈Nn\in\N ; on pose dn=PGCD⁡(2n+8;3n+15)d_n=\pgcd(2n+8;3n+15).

  1. Montrer que dnd_n divise 66.
  2. Déterminer les entiers naturels nn tels que dn=6d_n=6.
Voir la solution

1. dnd_n divise 2n+82n+8 et 3n+153n+15 ⟹\Longrightarrow dnd_n divise 2(3n+15)−3(2n+8)=62(3n+15)-3(2n+8)=6.

2. dn=6  ⟺  6d_n=6\iff6 divise 2n+82n+8 et 66 divise 3n+153n+15. 66 divise 2n+8  ⟺  32n+8\iff3 divise n+4  ⟺  n≡2 [3]n+4\iff n\equiv2\,[3] ; 66 divise 3n+15  ⟺  23n+15\iff2 divise n+5  ⟺  nn+5\iff n impair. Donc dn=6  ⟺  n≡2 [3]d_n=6\iff n\equiv2\,[3] et n≡1 [2]  ⟺  n≡5 [6]n\equiv1\,[2]\iff n\equiv5\,[6].

Exercice 46 — PGCD de nombres de Mersenne Difficile ★★★★★

Soient a,b∈N∗a,b\in\N^* avec a≥3a\ge3 et aa impair. On pose d=PGCD⁡(2a−1;2b+1)d=\pgcd\left(2^a-1;2^b+1\right).

  1. Montrer que 2ab≡1 [d]2^{ab}\equiv1\,[d].
  2. Montrer que 2ab≡−1 [d]2^{ab}\equiv-1\,[d].
  3. En déduire que d∈{1;2}d\in\{1;2\}.
  4. Montrer que d=1d=1.
Voir la solution

1. dd divise 2a−12^a-1, donc 2a≡1 [d]2^a\equiv1\,[d] et 2ab=(2a)b≡1 [d]2^{ab}=\left(2^a\right)^b\equiv1\,[d].

2. dd divise 2b+12^b+1, donc 2b≡−1 [d]2^b\equiv-1\,[d] et 2ab=(2b)a≡(−1)a=−1 [d]2^{ab}=\left(2^b\right)^a\equiv(-1)^a=-1\,[d] (aa impair).

3. Par transitivité 1≡−1 [d]1\equiv-1\,[d] : dd divise 22, donc d∈{1;2}d\in\{1;2\}.

4. Raisonnement par l’absurde. Supposons d=2d=2 : alors 22 divise 2a−12^a-1, qui est impair (a≥1a\ge1) : contradiction. Donc d=1d=1.

Exercice 47 — Tour de puissances Difficile ★★★★☆

Montrer que pour tout n∈Nn\in\N, 24n+1+5≡0 [21]2^{4^{n+1}}+5\equiv0\,[21].

Voir la solution

26=64=63+1≡1 [21]2^6=64=63+1\equiv1\,[21]. Montrons d’abord que 4m≡4 [6]4^m\equiv4\,[6] pour tout m∈N∗m\in\N^* (raisonnement par récurrence) :

  • Initialisation. Pour m=1m=1, on a 41=4≡4 [6]4^1=4\equiv4\,[6].
  • Hérédité. Soit m∈N∗m\in\N^*, on suppose 4m≡4 [6]4^m\equiv4\,[6] : il existe k∈Nk\in\N tel que 4m=6k+44^m=6k+4. Alors 4m+1=24k+16=6(4k+2)+4≡4 [6]4^{m+1}=24k+16=6(4k+2)+4\equiv4\,[6].
  • Conclusion. D’après le principe du raisonnement par récurrence, 4m≡4 [6]4^m\equiv4\,[6] pour tout m∈N∗m\in\N^*.

Soit n∈Nn\in\N : il existe k∈Nk\in\N tel que 4n+1=6k+44^{n+1}=6k+4, d’où 24n+1=(26)k×24≡16 [21]2^{4^{n+1}}=\left(2^6\right)^k\times2^4\equiv16\,[21] et 24n+1+5≡21≡0 [21]2^{4^{n+1}}+5\equiv21\equiv0\,[21].

Exercice 48 — Quotient et reste liés Moyen ★★★☆☆

Déterminer les entiers naturels nn tels que, dans la D.E. de nn par 2525, le quotient soit un entier p∈Np\in\N et le reste p2p^2.

Voir la solution

n=25p+p2n=25p+p^2 avec 0≤p2<250\le p^2<25, donc p∈{0;1;2;3;4}p\in\{0;1;2;3;4\} et n∈{0;26;54;84;116}n\in\{0;26;54;84;116\} (réciproquement ces valeurs conviennent par unicité de la D.E.).

Exercice 49 — Quotient Difficile ★★★★☆

Soient b∈N∗b\in\N^* et a∈Za\in\Z. On note qq le quotient de la D.E. de a−1a-1 par bb. Déterminer le quotient de la D.E. de ab9−1ab^9-1 par b10b^{10}.

Voir la solution

a−1=bq+ra-1=bq+r avec 0≤r≤b−10\le r\le b-1. Alors ab9−1=(bq+r+1)b9−1=qb10+[(r+1)b9−1]ab^9-1=(bq+r+1)b^9-1=qb^{10}+\left[(r+1)b^9-1\right] et 0≤b9−1≤(r+1)b9−1≤b⋅b9−1<b100\le b^9-1\le(r+1)b^9-1\le b\cdot b^9-1<b^{10}. Par unicité, le quotient est qq (et le reste (r+1)b9−1(r+1)b^9-1).

Exercice 50 — Binôme et congruences Difficile ★★★★★

  1. Montrer que pour tout n∈N∗n\in\N^*, (n+2)n+2−2n+2(n+1)≡0 [n2](n+2)^{n+2}-2^{n+2}(n+1)\equiv0\,[n^2].
  2. Montrer que 7777≡3 [10]7^{7^{7^7}}\equiv3\,[10].
Voir la solution

1. Binôme (Ch. 13) : (n+2)n+2=∑k=0n+2Cn+2knk2n+2−k(n+2)^{n+2}=\sum_{k=0}^{n+2}C_{n+2}^kn^k2^{n+2-k}. Pour k≥2k\ge2, n2n^2 divise nkn^k ; donc (n+2)n+2≡2n+2+(n+2)n2n+1 [n2](n+2)^{n+2}\equiv2^{n+2}+(n+2)n2^{n+1}\,[n^2]. Or (n+2)n2n+1=n22n+1+n2n+2≡n2n+2 [n2](n+2)n2^{n+1}=n^22^{n+1}+n2^{n+2}\equiv n2^{n+2}\,[n^2]. D’où (n+2)n+2≡2n+2(1+n) [n2](n+2)^{n+2}\equiv2^{n+2}(1+n)\,[n^2], ce qu’il fallait démontrer.

2. 74=2401≡1 [10]7^4=2401\equiv1\,[10]. Posons E=777E=7^{7^7}. Comme 7≡−1 [4]7\equiv-1\,[4] et 777^7 est impair, E≡(−1)77=−1≡3 [4]E\equiv(-1)^{7^7}=-1\equiv3\,[4] : E=4k+3E=4k+3 avec k∈Nk\in\N. Donc 7E=(74)k73≡343≡3 [10]7^E=\left(7^4\right)^k7^3\equiv343\equiv3\,[10].

Quiz — testez-vous

20 questions tirées au hasard parmi 33.

← Retour aux chapitres 1BAC SM