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

Chapitre 14 — Arithmétique dans ℤ

Semestre 2

Chargement du PDF…

📄 CoursOuvrir le PDF · Télécharger
📄 Série d’exercicesOuvrir le PDF · Télécharger
📄 Corrigé de la sérieOuvrir le PDF · Télécharger

Cours

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

Prérequis. Ensembles $\N$ et $\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 « $a$ divise $b$ » en toutes lettres.

I. Divisibilité dans $\Z$

1) Définition

Définition 1

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

Exemple 1

Montrer que $3$ divise $-12$ . Que dire de $0$ , de $1$ et de $-1$ vis-à-vis de la divisibilité ?

Voir la solution

$3$ divise $-12$ car $-12=(-4)\times3$ ; $0$ est multiple de tout entier ; $1$ et $-1$ divisent tout entier.

2) Propriétés

Propriété 1

Soient $a,b,c\in\Z$ .

$a$ divise $a$ ; si $a$ divise $b$ et $b$ divise $c$ , alors $a$ divise $c$ (transitivité).
Si $a$ divise $b$ et $b$ divise $a$ , alors $|a|=|b|$ .
Si $a$ divise $b$ et $a$ divise $c$ , alors pour tous $u,v\in\Z$ , $a$ divise $ub+vc$ (combinaison linéaire).
Si $a$ divise $b$ et $b\neq0$ , alors $|a|\le|b|$ .

Voir la solution

Preuve de la combinaison linéaire (raisonnement direct). $a$ divise $b$ et $a$ divise $c$ $\Longrightarrow$ il existe $k,k'\in\Z$ tels que $b=ka$ et $c=k'a$ $\Longrightarrow$ $ub+vc=(uk+vk')a$ avec $uk+vk'\in\Z$ $\Longrightarrow$ $a$ divise $ub+vc$ .

Exemple 2

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

Voir la solution

Soit $n\in\Z$ tel que $n+2$ divise $3n+1$ . Comme $n+2$ divise $3(n+2)$ , il divise $3(n+2)-(3n+1)=5$ : donc $n+2\in\{-5;-1;1;5\}$ , soit $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\in\Z$ et $b\in\N^*$ . Il existe un unique couple $(q;r)\in\Z\times\N$ tel que $a=bq+r$ et $0\le r<b$ . $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ .

Exemple 3

Déterminer le quotient et le reste de la division euclidienne de $-23$ par $5$ .

Voir la solution

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

2) Conséquence

Propriété 2

Soit $b\in\N^*$ . Tout entier $a$ s’écrit sous l’une des formes $bk$ , $bk+1$ , …, $bk+(b-1)$ avec $k\in\Z$ . En particulier tout entier est de la forme $2k$ ou $2k+1$ , et de la forme $3k$ , $3k+1$ ou $3k+2$ .

Exemple 4

Montrer que, pour tout $n\in\Z$ , $n(n+1)(n+2)$ est divisible par $3$ .

Voir la solution

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

III. Congruences modulo $n$

1) Définition

Définition 2

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

Propriété 3

Si $r$ est le reste de la division euclidienne de $a$ par $n$ , alors $a\equiv r\,[n]$ et $0\le r<n$ . Réciproquement, si $a\equiv r\,[n]$ et $0\le r<n$ , alors $r$ est ce reste.

2) Compatibilité avec les opérations

Propriété 4

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

$a+c\equiv b+d\,[n]$ et $a-c\equiv b-d\,[n]$ ;
$ac\equiv bd\,[n]$ ;
pour tout $k\in\N$ : $a^k\equiv b^k\,[n]$ ;
la relation $\equiv$ est réflexive, symétrique et transitive.

Voir la solution

Preuve de $a^k\equiv b^k\,[n]$ (raisonnement par récurrence sur $k$ ). Initialisation : pour $k=0$ , on a $a^0=1\equiv1=b^0\,[n]$ . Hérédité : soit $k\in\N$ , on suppose $a^k\equiv b^k\,[n]$ ; comme $a\equiv b\,[n]$ , la compatibilité avec le produit donne $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, $a^k\equiv b^k\,[n]$ pour tout $k\in\N$ .

Exemple 5

Déterminer le reste de $2^{2027}$ dans la division par $7$ .

Voir la solution

Reste de $2^{2027}$ dans la division par $7$ : $2^3=8\equiv1\,[7]$ et $2027=3\times675+2$ , donc $2^{2027}=(2^3)^{675}\times2^2\equiv1\times4=4\,[7]$ . Le reste est $4$ .

IV. Nombres premiers

1) Définition et critère

Définition 3

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

Propriété 5

Tout entier naturel $n\ge2$ admet au moins un diviseur premier.
Si $n\ge2$ n’est pas premier, il admet un diviseur premier $p$ tel que $p^2\le n$ . Donc si aucun nombre premier $p$ tel que $p^2\le n$ ne divise $n$ , alors $n$ 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 $p_1,\dots,p_k$ et posons $N=p_1p_2\cdots p_k+1\ge2$ . $N$ admet un diviseur premier, donc un $p_i$ divise $N$ ; comme $p_i$ divise aussi $p_1\cdots p_k$ , il divise la différence $1$ : contradiction avec $p_i\ge2$ .

2) Décomposition en facteurs premiers

Théorème 2 (admis)

Tout entier $n\ge2$ s’écrit de façon unique (à l’ordre près) $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ où $p_1<\dots<p_k$ sont premiers et $\alpha_i\in\N^*$ .

Propriété 6 : nombre de diviseurs

Avec la décomposition ci-dessus, les diviseurs positifs de $n$ sont les $p_1^{\beta_1}\cdots p_k^{\beta_k}$ avec $0\le\beta_i\le\alpha_i$ ; leur nombre est (principe multiplicatif, Ch. 13) $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$ .

Exemple 6

Combien $360$ possède-t-il de diviseurs positifs ?

Voir la solution

$360=2^3\times3^2\times5$ possède $4\times3\times2=24$ diviseurs positifs.

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

Si un nombre premier $p$ divise un produit $ab$ ( $a,b\in\Z$ ), alors $p$ divise $a$ ou $p$ divise $b$ .

V. PGCD et PPCM

1) Définitions

Définition 4

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

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

Propriété 8

Soient $a,b\in\Z^*$ .

Pour tout $k\in\Z$ : $a\wedge b=b\wedge(a-kb)$ . En particulier, si $a=bq+r$ (division euclidienne), $a\wedge b=b\wedge r$ .
Algorithme d’Euclide : on effectue des divisions successives ; le PGCD est le dernier reste non nul.
Les diviseurs communs à $a$ et $b$ sont exactement les diviseurs de $a\wedge b$ ; les multiples communs sont les multiples de $a\vee b$ .
$(a\wedge b)\times(a\vee b)=|ab|$ ; pour $k\in\N^*$ : $(ka)\wedge(kb)=k(a\wedge b)$ .
Si $d=a\wedge b$ , alors $a=da'$ et $b=db'$ avec $a'\wedge b'=1$ .
Avec les décompositions en facteurs premiers : $a\wedge b$ (resp. $a\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)$ par l’algorithme d’Euclide, puis $1071\vee462$ .

Voir la solution

$\pgcd(1071;462)$ : $1071=462\times2+147$ , $462=147\times3+21$ , $147=21\times7+0$ : $1071\wedge462=21$ et $1071\vee462=\frac{1071\times462}{21}=23\,562$ .

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

1) Classes d’équivalence

Définition 5

Soit $n\in\N^*$ , $n\ge2$ . La classe de $a\in\Z$ modulo $n$ est $\overline a=\{b\in\Z\ /\ b\equiv a\,[n]\}=a+n\Z$ . On a $\overline a=\overline b\iff a\equiv b\,[n]$ . L’ensemble des classes est $\Z/n\Z=\{\overline0;\overline1;\dots;\overline{n-1}\}$ ; il a $n$ éléments.

2) Opérations

Propriété 9

On définit $\overline a+\overline b=\overline{a+b}$ et $\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/n\Z$ en testant les $n$ classes, à l’aide d’une table d’addition ou de multiplication.

Exemple 8

Résoudre dans $\Z/5\Z$ l’équation $\overline3\times\overline x=\overline2$ .

Voir la solution

Dans $\Z/5\Z$ : $\overline3\times\overline x=\overline2$ . Les produits $\overline3\times\overline0,\dots,\overline3\times\overline4$ valent $\overline0,\overline3,\overline1,\overline4,\overline2$ : l’unique solution est $\overline x=\overline4$ .

Résumé

Remarque — l’essentiel

$a$ divise $b$ $\iff$ $\exists k\in\Z$ , $b=ka$ ; un diviseur commun divise toute combinaison linéaire.
Division euclidienne : $a=bq+r$ , $0\le r<b$ ; $a\equiv b\,[n]\iff n$ divise $a-b$ ; congruences compatibles avec $+$ , $\times$ , puissances.
Décomposition en facteurs premiers ; nombre de diviseurs $\prod(\alpha_i+1)$ .
$a\wedge b=b\wedge(a-kb)$ ; algorithme d’Euclide ; $(a\wedge b)(a\vee b)=|ab|$ .
$\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 à $1$ (ou $-1$ ), puis on écrit la D.E. de l’exposant.
Disjonction de cas : on examine tous les restes possibles modulo $n$ (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 « $a$ divise $b$ » 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 ★☆☆☆☆

Déterminer et dénombrer les diviseurs positifs de $156$ .
Déterminer tous les diviseurs de $-8$ dans $\Z$ .

Voir la solution

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

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

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

Soient $a,b,c,x,y\in\Z$ . Montrer que : a. si $a$ divise $2b+c$ et $a$ divise $b+c$ , alors $a$ divise $c$ ; b. si $a$ divise $2b+3c$ et $a$ divise $b+c$ , alors $a$ divise $c$ ; c. si $a$ divise $x-y$ et $a$ divise $b-c$ , alors $a$ divise $xb-cy$ .
Soient $a,n\in\Z$ tels que $a$ divise $12n+1$ et $a$ divise $-2n+3$ . Montrer que $a$ divise $19$ .
Soient $d,n\in\Z$ tels que $d$ divise $n^2+3$ et $d$ divise $2n-1$ . Montrer que $d$ divise $13$ .

Voir la solution

Raisonnement direct, par combinaisons linéaires.

1. a. $a$ divise $2b+c$ et $a$ divise $b+c$ $\Longrightarrow$ $a$ divise $2(b+c)-(2b+c)=c$ .

1. b. $a$ divise $2b+3c$ et $a$ divise $b+c$ $\Longrightarrow$ $a$ divise $(2b+3c)-2(b+c)=c$ .

1. c. On remarque que $xb-cy=x(b-c)+c(x-y)$ . Donc $a$ divise $b-c$ et $a$ divise $x-y$ $\Longrightarrow$ $a$ divise $x(b-c)+c(x-y)=xb-cy$ .

2. $a$ divise $12n+1$ et $a$ divise $-2n+3$ $\Longrightarrow$ $a$ divise $(12n+1)+6(-2n+3)=19$ .

3. $d$ divise $n^2+3$ et $d$ divise $2n-1$ $\Longrightarrow$ $d$ divise $4(n^2+3)$ et $d$ divise $(2n-1)(2n+1)=4n^2-1$ $\Longrightarrow$ $d$ divise $4(n^2+3)-(4n^2-1)=13$ .

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

Soient $a,x\in\Z$ . Montrer que si $a$ divise $5x+7$ et $a$ divise $2x-3$ , alors $a$ divise $29$ .

Voir la solution

$a$ divise $5x+7$ et $a$ divise $2x-3$ $\Longrightarrow$ $a$ divise $2(5x+7)-5(2x-3)=14+15=29$ .

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

Montrer que pour tout $n\in\N$ , $3$ divise $4^n-1$ .

Voir la solution

Raisonnement par récurrence. Pour $n\in\N$ , notons $P(n)$ : « $3$ divise $4^n-1$ ».

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

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

Déterminer les entiers relatifs $n$ , $n\neq1$ , tels que $n-1$ divise $2n+7$ .

Voir la solution

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

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

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

Voir la solution

Par division : $n^3+8=(n+4)(n^2-4n+16)-56$ . Donc $\frac{n^3+8}{n+4}=n^2-4n+16-\frac{56}{n+4}$ et $\frac{n^3+8}{n+4}\in\Z\iff n+4$ divise $56$ . Les diviseurs de $56=2^3\times7$ sont $\pm1,\pm2,\pm4,\pm7,\pm8,\pm14,\pm28,\pm56$ . Donc $n=d-4$ avec $d$ l’un de ces diviseurs : $n\in\{-60;-32;-18;-12;-11;-8;-6;-5;-3;-2;0;3;4;10;24;52\}$ (seize valeurs).

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

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

$x^2-y^2=32$ avec $x>y$ ;
$2xy+2x+y=99$ .

Voir la solution

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

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

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

Déterminer le reste de la D.E. par $9$ de chacun des nombres $23451^{100}$ et $100^{23451}+23451^{100}$ .

Voir la solution

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

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

Montrer que $5^8\equiv-1\,[17]$ .
Déterminer les restes de la D.E. par $17$ des nombres $5^{16}$ et $5^{500}$ .

Voir la solution

1. $5^2=25\equiv8\,[17]$ , $5^4\equiv64\equiv13\equiv-4\,[17]$ , $5^8\equiv(-4)^2=16\equiv-1\,[17]$ .

2. $5^{16}=\left(5^8\right)^2\equiv(-1)^2=1\,[17]$ : reste $1$ . $500=16\times31+4$ , donc $5^{500}=\left(5^{16}\right)^{31}\times5^4\equiv1\times13\,[17]$ : reste $13$ .

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

Soient $a,b\in\Z$ tels que le reste de la D.E. de $a$ par $19$ est $17$ et celui de $b$ par $19$ est $15$ . Déterminer le reste de la D.E. par $19$ de :

$a+b$ ;
$a^2+b^2$ ;
$2a-5b$ .

Voir la solution

$a\equiv17\equiv-2\,[19]$ et $b\equiv15\equiv-4\,[19]$ .

1. $a+b\equiv-6\equiv13\,[19]$ : reste $13$ . 2. $a^2+b^2\equiv4+16=20\equiv1\,[19]$ : reste $1$ . 3. $2a-5b\equiv-4+20=16\,[19]$ : reste $16$ .

Exercice 11 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de $3^{2007}$ par $2$ , puis par $13$ .

Voir la solution

$3^{2007}$ est impair : le reste par $2$ est $1$ . $3^3=27\equiv1\,[13]$ et $2007=3\times669$ , donc $3^{2007}=\left(3^3\right)^{669}\equiv1\,[13]$ : reste $1$ .

Exercice 12 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de $73^{2019}$ par $7$ .

Voir la solution

$73=7\times10+3$ , donc $73\equiv3\,[7]$ ; $3^3=27\equiv-1\,[7]$ , donc $3^6\equiv1\,[7]$ . $2019=6\times336+3$ : $73^{2019}\equiv\left(3^6\right)^{336}\times3^3\equiv-1\equiv6\,[7]$ . Reste $6$ .

Exercice 13 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. de $19^{52}\times23^{41}$ par $7$ .

Voir la solution

$19\equiv5\equiv-2\,[7]$ et $23\equiv2\,[7]$ ; $2^3\equiv1\,[7]$ . $19^{52}\equiv(-2)^{52}=2^{52}=\left(2^3\right)^{17}\times2\equiv2\,[7]$ et $23^{41}\equiv2^{41}=\left(2^3\right)^{13}\times2^2\equiv4\,[7]$ . Donc $19^{52}\times23^{41}\equiv8\equiv1\,[7]$ : reste $1$ .

Exercice 14 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. par $5$ du nombre $22^{33}+33^{22}$ .

Voir la solution

$22\equiv2\,[5]$ , $2^4=16\equiv1\,[5]$ , $33=4\times8+1$ : $22^{33}\equiv2\,[5]$ . $33\equiv3\equiv-2\,[5]$ , $22=4\times5+2$ : $33^{22}\equiv(-2)^{22}=\left(2^4\right)^5\times4\equiv4\,[5]$ . Somme : $6\equiv1\,[5]$ , reste $1$ .

Exercice 15 — Discussion suivant $n$ Moyen ★★★☆☆

Déterminer, suivant les valeurs de $n\in\N$ , le reste de la D.E. de $3^n$ par $7$ .
En déduire le reste de la D.E. de $2019^{2019}$ par $7$ .

Voir la solution

1. $3^1\equiv3$ , $3^2\equiv2$ , $3^3\equiv6$ , $3^4\equiv4$ , $3^5\equiv5$ , $3^6\equiv1\,[7]$ . Soit $n=6k+r$ ( $k\in\N$ , $0\le r\le5$ ) : $3^n=\left(3^6\right)^k3^r\equiv3^r\,[7]$ . Le reste vaut $1,3,2,6,4,5$ selon que $r=0,1,2,3,4,5$ .

2. $2019=7\times288+3$ : $2019\equiv3\,[7]$ donc $2019^{2019}\equiv3^{2019}\,[7]$ ; $2019=6\times336+3$ , donc $r=3$ et le reste est $6$ .

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

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

$\overline2x=\overline3$ ;
$x^2+\overline3x=\overline0$ ;
$\overline{2013}x^3+\overline2x=\overline k$ , en discutant suivant $\overline k\in\Z/4\Z$ .

Voir la solution

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

1. $\overline2x$ prend les valeurs $\overline0,\overline2,\overline0,\overline2$ : jamais $\overline3$ . $S=\emptyset$ .

2. $x^2+\overline3x$ vaut $\overline0,\overline0,\overline{10}=\overline2,\overline{18}=\overline2$ pour $x=\overline0,\overline1,\overline2,\overline3$ . $S=\{\overline0;\overline1\}$ .

3. $\overline{2013}=\overline1$ (car $2013=4\times503+1$ ). $x^3+\overline2x$ vaut $\overline0,\overline3,\overline{12}=\overline0,\overline{33}=\overline1$ . D’où : si $\overline k=\overline0$ , $S=\{\overline0;\overline2\}$ ; si $\overline k=\overline1$ , $S=\{\overline3\}$ ; si $\overline k=\overline2$ , $S=\emptyset$ ; si $\overline k=\overline3$ , $S=\{\overline1\}$ .

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

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

Voir la solution

$x+\overline3y=\overline1\iff x=\overline1-\overline3y$ . Pour chaque $y$ , $x$ est unique : $S=\{(\overline1;\overline0);(\overline3;\overline1);(\overline0;\overline2);(\overline2;\overline3);(\overline4;\overline4)\}$ (cinq couples).

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

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

Voir la solution

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

Exercice 19 — Modulo 10 Moyen ★★★☆☆

Déterminer, suivant les valeurs de $n\in\N$ , le reste de la D.E. de $3^n$ par $10$ .
En déduire le chiffre des unités du nombre $2029^{2020}$ .
Déterminer les entiers $n\in\N$ tels que $3^n+5n+2\equiv0\,[10]$ .

Voir la solution

1. $3^0\equiv1$ , $3^1\equiv3$ , $3^2\equiv9$ , $3^3\equiv7$ , $3^4\equiv1\,[10]$ . Pour $n=4k+r$ ( $0\le r\le3$ ) : $3^n\equiv3^r\,[10]$ ; le reste vaut $1,3,9,7$ pour $r=0,1,2,3$ .

2. $2029\equiv9\equiv-1\,[10]$ et $2020$ est pair : $2029^{2020}\equiv1\,[10]$ . Le chiffre des unités est $1$ .

3. Disjonction de cas suivant $n$ modulo $4$ (on a $5n\equiv0\,[10]$ si $n$ pair, $5n\equiv5\,[10]$ si $n$ impair). Cas 1 : $n=4k$ : $1+0+2=3\not\equiv0$ . Cas 2 : $n=4k+1$ : $3+5+2=10\equiv0$ : convient. Cas 3 : $n=4k+2$ : $9+0+2=11\not\equiv0$ . Cas 4 : $n=4k+3$ : $7+5+2=14\not\equiv0$ . Les solutions sont les $n\in\N$ tels que $n\equiv1\,[4]$ .

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

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

Voir la solution

$24537\equiv7\,[10]$ ; $7^2\equiv9$ , $7^4\equiv81\equiv1\,[10]$ ; $2018=4\times504+2$ : $24537^{2018}\equiv7^2\equiv9\,[10]$ . Chiffre des unités : $9$ .

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

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

Voir la solution

$2^6=64\equiv1\,[9]$ : $2^n\,[9]$ ne dépend que de $n$ modulo $6$ ; $n^2\,[9]$ ne dépend que de $n$ modulo $9$ . On étudie donc $n$ modulo $18=\operatorname{PPCM}(6;9)$ : pour $n=18k+r$ , $2^n\equiv2^r$ et $n^2\equiv r^2\,[9]$ . On teste $r\in\{0;\dots;17\}$ : les restes de $2^r$ sont $1,2,4,8,7,5$ (période $6$ ) et ceux de $r^2$ sont $0,1,4,0,7,7,0,4,1$ (période $9$ ). L’égalité n’a lieu que pour $r=2$ ( $4=4$ ) et $r=4$ ( $7=7$ ). Les solutions sont les $n\in\N$ tels que $n\equiv2\,[18]$ ou $n\equiv4\,[18]$ .

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

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

Voir la solution

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

Exercice 23 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de $22^{33}\times33^{22}$ par $5$ .

Voir la solution

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

Exercice 24 — Restes Facile ★☆☆☆☆

Déterminer le reste de la D.E. de $3^{2019}$ par $2$ et par $13$ .

Voir la solution

$3^{2019}$ est impair : reste $1$ par $2$ . $3^3\equiv1\,[13]$ et $2019=3\times673$ : $3^{2019}\equiv1\,[13]$ , reste $1$ .

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

Montrer que pour tout $n\in\N^*$ , $2^{2n}+6n-1$ est divisible par $9$ .
En déduire que pour tout $n\in\N^*$ , $4^n\equiv3n+1\,[9]$ .

Voir la solution

1. Raisonnement par récurrence.

Initialisation. Pour $n=1$ , on a $2^2+6-1=9$ : $9$ divise $9$ .
Hérédité. Soit $n\in\N^*$ , on suppose que $9$ divise $2^{2n}+6n-1$ : il existe $k\in\N$ tel que $2^{2n}+6n-1=9k$ , soit $2^{2n}=9k-6n+1$ . Alors $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\in\Z$ (et même dans $\N$ puisque le nombre est positif) : $9$ divise $2^{2(n+1)}+6(n+1)-1$ .
Conclusion. D’après le principe du raisonnement par récurrence, $9$ divise $2^{2n}+6n-1$ pour tout $n\in\N^*$ .

2. Soit $n\in\N^*$ : $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 $11$ du nombre $1653^{351}+43^{137}$ .

Voir la solution

$1653=11\times150+3$ , donc $1653\equiv3\,[11]$ ; $3^5=243=11\times22+1\equiv1\,[11]$ et $351=5\times70+1$ : $1653^{351}\equiv3\,[11]$ . $43\equiv-1\,[11]$ et $137$ est impair : $43^{137}\equiv-1\,[11]$ . Somme : $3-1=2$ ; reste $2$ .

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

Montrer que $7$ divise $1^{2019}+2^{2019}+3^{2019}+4^{2019}+5^{2019}+6^{2019}$ .

Voir la solution

Pour $k\in\{1;2;3\}$ : $7-k\equiv-k\,[7]$ et $2019$ est impair, donc $(7-k)^{2019}\equiv(-k)^{2019}=-k^{2019}\,[7]$ . En groupant $1$ avec $6$ , $2$ avec $5$ , $3$ avec $4$ : la somme est $\equiv0\,[7]$ , donc $7$ la divise.

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

Montrer que pour tout $n\in\Z$ , $\pgcd(n;n+1)=1$ .

Voir la solution

Raisonnement direct. Soit $d=\pgcd(n;n+1)$ : $d$ divise $n$ et $d$ divise $n+1$ $\Longrightarrow$ $d$ divise $(n+1)-n=1$ $\Longrightarrow$ $d=1$ (car $d\ge1$ ).

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

Pour $n\in\N$ , on pose $U_n=4^n-3n-1$ .

Montrer que pour tout $n\in\N$ , $U_{n+1}=4U_n+9n$ .
En déduire que pour tout $n\in\N$ , $9$ divise $4^n-3n-1$ .

Voir la solution

1. Soit $n\in\N$ : $4U_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=0$ , on a $4^0-0-1=0$ et $9$ divise $0$ .
Hérédité. Soit $n\in\N$ , on suppose que $9$ divise $4^n-3n-1$ : il existe $k\in\N$ tel que $4^n-3n-1=9k$ . D’après 1., $4^{n+1}-3(n+1)-1=4\times9k+9n=9(4k+n)$ avec $4k+n\in\N$ .
Conclusion. D’après le principe du raisonnement par récurrence, $9$ divise $4^n-3n-1$ pour tout $n\in\N$ .

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

Pour $n\in\N$ , on pose $\alpha_n=n^4-n^2+16$ .

Montrer que $n^2+3n+4$ et $n^2-3n+4$ sont des entiers naturels pairs, et que $\alpha_n=(n^2+3n+4)(n^2-3n+4)$ .
En déduire que $\alpha_n$ n’est pas premier.

Voir la solution

1. $n^2+3n=n(n+3)$ : l’un des facteurs $n$ , $n+3$ est pair (ils sont de parités différentes), donc $n^2+3n+4$ est pair ; de même $n^2-3n=n(n-3)$ est pair. Ce sont des entiers naturels car $n^2-3n+4=\left(n-\frac32\right)^2+\frac74>0$ . Enfin $(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 $\ge2$ et le produit $\alpha_n$ est divisible par $4$ ; comme $\alpha_n\ge16>4$ (car $n^4-n^2=n^2(n^2-1)\ge0$ ), $4$ est un diviseur de $\alpha_n$ différent de $1$ et de $\alpha_n$ : $\alpha_n$ n’est pas premier.

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

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

Montrer que $\pgcd(A;B)=\pgcd(n+2;7)$ .
Déterminer l’entier naturel $n$ tel que $\dfrac{n^2+3}{n+2}\in\N$ .

Voir la solution

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

2. $\frac{n^2+3}{n+2}\in\N\iff n+2$ divise $n^2+3\iff n+2$ divise $7$ (car $n+2$ divise $(n+2)(n-2)$ ) $\iff n+2=7$ (car $n+2\ge2$ ) $\iff n=5$ . Vérification : $\frac{28}7=4$ .

Exercice 32 — PGCD Moyen ★★★☆☆

Pour $n\in\N^*$ , on pose $a_n=\left(25^n-1\right)\left(36^n-1\right)$ et $b_n=\left(5^n-1\right)\left(6^n-1\right)$ . Calculer $\pgcd(a_n;b_n)$ .

Voir la solution

$a_n=(5^n-1)(5^n+1)(6^n-1)(6^n+1)=b_n\times(5^n+1)(6^n+1)$ : $b_n$ divise $a_n$ et $b_n>0$ (pour $n\ge1$ ). Donc $\pgcd(a_n;b_n)=b_n=(5^n-1)(6^n-1)$ .

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

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

$x^2-y^2=45$ avec $x>y$ ;
$xy+2x+3y=24$ .

Voir la solution

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

2. $xy+2x+3y=24\iff(x+3)(y+2)=30$ avec $x+3\ge3$ et $y+2\ge2$ : $(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)\}$ .

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

Déterminer tous les entiers $n\in\Z$ , $n\neq-3$ , tels que $n+3$ divise $2n+13$ .

Voir la solution

$2n+13=2(n+3)+7$ : $n+3$ divise $2n+13\iff n+3$ divise $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\in\Z$ , $n\neq-4$ , tels que $\dfrac{3n+8}{n+4}$ soit un entier relatif.

Voir la solution

$\frac{3n+8}{n+4}=3-\frac4{n+4}$ ; il est entier $\iff n+4$ divise $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)$ et $m=\operatorname{PPCM}(8316;1980)$ .

Voir la solution

$8316=2^2\times3^3\times7\times11$ , $1080=2^3\times3^3\times5$ , $1980=2^2\times3^2\times5\times11$ . $d=\pgcd(8316;1080)=2^2\times3^3=108$ ; $m=2^2\times3^3\times5\times7\times11=41\,580$ .

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

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

Voir la solution

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

Exercice 38 — Quotients successifs Difficile ★★★★☆

Soient $n\in\N$ et $a,b\in\N^*$ . Montrer que si $q$ est le quotient de la D.E. de $n$ par $a$ et $q'$ celui de la D.E. de $q$ par $b$ , alors $q'$ est aussi le quotient de la D.E. de $n$ par $ab$ .

Voir la solution

Raisonnement direct. $n=aq+r$ avec $0\le r\le a-1$ et $q=bq'+r'$ avec $0\le r'\le b-1$ . Alors $n=abq'+(ar'+r)$ et $0\le ar'+r\le a(b-1)+a-1=ab-1<ab$ . Par unicité de la D.E. de $n$ par $ab$ , le quotient est $q'$ (et le reste $ar'+r$ ).

Exercice 39 — Restes Facile ★★☆☆☆

Déterminer le reste de la D.E. de $19^{41}\times23^{52}$ par $7$ .

Voir la solution

$19\equiv-2$ et $23\equiv2\,[7]$ : $19^{41}\equiv-2^{41}=-\left(2^3\right)^{13}2^2\equiv-4\,[7]$ et $23^{52}\equiv2^{52}\equiv2\,[7]$ . Produit : $-8\equiv-1\equiv6\,[7]$ ; reste $6$ .

Exercice 40 — Congruences Facile ★★☆☆☆

Montrer que pour tout $n\in\N^*$ , $(n+1)^{2019}-1\equiv0\,[n]$ .
Montrer que pour tout $n\in\N$ , $4^{2n+2}\equiv1\,[15]$ .

Voir la solution

1. Soit $n\in\N^*$ : $n+1\equiv1\,[n]\Longrightarrow(n+1)^{2019}\equiv1\,[n]\Longrightarrow(n+1)^{2019}-1\equiv0\,[n]$ .

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

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

Résoudre dans $\Z/5\Z$ l’équation $x^2-x-\overline2=\overline0$ .

Voir la solution

On teste les cinq classes : $x^2-x-\overline2$ vaut $\overline{-2}=\overline3$ , $\overline3$ , $\overline0$ , $\overline4$ , $\overline{10}=\overline0$ pour $x=\overline0,\dots,\overline4$ . $S=\{\overline2;\overline4\}$ .

Exercice 42 — PGCD Facile ★★☆☆☆

Soient $a,b,c,d\in\Z$ , avec $b\neq0$ , tels que $a=bc+d$ .

Montrer que $\pgcd(a;b)=\pgcd(b;d)$ .
En déduire que $\pgcd(a;b)=\pgcd(b;a-bc)$ .

Voir la solution

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

2. On applique 1. avec $d=a-bc$ .

Exercice 43 — PGCD Moyen ★★★☆☆

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

Voir la solution

Soit $\delta=\pgcd(A;B)$ : $\delta$ divise $A$ et $B$ $\Longrightarrow$ $\delta$ divise $7B-9A=(315a+532)-(315a+513)=19$ . Comme $19$ est premier, $\delta\in\{1;19\}$ .

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

Soient $x,y\in\N^*$ , $a=9x+4y$ et $b=2x+y$ . Montrer que $\pgcd(x;y)=\pgcd(a;b)$ .
Soit $n\in\N$ ; on pose $a=n^2+5n+13$ et $b=n+3$ . a. Montrer que $\pgcd(a;b)=\pgcd(b;7)$ . b. En déduire les valeurs possibles de $\pgcd(a;b)$ . c. Montrer que $n\equiv4\,[7]\iff\pgcd(a;b)=7$ . d. En déduire les valeurs de $n$ telles que $\pgcd(a;b)=1$ .

Voir la solution

1. $a-4b=x$ et $9b-2a=y$ . Tout diviseur commun de $x,y$ divise $a=9x+4y$ et $b=2x+y$ ; tout diviseur commun de $a,b$ divise $x=a-4b$ et $y=9b-2a$ . Mêmes diviseurs communs, donc $\pgcd(x;y)=\pgcd(a;b)$ .

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

2. b. $\pgcd(b;7)$ divise $7$ , premier : $\pgcd(a;b)\in\{1;7\}$ .

2. c. $\pgcd(a;b)=7\iff7$ divise $n+3\iff n\equiv-3\,[7]\iff n\equiv4\,[7]$ .

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

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

Soit $n\in\N$ ; on pose $d_n=\pgcd(2n+8;3n+15)$ .

Montrer que $d_n$ divise $6$ .
Déterminer les entiers naturels $n$ tels que $d_n=6$ .

Voir la solution

1. $d_n$ divise $2n+8$ et $3n+15$ $\Longrightarrow$ $d_n$ divise $2(3n+15)-3(2n+8)=6$ .

2. $d_n=6\iff6$ divise $2n+8$ et $6$ divise $3n+15$ . $6$ divise $2n+8\iff3$ divise $n+4\iff n\equiv2\,[3]$ ; $6$ divise $3n+15\iff2$ divise $n+5\iff n$ impair. Donc $d_n=6\iff n\equiv2\,[3]$ et $n\equiv1\,[2]\iff n\equiv5\,[6]$ .

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

Soient $a,b\in\N^*$ avec $a\ge3$ et $a$ impair. On pose $d=\pgcd\left(2^a-1;2^b+1\right)$ .

Montrer que $2^{ab}\equiv1\,[d]$ .
Montrer que $2^{ab}\equiv-1\,[d]$ .
En déduire que $d\in\{1;2\}$ .
Montrer que $d=1$ .

Voir la solution

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

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

3. Par transitivité $1\equiv-1\,[d]$ : $d$ divise $2$ , donc $d\in\{1;2\}$ .

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

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

Montrer que pour tout $n\in\N$ , $2^{4^{n+1}}+5\equiv0\,[21]$ .

Voir la solution

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

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

Soit $n\in\N$ : il existe $k\in\N$ tel que $4^{n+1}=6k+4$ , d’où $2^{4^{n+1}}=\left(2^6\right)^k\times2^4\equiv16\,[21]$ et $2^{4^{n+1}}+5\equiv21\equiv0\,[21]$ .

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

Déterminer les entiers naturels $n$ tels que, dans la D.E. de $n$ par $25$ , le quotient soit un entier $p\in\N$ et le reste $p^2$ .

Voir la solution

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

Exercice 49 — Quotient Difficile ★★★★☆

Soient $b\in\N^*$ et $a\in\Z$ . On note $q$ le quotient de la D.E. de $a-1$ par $b$ . Déterminer le quotient de la D.E. de $ab^9-1$ par $b^{10}$ .

Voir la solution

$a-1=bq+r$ avec $0\le r\le b-1$ . Alors $ab^9-1=(bq+r+1)b^9-1=qb^{10}+\left[(r+1)b^9-1\right]$ et $0\le b^9-1\le(r+1)b^9-1\le b\cdot b^9-1<b^{10}$ . Par unicité, le quotient est $q$ (et le reste $(r+1)b^9-1$ ).

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

Montrer que pour tout $n\in\N^*$ , $(n+2)^{n+2}-2^{n+2}(n+1)\equiv0\,[n^2]$ .
Montrer que $7^{7^{7^7}}\equiv3\,[10]$ .

Voir la solution

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

2. $7^4=2401\equiv1\,[10]$ . Posons $E=7^{7^7}$ . Comme $7\equiv-1\,[4]$ et $7^7$ est impair, $E\equiv(-1)^{7^7}=-1\equiv3\,[4]$ : $E=4k+3$ avec $k\in\N$ . Donc $7^E=\left(7^4\right)^k7^3\equiv343\equiv3\,[10]$ .

Quiz — testez-vous

20 questions tirées au hasard parmi 33.

Ton prénom (facultatif)

← Retour aux chapitres 1BAC SM

Chapitre 14 — Arithmétique dans ℤ

Cours

I. Divisibilité dans Z\ZZ

1) Définition

2) Propriétés

II. Division euclidienne

1) Théorème

2) Conséquence

III. Congruences modulo nnn

1) Définition

2) Compatibilité avec les opérations

IV. Nombres premiers

1) Définition et critère

2) Décomposition en facteurs premiers

V. PGCD et PPCM

1) Définitions

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

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

1) Classes d’équivalence

2) Opérations

Résumé

Série d’exercices

Exercice 1 — Diviseurs Facile ★☆☆☆☆

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

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

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

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

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

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

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

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

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

Exercice 11 — Restes Facile ★☆☆☆☆

Exercice 12 — Restes Facile ★☆☆☆☆

Exercice 13 — Restes Facile ★★☆☆☆

Exercice 14 — Restes Facile ★★☆☆☆

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

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

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

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

Exercice 19 — Modulo 10 Moyen ★★★☆☆

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

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

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

Exercice 23 — Restes Facile ★☆☆☆☆

Exercice 24 — Restes Facile ★☆☆☆☆

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

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

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

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

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

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

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

Exercice 32 — PGCD Moyen ★★★☆☆

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

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

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

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

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

Exercice 38 — Quotients successifs Difficile ★★★★☆

Exercice 39 — Restes Facile ★★☆☆☆

Exercice 40 — Congruences Facile ★★☆☆☆

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

Exercice 42 — PGCD Facile ★★☆☆☆

Exercice 43 — PGCD Moyen ★★★☆☆

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

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

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

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

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

Exercice 49 — Quotient Difficile ★★★★☆

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

Quiz — testez-vous

I. Divisibilité dans $\Z$

III. Congruences modulo $n$

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

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

Exercice 15 — Discussion suivant $n$ Moyen ★★★☆☆

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

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

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

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

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