Accueil › 1BAC SM › Devoir maison n°3 — Semestre 2

Devoir maison n°3 — Semestre 2

Dénombrement et arithmétique dans ℤ

Chargement du PDF…

📄 ÉnoncéOuvrir le PDF · Télécharger
📄 CorrigéOuvrir le PDF · Télécharger

Remarque — méthodes

Les méthodes sont celles du cours et de la série du chapitre 14 : combinaisons linéaires, congruences, disjonction de cas sur les restes, PGCD (algorithme d’Euclide, décomposition en facteurs premiers). Tous les résultats ont été contrôlés avec Python/sympy (build/verif_lot3.py).

Programme couvert. Chapitre 14 (Arithmétique dans $\Z$ ), avec quelques outils du chapitre 13 (dénombrement des diviseurs). Toute réponse doit être justifiée ; on précisera le type de raisonnement utilisé. On écrit « divise » en toutes lettres.

Exercice 1 — Restes de divisions euclidiennes Facile ★★☆☆☆

Soient $a,b\in\Z$ . Le reste de la division euclidienne de $a$ par $11$ est $2$ , celui de $b$ par $11$ est $7$ . a. Déterminer le reste de la division euclidienne par $11$ de $a+b$ et de $a-b$ . b. En déduire le reste de la division euclidienne de $a^2-b^2$ par $11$ .
Soit $n\in\N^*$ . Déterminer le reste de la division euclidienne : a. de $n^2+n+1$ par $n+1$ ; b. de $4^n+3$ par $2^n+1$ (on distinguera les cas $n=1$ et $n\ge2$ ).
Soit $n\in\N$ . Déterminer le reste de la division euclidienne de $(n+2)^2$ par $n+3$ .

Voir la correction

1. a. $a\equiv2\,[11]$ et $b\equiv7\,[11]$ $\Longrightarrow$ $a+b\equiv9\,[11]$ et $a-b\equiv-5\equiv6\,[11]$ . Les restes sont $9$ et $6$ .

1. b. $a^2-b^2=(a+b)(a-b)\equiv9\times6=54=44+10\equiv10\,[11]$ : reste $10$ .

2. a. $n^2+n+1=(n+1)\times n+1$ et $0\le1<n+1$ (car $n\ge1$ ). Par unicité de la division euclidienne, le reste est $1$ (quotient $n$ ).

2. b. $4^n+3=(2^n)^2-1+4=(2^n+1)(2^n-1)+4$ . Cas 1 : $n\ge2$ : $2^n+1\ge5>4$ , donc $0\le4<2^n+1$ et le reste est $4$ (quotient $2^n-1$ ). Cas 2 : $n=1$ : $4^1+3=7=3\times2+1$ : le reste est $1$ .

3. $(n+2)^2=n^2+4n+4=(n+3)(n+1)+1$ et $0\le1<n+3$ : le reste est $1$ .

Exercice 2 — Divisibilité et équations Moyen ★★★☆☆

Montrer que la somme de trois entiers relatifs consécutifs est un multiple de $3$ .
Résoudre dans $\Z^2$ les équations : a. $x^2-y^2=9$ ; b. $x^2-y^2=401$ (on admet que $401$ est premier).
Soit $n\in\Z$ . Montrer que si $n-2$ est un multiple de $7$ , alors $n^3-1$ est un multiple de $7$ .
Montrer que $13$ divise $2^{70}+3^{70}$ .
Déterminer les entiers naturels $n$ dans chacun des cas suivants : a. $n-2$ divise $n+5$ ; b. $n+1$ divise $n^3+2$ .
Résoudre dans $\Z^2$ l’équation $xy-5x-3y+18=0$ .

Voir la correction

1. Raisonnement direct : $n+(n+1)+(n+2)=3(n+1)$ avec $n+1\in\Z$ : c’est un multiple de $3$ .

2. a. $(x-y)(x+y)=9$ . Les nombres $x-y$ et $x+y$ ont même parité (leur somme est $2x$ ) ; on pose $x-y=d$ et $x+y=\frac9d$ avec $d\in\{\pm1;\pm3;\pm9\}$ , d’où $x=\frac{d+9/d}2$ et $y=\frac{9/d-d}2$ : $S=\{(5;4);(5;-4);(-5;-4);(-5;4);(3;0);(-3;0)\}$ .

2. b. $401$ est premier, donc $d\in\{\pm1;\pm401\}$ : $S=\{(201;200);(201;-200);(-201;-200);(-201;200)\}$ .

3. Raisonnement direct : $n-2$ multiple de $7$ $\Longrightarrow$ $n\equiv2\,[7]$ $\Longrightarrow$ $n^3-1\equiv8-1=7\equiv0\,[7]$ .

4. $2^6=64\equiv-1\,[13]$ donc $2^{12}\equiv1\,[13]$ ; $70=12\times5+10$ : $2^{70}\equiv2^{10}=2^6\times2^4\equiv-16\equiv10\,[13]$ . $3^3=27\equiv1\,[13]$ et $70=3\times23+1$ : $3^{70}\equiv3\,[13]$ . Donc $2^{70}+3^{70}\equiv13\equiv0\,[13]$ .

5. a. $n+5=(n-2)+7$ : $n-2$ divise $n+5$ $\iff$ $n-2$ divise $7$ $\iff$ $n-2\in\{-7;-1;1;7\}$ . Comme $n\in\N$ , $n-2\ge-2$ : $n\in\{1;3;9\}$ .

5. b. $n\equiv-1\,[n+1]$ donc $n^3+2\equiv-1+2=1\,[n+1]$ . Ainsi $n+1$ divise $n^3+2\iff n+1$ divise $1\iff n+1=1\iff n=0$ .

6. $xy-5x-3y+18=0\iff(x-3)(y-5)=15-18=-3$ . Donc $x-3\in\{-3;-1;1;3\}$ et $y-5=\frac{-3}{x-3}$ : $S=\{(0;6);(2;8);(4;2);(6;4)\}$ .

Exercice 3 — Congruences modulo 7 et 13 Moyen ★★★☆☆

Soit $n\in\Z$ . Montrer que si $7$ ne divise pas $n$ , alors $7$ divise $n^6-1$ .
a. Montrer que pour tout $n\in\N$ , $3^{3n}\equiv1\,[13]$ . b. En déduire que pour tout $n\in\N$ , $3^{3n+2}+3^{3n+1}+1$ est divisible par $13$ .
Déterminer le reste de la division euclidienne de $32^{45}$ par $7$ .

Voir la correction

1. Raisonnement par disjonction de cas. Si $7$ ne divise pas $n$ , alors $n\equiv\pm1$ , $\pm2$ ou $\pm3\,[7]$ . Cas 1 : $n\equiv\pm1$ : $n^2\equiv1$ , $n^6\equiv1\,[7]$ . Cas 2 : $n\equiv\pm2$ : $n^2\equiv4$ , $n^6\equiv64\equiv1\,[7]$ . Cas 3 : $n\equiv\pm3$ : $n^2\equiv2$ , $n^6\equiv8\equiv1\,[7]$ . Dans tous les cas $7$ divise $n^6-1$ .

2. a. $3^3=27=2\times13+1\equiv1\,[13]$ , donc $3^{3n}=(3^3)^n\equiv1\,[13]$ .

2. b. $3^{3n+2}+3^{3n+1}+1=3^{3n}\times9+3^{3n}\times3+1\equiv9+3+1=13\equiv0\,[13]$ .

3. $32\equiv4\,[7]$ et $4^3=64\equiv1\,[7]$ ; $45=3\times15$ , donc $32^{45}\equiv(4^3)^{15}\equiv1\,[7]$ : reste $1$ .

Exercice 4 — Carrés modulo 8 ; équations Difficile ★★★★☆

a. Montrer que pour tout $n\in\Z$ : $n^2\equiv0\,[8]$ ou $n^2\equiv1\,[8]$ ou $n^2\equiv4\,[8]$ . b. En déduire que si $a\in\Z$ vérifie $a\equiv7\,[8]$ , alors $a$ n’est pas la somme de trois carrés d’entiers, c’est-à-dire : pour tout $(x;y;z)\in\Z^3$ , $a\neq x^2+y^2+z^2$ .
Résoudre dans $\Z$ les équations : a. $x^2+x+7\equiv0\,[13]$ ; b. $2x+11\equiv0\,[8]$ ; c. $5x\equiv1\,[8]$ .
Montrer que le système $\begin{cases}x\equiv3\,[12]\\x\equiv5\,[9]\end{cases}$ n’admet pas de solution dans $\Z$ .
Résoudre dans $\Z/5\Z$ l’équation $x^2-\overline2x-\overline7=\overline0$ .

Voir la correction

1. a. Disjonction de cas suivant le reste $r\in\{0;\dots;7\}$ de $n$ modulo $8$ : $r^2$ vaut $0,1,4,9,16,25,36,49$ , c’est-à-dire $0,1,4,1,0,1,4,1$ modulo $8$ .

1. b. Raisonnement par l’absurde. Supposons $a=x^2+y^2+z^2$ avec $x,y,z\in\Z$ . D’après a., chaque carré est congru à $0$ , $1$ ou $4$ modulo $8$ ; les sommes possibles de trois de ces valeurs sont $0,1,2,3,4,5,6$ (et $8\equiv0$ , $9\equiv1$ , $12\equiv4$ ) modulo $8$ , jamais $7$ . Cela contredit $a\equiv7\,[8]$ .

2. a. On teste les $13$ restes : seuls $x\equiv2$ ( $4+2+7=13$ ) et $x\equiv10$ ( $100+10+7=117=9\times13$ ) conviennent. $S=\{13k+2\ ;\ k\in\Z\}\cup\{13k+10\ ;\ k\in\Z\}$ .

2. b. $2x+11$ est impair, donc n’est pas divisible par $8$ : $S=\emptyset$ .

2. c. $5\times5=25\equiv1\,[8]$ : $5x\equiv1\,[8]\iff25x\equiv5\,[8]\iff x\equiv5\,[8]$ . $S=\{8k+5\ ;\ k\in\Z\}$ .

3. Raisonnement par l’absurde. Supposons qu’un entier $x$ vérifie le système. $x\equiv3\,[12]\Longrightarrow x\equiv0\,[3]$ (car $3$ divise $12$ et $3$ ) ; $x\equiv5\,[9]\Longrightarrow x\equiv2\,[3]$ . Donc $0\equiv2\,[3]$ : contradiction. Le système n’a pas de solution.

4. $x^2-\overline2x-\overline7=(x-\overline1)^2-\overline8=(x-\overline1)^2-\overline3$ . Les carrés de $\Z/5\Z$ sont $\overline0,\overline1,\overline4$ ; $\overline3$ n’est pas un carré. L’équation n’a pas de solution : $S=\emptyset$ .

Exercice 5 — Nombres premiers Moyen ★★★☆☆

Décomposer $624$ en produit de facteurs premiers et en déduire le nombre de ses diviseurs positifs.
Soit $p$ un nombre premier tel que $p\ge3$ . Montrer qu’il existe $k\in\N$ tel que $p=4k+1$ ou $p=4k+3$ .
Soit $n\in\N^*$ . Montrer que le nombre $x=\displaystyle\sum_{k=0}^{n}(2025+2k)$ n’est pas premier.
Soient $p$ un nombre premier et $n\in\Z^*$ . Montrer que si $p$ ne divise pas $n$ , alors $\pgcd(p;n)=1$ .
Vérifier que si $p_1$ et $p_2$ sont deux nombres premiers distincts, alors $\pgcd(p_1;p_2)=1$ .

Voir la correction

1. $624=2^4\times3\times13$ : $(4+1)(1+1)(1+1)=20$ diviseurs positifs.

2. Division euclidienne par $4$ : $p=4k+r$ , $r\in\{0;1;2;3\}$ . Cas $r=0$ ou $r=2$ : $p$ serait pair et $\ge3$ , donc divisible par $2$ et différent de $2$ : il ne serait pas premier, contradiction. Donc $r=1$ ou $r=3$ .

3. $x=2025(n+1)+2\sum_{k=0}^nk=2025(n+1)+n(n+1)=(n+1)(n+2025)$ . Comme $n\ge1$ , on a $n+1\ge2$ et $n+2025\ge2$ : $x$ admet le diviseur $n+1$ différent de $1$ et de $x$ , donc $x$ n’est pas premier.

4. $d=\pgcd(p;n)$ est un diviseur positif de $p$ , donc $d=1$ ou $d=p$ . Si $d=p$ , alors $p$ divise $n$ , ce qui est exclu. Donc $d=1$ .

5. $p_2$ est premier et distinct de $p_1$ , donc $p_1$ ne divise pas $p_2$ (sinon $p_1\in\{1;p_2\}$ ). D’après 4., $\pgcd(p_1;p_2)=1$ .

Exercice 6 — PGCD et PPCM Difficile ★★★★☆

On note $a\wedge b=\pgcd(a;b)$ et $a\vee b=\operatorname{PPCM}(a;b)$ .

À l’aide de l’algorithme d’Euclide, déterminer $604800\wedge476280$ .
Déterminer $50\wedge40$ et $50\vee40$ par quatre méthodes différentes.
a. Montrer que pour tout $n\in\N$ : $(3n^3-11n)\wedge(n+3)=(n+3)\wedge48$ . b. En déduire l’ensemble des entiers naturels $n$ tels que $\dfrac{3n^3-11n}{n+3}\in\N$ .
Soit $n\in\N$ . a. Montrer que $(n-1)\wedge(n-5)$ est un diviseur de $4$ . b. En déduire que si $n$ est pair, alors $(n-1)\wedge(n-5)=1$ .
Soit $n\in\N^*$ . On pose $a=5^{n+2}-5^n$ et $b=7^{n+2}-7^n$ . Déterminer $a\wedge b$ et $a\vee b$ .
Résoudre dans $(\N^*)^2$ : $(E_1)$ : $\begin{cases}x+y=100\\x\wedge y=10\end{cases}$ ; $(E_2)$ : $(x\wedge y)+(x\vee y)=x+y$ .

Voir la correction

1. $604800=476280\times1+128520$ ; $476280=128520\times3+90720$ ; $128520=90720\times1+37800$ ; $90720=37800\times2+15120$ ; $37800=15120\times2+7560$ ; $15120=7560\times2+0$ . Le dernier reste non nul est $7560$ : $604800\wedge476280=7560$ .

2. Méthode 1 (diviseurs) : diviseurs communs de $50$ et $40$ : $1,2,5,10$ ; donc $50\wedge40=10$ . Méthode 2 (Euclide) : $50=40\times1+10$ , $40=10\times4$ : $10$ . Méthode 3 (décomposition) : $50=2\times5^2$ , $40=2^3\times5$ : $50\wedge40=2\times5=10$ et $50\vee40=2^3\times5^2=200$ . Méthode 4 (relation) : $50\vee40=\frac{50\times40}{10}=200$ ; ou multiples de $50$ : $50,100,150,200$ , et $200$ est le premier multiple de $40$ .

3. a. $3n^3-11n=(n+3)(3n^2-9n+16)-48$ (vérification par développement). Donc $(3n^3-11n)\wedge(n+3)=(n+3)\wedge(-48)=(n+3)\wedge48$ .

3. b. $\frac{3n^3-11n}{n+3}\in\N$ $\iff$ $n+3$ divise $3n^3-11n$ et $3n^3-11n\ge0$ $\iff$ $n+3$ divise $48$ et $3n^3-11n\ge0$ . Avec $n+3\ge3$ : $n+3\in\{3;4;6;8;12;16;24;48\}$ , soit $n\in\{0;1;3;5;9;13;21;45\}$ . Pour $n=1$ : $3-11=-8<0$ , exclu. Les autres conviennent ( $3n^3-11n=n(3n^2-11)\ge0$ pour $n=0$ ou $n\ge2$ ). Ensemble : $\{0;3;5;9;13;21;45\}$ .

4. a. $\delta=(n-1)\wedge(n-5)$ divise $(n-1)-(n-5)=4$ .

4. b. Si $n$ est pair, $n-1$ est impair, donc $\delta$ est impair ; c’est un diviseur positif impair de $4$ : $\delta=1$ .

5. $a=5^n(25-1)=2^3\times3\times5^n$ et $b=7^n(49-1)=2^4\times3\times7^n$ . Donc $a\wedge b=2^3\times3=24$ et $a\vee b=2^4\times3\times5^n\times7^n=48\times35^n$ .

6. $(E_1)$ : $x=10x'$ , $y=10y'$ avec $x'\wedge y'=1$ et $x'+y'=10$ : $(x';y')\in\{(1;9);(3;7);(7;3);(9;1)\}$ ( $(5;5)$ , $(2;8)$ , $(4;6)$ … exclus car non premiers entre eux). $S_1=\{(10;90);(30;70);(70;30);(90;10)\}$ . $(E_2)$ : on pose $d=x\wedge y$ , $x=dx'$ , $y=dy'$ , $x'\wedge y'=1$ , d’où $x\vee y=dx'y'$ . L’équation devient $d+dx'y'=dx'+dy'\iff1+x'y'-x'-y'=0\iff(x'-1)(y'-1)=0\iff x'=1$ ou $y'=1\iff x$ divise $y$ ou $y$ divise $x$ . $S_2=\{(x;y)\in(\N^*)^2\ /\ x$ divise $y$ ou $y$ divise $x\}$ .

← Retour aux chapitres 1BAC SM