Ce contenu est en cours de préparation et sera ajouté par notre équipe pédagogique très prochainement.
$\forall (a,b) \in \mathbb{Z}^2$, on dit que $a$ divise $b$ (noté $a/b$) si et seulement si :
Exemples : $1/a \quad ; \quad a/0 \quad ; \quad 0/0 \text{ car } 0 = 0 \times k \ (k \in \mathbb{Z})$
Théorème :
Considérons $a$ et $b$ deux entiers relatifs tels que $b \neq 0$. Il existe un unique entier relatif $q$ et un unique entier naturel $r$ tels que :
Soit $(a,b) \in \mathbb{Z}^{*2}$ :
| PGCD ($a \wedge b$) | PPCM ($a \vee b$) |
|---|---|
| $a \wedge b = \max(\mathcal{D}_a^+ \cap \mathcal{D}_b^+)$ | $a \vee b = \min(\mathcal{M}_a^{+*} \cap \mathcal{M}_b^{+*})$ |
| $a \wedge b = b \wedge a$ | $a \vee b = b \vee a$ |
| $a \wedge (b \wedge c) = (a \wedge b) \wedge c$ | $a \vee (b \vee c) = (a \vee b) \vee c$ |
| $a \wedge a = |a|$ | $a \vee a = |a|$ |
| $a / b \iff a \wedge b = |a|$ | $a / b \iff a \vee b = |b|$ |
| $c(a \wedge b) = |c|(a \wedge b)$ | $c(a \vee b) = |c|(a \vee b)$ |
| $a \wedge 1 = 1$ | $a \vee 1 = |a|$ |
| Relation fondamentale : $(a \wedge b) \times (a \vee b) = |ab|$ | |
Théorème 1 : $d = a \wedge b \implies \exists (u,v) \in \mathbb{Z}^2 \ / \ d = au + bv$
(Attention : la réciproque est fausse)
Théorème 2 (Bézout) : $\forall (a,b) \in \mathbb{Z}^2$
$a \wedge b = 1 \iff \exists (u,v) \in \mathbb{Z}^2 \ / \ au + bv = 1$
Conséquences $\forall (a,b,c) \in \mathbb{Z}^3$ :
$\forall (a,b,c) \in \mathbb{Z}^3$, si $a / bc$ et $a \wedge b = 1$ alors $a / c$
Corollaire : Si $a/c$ et $b/c$ avec $a \wedge b = 1$, alors $ab / c$.
Soient $(a,b,c) \in \mathbb{Z}^3$ et $d = a \wedge b$.
Soit $n \in \mathbb{N}^* \setminus \{1\}$ et $\forall (a,b) \in \mathbb{Z}^2$.
On dit que $a$ est congru à $b$ modulo $n$ si et seulement si $n / (a-b)$. On écrit :
$\forall (a,b,c,d) \in \mathbb{Z}^4$ et $\forall m \in \mathbb{N}^* \setminus \{1\}$ :
Soit $p$ un nombre premier et $(a,b) \in \mathbb{Z}^2$.
Soit $p$ un nombre premier positif et $a \in \mathbb{Z}$.
Si de plus $p$ ne divise pas $a$ ($p \nmid a$ ou $a \wedge p = 1$), alors :
Théorème fondamental de l'arithmétique :
Tout entier $a \in \mathbb{Z}^* \setminus \{-1, 1\}$ s'écrit d'une façon unique sous la forme d'un produit de nombres premiers :
Avec $\alpha_i \in \mathbb{N}^*$ et $p_1, p_2 \dots p_n$ des nombres premiers positifs distincts.
Théorème :
Soit $b \in \mathbb{N}^*$ tel que $b \ge 2$ et soit $a \in \mathbb{N}^*$. $a$ s'écrit d'une façon unique de la forme :
Avec $0 \le a_i < b$ et $a_n \neq 0$.
On dit que $a$ est écrit dans le système de numération de base $b$. On le note :
Remarque (Comparaison) : Si l'on compare deux nombres dans une même base, celui qui a le plus de chiffres est le plus grand. S'ils ont le même nombre de chiffres, on compare de gauche à droite (comme pour l'ordre alphabétique).
Soit $n \in \mathbb{N}^*$ et $a \in \mathbb{Z}$. La classe d'équivalence de $a$ est l'ensemble des entiers $x \in \mathbb{Z}$ tels que $x \equiv a \ [n]$. On la note $\bar{a}$ (ou $\dot{a}$ ou $cl(a)$) :
L'ensemble des classes d'équivalence modulo $n$ est noté $\mathbb{Z}/n\mathbb{Z}$ :
On définit l'addition et la multiplication dans $\mathbb{Z}/n\mathbb{Z}$ par :
$\bar{x} + \bar{y} = \overline{x+y} \quad$ et $\quad \bar{x} \cdot \bar{y} = \overline{x \cdot y}$
Théorème d'inversibilité :
Soit $\bar{x} \in \mathbb{Z}/n\mathbb{Z}$.
Pour montrer que $a \wedge b = d$, il faut procéder en deux étapes :
Soit $b \in (\mathbb{N}^* \setminus \{1\})$.
Dans le système de numération de base $b$, on détermine les restes $a_k$ des divisions successives par $b$ (avec $0 \le a_k < b$) et on écrit : $N = \overline{a_k a_{k-1} \dots a_1 a_0}$.
Si $x = \overline{a_n a_{n-1} \dots a_1 a_0}^{(b)}$ et $y = \overline{c_m c_{m-1} \dots c_1 c_0}^{(b)}$, alors :
Déterminer le chiffre d'unité du nombre $N = 1987^{1991^{1983}}$
Montrer que le nombre $(9518)^{42} - 4$ est un multiple de 5
1) Déterminer les restes de la division euclidienne du nombre 7 par les nombres suivants : $5, 5^2, 5^3, 5^4, 5^5, 5^6$ et $5^7$
2) Déterminer suivant les valeurs de l'entier naturel $n$, le reste de la division euclidienne du nombre $5^n$ par $7$
Calculer $x$ dans chacun des cas :
1) $(2601)^{187} \equiv x [11]$ et $0 \le x < 11$
2) $(82324)^{625} \equiv x [7]$ et $0 \le x < 7$
1) Montrer que : $(\forall n \in \mathbb{N}) ; 10^{3n} \equiv 1 [27]$
2) On pose : $A = 10^{100} + 10^{20}$
Déterminer le reste de la division euclidienne du nombre $A$ par $27$
Montrer que pour tout entier naturel $n$ on a :
1) Le nombre $A = 3^{2n+1} + 2^{n+2}$ est divisible par 7
2) Le nombre $B = 3^{n+3} - 4^{4n+2}$ est divisible par 11
Soit $x$, $y$ et $z$ des éléments de $\mathbb{N}$ tels que $3x - 7y - 24z = 0$
Montrer que : $21|y(x - z)$
1) Soit $a$ et $b$ deux éléments de $\mathbb{Z}^*$ tels que : $a \wedge b = 1$
Déterminer en fonction de $a$ et $b$ l'élément $c$ de $\mathbb{Z}$ tel que :
$b|ac$ ; $c|ab$ et $a|bc$
2) Déterminer les entiers naturels $a, b$ et $c$ tels que :
$\begin{cases} a \wedge b = 12 \\ b \wedge c = 18 \\ a + b + c = 102 \end{cases}$
Soit $a$ et $b$ deux éléments de $\mathbb{N}$ tels que : $a \wedge b = 1$
Montrer que : $(a^2 - ab + b^2) \wedge (a + b) \le 3$
Soit $a$ et $b$ deux éléments de $\mathbb{Z}$
Montrer que : $(a^2 + b^2) \wedge ab = (a \wedge b)^2$
Soit $a$ et $b$ deux entiers naturels premiers entre eux.
1) Montrer que :
a) $(a + b) \wedge a = 1$ b) $(a + b) \wedge b = 1$ c) $(a + b) \wedge ab = 1$
2) On pose : $d = (a + b) \wedge (a^2 + b^2 - ab)$
Montrer que : $d = 1$ ou $d = 3$
3) Soit $n$ un entier naturel.
On pose : $\alpha = (a + b) \wedge (a^2 + b^2 - nab)$
a) Montrer que : $\alpha | (n + 2)ab$ b) En déduire que : $\alpha | n + 2$
Soit $p$ un nombre premier impair.
Résoudre dans $\mathbb{N}^2$, l'équation : $x^2 - y^2 = p$
Existe-t-il un nombre entier naturel $n$ non nul ; tel que : $2^{4n+2} + 1$ soit premier ?
Pour déterminer le chiffre d'unité du nombre $N$, il suffit de déterminer le reste de la division euclidienne du nombre $N$ par 10.
On a : $1987 \equiv 7 [10]$ et $1987^2 \equiv 9 [10]$
et $1987^3 \equiv 3 [10]$ et $1987^4 \equiv 1 [10]$
Donc : $1987^{4k} \equiv 1 [10]$, $1987^{4k+1} \equiv 7 [10]$
$1987^{4k+2} \equiv 9 [10]$ et $1987^{4k+3} \equiv 3 [10]$ pour tout $k$ de $\mathbb{N}$
Déterminons le reste de la division euclidienne du nombre $1991^{1983}$ par 4 :
On a : $1991 \equiv 3 [4]$ et $1991^2 \equiv 1 [4]$
et puisque $1983$ est un nombre impair alors : $1991^{1983} \equiv 3 [4]$
c'est-à-dire : $1991^{1983} = 3 + 4k$ où $k \in \mathbb{N}$
D'où : $1987^{1991^{1983}} \equiv 3 [10]$
Par conséquent : 3 est le chiffre d'unité du nombre $N$.
On a : $9518 \equiv 3 [5]$
Déterminons l'ensemble des entiers $n$ tels que $3^n \equiv 1 [5]$ :
On a :
$3^0 \equiv 1 [5]$
$3^1 \equiv 3 [5]$
$3^2 \equiv 4 [5]$
$3^3 \equiv 2 [5]$
$3^4 \equiv 1 [5]$
Donc le reste de la division euclidienne $3^n$ par $5$ dépend du reste de la division euclidienne de $n$ par 4.
On a : $42 = 4 \times 10 + 2$
Donc : $9518 \equiv 3 [5] \implies (9518)^{42} \equiv (3)^{42} [5]$
$\implies (9518)^{42} \equiv (3)^{4 \times 10 + 2} \equiv (3^4)^{10} \times 3^2 [5]$
Et puisque : $(3^4)^{10} \equiv 1 [5]$ et $3^2 \equiv 4 [5]$
Alors : $(3^4)^{10} \times 3^2 \equiv 4 [5]$
Donc : $(9518)^{42} \equiv 4 [5]$
C'est-à-dire : $(9518)^{42} - 4 \equiv 0 [5]$
Par conséquent : $(9518)^{42} - 4$ est un multiple de 5.
1) On a :
$5 \equiv 5 [7]$ donc 5 est le reste de la division euclidienne de $5$ par 7
$5^2 \equiv 4 [7]$ donc 4 est le reste de la division euclidienne de $5^2$ par 7
$5^3 \equiv 6 [7]$ donc 6 est le reste de la division euclidienne de $5^3$ par 7
$5^4 \equiv 2 [7]$ donc 2 est le reste de la division euclidienne de $5^4$ par 7
$5^5 \equiv 3 [7]$ donc 3 est le reste de la division euclidienne de $5^5$ par 7
$5^6 \equiv 1 [7]$ donc 1 est le reste de la division euclidienne de $5^6$ par 7
$5^7 \equiv 5 [7]$ donc 5 est le reste de la division euclidienne de $5^7$ par 7
2) On a : $5^6 \equiv 1 [7]$ donc le reste de la division euclidienne de $5^n$ dépend du reste de la division euclidienne du nombre $n$ par 6.
D'où les cas suivants :
1er cas : $n \equiv 0 [6]$ ($n = 6k$ où $k \in \mathbb{N}$)
On a : $5^n = 5^{6k} = (5^6)^k$
Donc : $5^6 \equiv 1 [7] \implies (5^6)^k \equiv 1^k [7] \implies 5^n \equiv 1 [7]$
Par conséquent 1 est le reste de la division de $5^n$ par 7 (où $n = 6k ; k \in \mathbb{N}$).
2ème cas : $n \equiv 1 [6]$ ($n = 6k+1$ où $k \in \mathbb{N}$)
On a : $5^n = 5^{6k+1} = (5^6)^k \times 5$
donc : $\begin{cases} (5^6)^k \equiv 1 [7] \\ 5 \equiv 5 [7] \end{cases} \implies 5^{6k+1} \equiv 5 [7] \implies 5^n \equiv 5 [7]$
d'où 5 est le reste de la division euclidienne de $5^n$ par 7 (où $n = 6k+1 ; k \in \mathbb{N}$).
3ème cas : $n \equiv 2 [6]$ ($n = 6k+2$ où $k \in \mathbb{N}$)
On a : $5^n = 5^{6k+2} = (5^6)^k \times 5^2$
Donc : $\begin{cases} (5^6)^k \equiv 1 [7] \\ 5^2 \equiv 4 [7] \end{cases} \implies 5^{6k+2} \equiv 4 [7] \implies 5^n \equiv 4 [7]$
d'où 4 est le reste de la division euclidienne de $5^n$ par 7 (où $n = 6k+2 ; k \in \mathbb{N}$).
4ème cas : $n \equiv 3 [6]$ ($n = 6k+3$ où $k \in \mathbb{N}$)
On a : $5^n = (5^6)^k \times 5^3$
Donc : $\begin{cases} (5^6)^k \equiv 1 [7] \\ 5^3 \equiv 6 [7] \end{cases} \implies 5^{6k+3} \equiv 6 [7] \implies 5^n \equiv 6 [7]$
d'où 6 est le reste de la division euclidienne de $5^n$ par 7 (où $n = 6k+3 ; k \in \mathbb{N}$).
5ème cas : $n \equiv 4 [6]$ ($n = 6k+4$ où $k \in \mathbb{N}$)
On a : $5^n = (5^6)^k \times 5^4$
Donc : $\begin{cases} (5^6)^k \equiv 1 [7] \\ 5^4 \equiv 2 [7] \end{cases} \implies 5^{6k+4} \equiv 2 [7] \implies 5^n \equiv 2 [7]$
d'où 2 est le reste de la division euclidienne de $5^n$ par 7 (où $n = 6k+4 ; k \in \mathbb{N}$).
6ème cas : $n \equiv 5 [6]$ ($n = 6k+5$ où $k \in \mathbb{N}$)
On a : $5^n = (5^6)^k \times 5^5$
Donc : $\begin{cases} (5^6)^k \equiv 1 [7] \\ 5^5 \equiv 3 [7] \end{cases} \implies 5^{6k+5} \equiv 3 [7] \implies 5^n \equiv 3 [7]$
d'où 3 est le reste de la division euclidienne de $5^n$ par 7 (où $n = 6k+5 ; k \in \mathbb{N}$).
1) On a : $2601 \equiv 5 [11]$
Déterminons les entiers naturels $n$ tels que : $5^n \equiv 1 [11]$
On a : $5^1 \equiv 5 [11]$
$5^2 \equiv 3 [11]$
$5^3 \equiv 4 [11]$
$5^4 \equiv 9 [11]$
$5^5 \equiv 1 [11]$
Donc le reste de la division euclidienne de $5^n$ par $11$ dépend du reste de la division euclidienne du nombre $n$ par 5.
On a : $187 = 5 \times 37 + 2$
Donc : $5^5 \equiv 1 [11] \implies (5^5)^{37} \equiv 1 [11] \implies (5^5)^{37} \times 5^2 \equiv 5^2 [11] \implies 5^{187} \equiv 3 [11]$
D'autre part : $2601 \equiv 5 [11] \implies (2601)^{187} \equiv (5)^{187} [11]$
D'où : $(2601)^{187} \equiv 3 [11]$
Par suite $x = 3$.
2) On a : $82324 \equiv 4 [7]$
Déterminons les entiers naturels $n$ tels que : $4^n \equiv 1 [7]$
On a : $4^1 \equiv 4 [7]$
$4^2 \equiv 2 [7]$
$4^3 \equiv 1 [7]$
Donc le reste de la division euclidienne de $4^n$ par $7$ dépend du reste de la division euclidienne du nombre $n$ par 3.
On a : $625 = 3 \times 208 + 1$
Donc : $4^3 \equiv 1 [7] \implies (4^3)^{208} \equiv 1 [7] \implies (4^3)^{208} \times 4^1 \equiv 4^1 [7] \implies (4)^{625} \equiv 4 [7]$
D'autre part : $82324 \equiv 4 [7] \implies (82324)^{625} \equiv (4)^{625} [7]$
Donc : $(82324)^{625} \equiv 4 [7]$
Par conséquent $x = 4$.
1) Montrons que : $(\forall n \in \mathbb{N}) ; 10^{3n} \equiv 1 [27]$
Soit $n$ un élément de $\mathbb{N}$
On a : $27 \times 37 = 999$ donc $999 \equiv 0 [27]$
D'où : $1000 \equiv 1 [27]$ c'est-à-dire : $10^3 \equiv 1 [27]$
D'où : $(10^3)^n \equiv 1^n [27] \implies 10^{3n} \equiv 1 [27]$
Par suite $(\forall n \in \mathbb{N}) ; 10^{3n} \equiv 1 [27]$
2) Déterminons le reste de la division du nombre $A$ par 27
On a : $A = 10^{100} + 10^{20} = 10^{3 \times 33 + 1} + 10^{3 \times 6 + 2} = 10^{3 \times 33} \times 10 + 10^{3 \times 6} \times 10^2$
D'après a) on en déduit que : $10^{3 \times 33} \equiv 1 [27]$ et $10^{3 \times 6} \equiv 1 [27]$
Donc : $A \equiv 10 + 10^2 [27]$ c'est-à-dire : $A \equiv 110 [27]$
Et puisque : $110 = 4 \times 27 + 2 \implies 110 \equiv 2 [27]$ alors : $A \equiv 2 [27]$
Soit $n$ un élément de $\mathbb{N}$
1) Montrons que le nombre $A = 3^{2n+1} + 2^{n+2}$ est un multiple de 7, c'est-à-dire $A \equiv 0 [7]$.
On a : $9 \equiv 2 [7]$ c'est-à-dire : $3^2 \equiv 2 [7]$ donc : $3^{2n} \equiv 2^n [7]$
D'où : $3^{2n+1} \equiv 3 \times 2^n [7]$ (1)
Et puisque : $3 \equiv -4 [7]$ alors : $3 \equiv -2^2 [7]$ donc : $3 \times 2^n \equiv -2^{n+2} [7]$ (2)
de (1) et (2) on en déduit que : $3^{2n+1} \equiv -2^{n+2} [7]$
c'est-à-dire : $3^{2n+1} + 2^{n+2} \equiv 0 [7]$
Par conséquent le nombre $A = 3^{2n+1} + 2^{n+2}$ est divisible par 7.
2) Montrons que le nombre $B = 3^{n+3} - 4^{4n+2}$ est divisible par 11 c'est-à-dire : $B \equiv 0 [11]$
On a : $4 \equiv 4 [11]$ et $4^2 \equiv 5 [11]$ et $4^3 \equiv 9 [11]$ et $4^4 \equiv 3 [11]$
Donc : $4^{4n} \equiv 3^n [11]$
Et puisque : $4^2 \equiv 5 [11]$ et $3^3 \equiv 5 [11]$ alors : $4^2 \equiv 3^3 [11]$
D'où : $\begin{cases} 4^{4n} \equiv 3^n [11] \\ 4^2 \equiv 3^3 [11] \end{cases} \implies 4^{4n} \times 4^2 \equiv 3^n \times 3^3 [11]$
c'est-à-dire : $4^{4n+2} \equiv 3^{n+3} [11]$ donc : $3^{n+3} - 4^{4n+2} \equiv 0 [11]$
Par conséquent : $B = 3^{n+3} - 4^{4n+2}$ est divisible par 11.
Montrons que $21 | y(x - z)$
On a : $3x - 7y - 24z = 0 \iff 3(x - 8z) = 7y$
Donc : $3 | 7y$
et puisque : $7 \wedge 3 = 1$ alors $3 | y$ (d'après le théorème de Gauss)
Donc : $(\exists p \in \mathbb{N}) : y = 3p$ (1)
D'où : $3x - 7y - 24z = 0 \iff 3x - 21p - 24z = 0 \iff x - 7p - 8z = 0 \iff x - z = 7(p + z)$
Par suite $7 | (x - z)$, ainsi : $(\exists q \in \mathbb{N}) ; x - z = 7q$ (2)
de (1) et (2) on en déduit que : $y(x - z) = 3p \times 7q = 21pq$
Par conséquent : $21 | y(x - z)$
1) Déterminons $c$ tel que : $a|bc$, $b|ac$ et $c|ab$
On a : $a|bc$ et $a \wedge b = 1$ donc $a|c$ (d'après le théorème de Gauss)
et on a : $b|ac$ et $b \wedge a = 1$ donc $b|c$ (d'après le théorème de Gauss)
et on a : $a|c$ et $b|c$ et $a \wedge b = 1$ donc $ab|c$, et par hypothèse on a : $c|ab$
Donc : $|c| = |ab|$ c'est-à-dire $c = ab$ ou $c = -ab$
2) On a : $a \wedge b \wedge c = (a \wedge b) \wedge (b \wedge c)$
et puisque : $a \wedge b = 12$ et $b \wedge c = 18$ alors $a \wedge b \wedge c = 12 \wedge 18 = 6(2 \wedge 3) = 6$
Donc : $(\exists (x,y,z) \in (\mathbb{N}^*)^3) ; (a = 6x \text{ et } b = 6y \text{ et } c = 6z)$ avec $x \wedge y \wedge z = 1$
et on a : $a + b + c = 102 \iff 6(x + y + z) = 102 \iff x + y + z = 17$
et puisque : $a \wedge b = 12 \implies 6(x \wedge y) = 12 \iff x \wedge y = 2$
alors $2|y$
et puisque : $b \wedge c = 18 \implies 6(y \wedge z) = 18 \iff y \wedge z = 3$
alors $3|y$
et comme $2 \wedge 3 = 1$ alors $6|y$
Donc : $y = 6$ ou $y = 12$ (car $y \in \mathbb{N}^*$ et $x+y+z=17$)
• Si : $y = 12$ alors $x + z = 5$
Donc : $z = 5 - x$ et $z \ge 1$ d'où $x \in \{1,2,3,4\}$
et puisque $x \wedge y = 2$ alors $x$ est pair
D'où : $x = 2$ ou $x = 4$
Si $x = 4$ alors $z = 1$ et $y = 12$ mais $y \wedge z \neq 3$
D'où : $x = 2$
et donc ce cas on a : $(x; y; z) = (2; 12; 3)$ et $(a; b; c) = (12; 72; 18)$
• Si $y = 6$ alors $x + z = 11$ donc $1 \le x \le 10$ et $x$ est pair et $z$ est un multiple de 3
On obtient : $(x, z) \in \{(2; 9), (8; 3)\}$
Donc : $(x, y, z) \in \{(2; 6; 9), (8; 6; 3)\}$, d'où $(a, b, c) \in \{(12; 36; 54), (48; 36; 18)\}$
Par conséquent : $(a, b, c) \in \{(12; 36; 54), (48; 36; 18), (12; 72; 18)\}$
Posons : $d = (a^2 - ab + b^2) \wedge (a + b)$
On a : $\begin{cases} d | a^2 - ab + b^2 \\ d | a + b \end{cases} \implies \begin{cases} d | a^2 - ab + b^2 \\ d | (a + b)^2 \end{cases} \implies \begin{cases} d | a^2 - ab + b^2 \quad (1) \\ d | a^2 + 2ab + b^2 \quad (2) \end{cases} \implies d | 3ab \quad ((2) - (1))$
D'autre part : $\begin{cases} d | 3ab \\ d | a + b \end{cases} \implies \begin{cases} d | 3ab \quad (3) \\ d | 3a^2 + 3ab \quad (4) \text{ (car } d|3a(a+b)) \\ d | 3ab + 3b^2 \quad (5) \text{ (car } d|3b(a+b)) \end{cases} \implies \begin{cases} d | 3a^2 \quad ((4) - (3)) \\ d | 3b^2 \quad ((5) - (3)) \end{cases} \implies d | 3a^2 \wedge 3b^2 \implies d | 3(a^2 \wedge b^2)$
car $(a \wedge b = 1 \implies a^2 \wedge b^2 = 1) \implies d | 3 \implies d \le 3$
On pose : $d = a \wedge b$
On a : $(\exists (\alpha, \beta) \in (\mathbb{Z}^*)^2) ; a = \alpha d \text{ et } b = \beta d \text{ et } \alpha \wedge \beta = 1$
Donc : $(a^2 + b^2) \wedge ab = (\alpha^2 d^2 + \beta^2 d^2) \wedge (\alpha \beta d^2) = d^2((\alpha^2 + \beta^2) \wedge (\alpha \beta))$
Il suffit de montrer que : $(\alpha^2 + \beta^2) \wedge (\alpha \beta) = 1$ Sachant que : $\alpha \wedge \beta = 1$
Soit $x$ un élément de $\mathbb{Z}^*$ tel que $x | \alpha^2 + \beta^2$ et $x | \alpha \beta$
On a : $\begin{cases} x | \alpha \beta \\ x | \alpha^2 + \beta^2 \end{cases} \implies \begin{cases} x | \alpha \beta \\ x | \alpha^3 + \beta^2 \alpha \end{cases} \implies x | \alpha^3$
On montre de la même façon que : $x | \beta^3$
Donc : $\begin{cases} x | \alpha^3 \\ x | \beta^3 \end{cases} \text{ d'où } x | \alpha^3 \wedge \beta^3$
Par conséquent $x | (\alpha \wedge \beta)^3 \quad (\alpha \wedge \beta = 1 \implies \alpha^n \wedge \beta^n = 1)$
c'est-à-dire $x | 1$, d'où : $x = 1 \text{ ou } x = -1$
Finalement : $(\alpha \beta) \wedge (\alpha^2 + \beta^2) = 1$
Ainsi : $(\forall (a, b) \in (\mathbb{Z}^*)^2) ; (a^2 + b^2) \wedge ab = (a \wedge b)^2$
Soit $a$ et $b$ deux éléments de $\mathbb{N}$ tels que : $a \wedge b = 1$
a) Montrons que : $(a + b) \wedge a = 1$
Posons : $d = (a + b) \wedge a$
On a : $\begin{cases} d | a + b \\ d | a \end{cases} \implies \begin{cases} d | (a + b) - a \\ d | a \end{cases} \implies \begin{cases} d | b \\ d | a \end{cases} \implies d | a \wedge b$
$\implies d | 1 \text{ car } (a \wedge b = 1)$
$\implies d = 1 \text{ donc } (a + b) \wedge a = 1$
b) Montrons que : $(a + b) \wedge b = 1$
En utilisant le même raisonnement que a), on montre que $(a + b) \wedge b = 1$
c) Montrons que : $(a + b) \wedge ab = 1$
Posons : $\delta = (a + b) \wedge ab$
On a : $\begin{cases} \delta | a + b \\ \delta | ab \end{cases} \implies \begin{cases} \delta | ab + b^2 \quad \text{(car } \delta | b(a + b)) \\ \delta | a^2 + ab \quad \text{(car } \delta | a(a + b)) \\ \delta | ab \end{cases} \implies \begin{cases} \delta | b^2 \\ \delta | a^2 \\ \delta | a^2 \wedge b^2 \\ \delta | 1 \quad \text{(car } a^2 \wedge b^2 = (a \wedge b)^2 = 1) \end{cases}$
$\implies \delta = 1 \text{ donc } : (a + b) \wedge ab = 1$
2) Montrons que : $d = 1 \text{ ou } d = 3$
On a : $\begin{cases} d | a^2 + b^2 - ab \\ d | a + b \end{cases} \implies \begin{cases} d | a^2 + b^2 - ab \quad (1) \\ d | a^2 + b^2 + 2ab \quad (2) \text{ (car } d | (a + b)^2) \\ d | a + b \end{cases} \implies \begin{cases} d | 3ab \quad ((2) - (1)) \\ d | 3(a + b) \\ d | 3(a + b) \wedge 3ab \\ d | 3((a + b) \wedge ab) \end{cases}$
$\implies d | 3 \text{ (car } (a + b) \wedge ab = 1)$
et on a : $d \in \mathbb{N}$, donc $d = 1 \text{ ou } d = 3$
3) a) Soit $n$ un entier naturel. Montrons que : $\alpha | (n + 2)ab$
On a : $\begin{cases} \alpha | a^2 + b^2 - nab \\ \alpha | a + b \end{cases} \implies \begin{cases} \alpha | a^2 + b^2 - nab \\ \alpha | a^2 + b^2 + 2ab \end{cases} \implies \alpha | 2ab + nab \implies \alpha | (n + 2)ab$
Par conséquent : $\alpha | (n + 2)ab$
b) Déduisons que : $\alpha | n + 2$
Montrons que : $\alpha \wedge ab = 1$. On pose : $\alpha \wedge ab = d$
On a : $\begin{cases} d | \alpha \\ d | ab \end{cases} \implies \begin{cases} d | a + b \quad \text{(car } \alpha = (a + b) \wedge (a^2 + b^2 - nab)) \\ d | ab \end{cases} \implies d | (a + b) \wedge ab$
$\implies d | 1 \quad \text{(car } (a + b) \wedge ab = 1) \implies d = 1$
Donc : $\alpha \wedge ab = 1$ et puisque $\alpha | (n + 2)ab$ alors $\alpha | n + 2$ (d'après le théorème de Gauss).
L'équation $x^2 - y^2 = p$ s'écrit : $(x - y)(x + y) = p$
Et puisque : $x - y < x + y$ et $p$ est premier ; alors : $x + y = p$ et $x - y = 1$
D'où : $x = \frac{p + 1}{2}$ et $y = \frac{p - 1}{2}$
Et puisque $p$ est impair ; alors : $(\exists k \in \mathbb{N}^*) ; p = 2k + 1$
Par conséquent : $x = k + 1$ et $y = k$
Donc : les solutions de l'équation : $x^2 - y^2 = p$ sont les couples $(k + 1 ; k)$
avec : $k = \frac{p - 1}{2}$
Soit $n$ de $\mathbb{N}^*$ ; on a :
$N = 2^{4n+2} + 1 = (2^{2n+1})^2 + 2 \cdot 2^{2n+1} + 1 - 2 \times 2^{2n+1}$
$= (2^{2n+1} + 1)^2 - 2 \times 2^{2n+1}$
$= (2^{2n+1} + 1)^2 - 2^{2n+2}$
$= (2^{2n+1} + 1)^2 - (2^{n+1})^2$
$= (2^{2n+1} + 2^{n+1} + 1)(2^{2n+1} + 1 - 2^{n+1})$
On a : $(\forall n \in \mathbb{N}^*) ; 2^{2n+1} + 2^{n+1} + 1 > 1$
Et on a : $2^{2n+1} - 2^{n+1} + 1 = 2^{n+1}(2^n - 1) + 1$
Et : $(\forall n \in \mathbb{N}^*) ; 2^{2n+1} - 2^{n+1} + 1 > 1$
Par conséquent : $2^{2n+1} - 2^{n+1} + 1$ et $2^{2n+1} + 2^{n+1} + 1$ sont deux diviseurs propres du nombre $N$.
Conclusion : $N$ n'est pas premier.
Soit \( n \in \mathbb{N} \). On pose \( a = 5n + 3 \) et \( b = 2n - 1 \).
Calculer \( a \lor b \) (c'est-à-dire \(\gcd(a,b)\)) en fonction de \( n \).
Suites \( (x_n) \) et \( (y_n) \) définies par \( x_0 = 3,\; y_0 = 1 \) et pour tout \( n \) :
\( x_{n+1} = 2x_n - 1 \), \( y_{n+1} = 2y_n + 3 \).
1) a) Montrer que \( x_n = 2^{n+1} + 1 \).
b) Montrer que \( x_{n+1} \land x_n = 1 \).
2) a) Montrer que \( 2x_n - y_n = 5 \) ; en déduire \( y_n \).
b) Déterminer, suivant \( p \in \mathbb{N} \), les restes de \( 2^p \) modulo 5.
3) \( d_n = x_n \land y_n \).
a) Montrer que \( d_n = 1 \) ou \( d_n = 5 \).
b) Déterminer \( S = \{ n \in \mathbb{N} \mid d_n = 5 \} \).
Soit \( a,b \in \mathbb{N} \) avec \( a < b \). Déterminer \( a \) et \( b \) dans chaque cas :
1) \( a \lor b = 60 \) et \( a \land b = 5 \)
2) \( a^2 + b^2 = 325 \) et \( a \lor b = 30 \)
3) \( ab = 1440 \) et \( a \lor b = 240 \)
4) \( (a \lor b) - 3(a \land b) = 21 \)
5) \( (a \lor b) - 9(a \land b) = 13 \)
1) Résoudre dans \( \mathbb{Z} \) :
a) \( 3x \equiv 4 \pmod{5} \) b) \( 2x \equiv 3 \pmod{5} \)
c) \( 2x \equiv 4 \pmod{6} \) d) \( 2x \equiv 3 \pmod{6} \)
2) Résoudre dans \( \mathbb{N} \) : \( 3^x + 4n + 1 \equiv 0 \pmod{8} \).
1) Résoudre dans \( \mathbb{Z}/5\mathbb{Z} \) :
a) \( 2x = 1 \) b) \( 2x = 3 \) c) \( x^5 = 1 \) d) \( x^{20} = 1 \)
2) Déterminer \( n \in \mathbb{N} \) tels que \( 7 \mid n^{20} - 1 \).
1) \( x,y \in \mathbb{Z}^* \), \( n \in \mathbb{N}^* \), \( n>1 \). Montrer que \( x^n \land y^n = (x \land y)^n \).
2) Si \( a \land b = 1 \) et \( a+b \) impair, montrer que \( (a^2+b^2) \land (a+b) = 1 \).
Résoudre les équations suivantes (modulo 5) :
1) \( x^2 - 2x - 2 \equiv 0 \pmod{5} \)
2) \( x^2 + 2x + 2 \equiv 0 \pmod{5} \)
3) \( x^2 - x - 1 \equiv 0 \pmod{5} \)
4) \( 2x^2 - 3x - 2 \equiv 7 \pmod{5} \)
Montrer pour tout \( n \in \mathbb{N} \) :
1) \( 4^n - 3n - 1 \equiv 0 \pmod{9} \)
2) \( 2^{2n+1} + 3^{2n+1} \equiv 0 \pmod{5} \)
3) \( 2^{4n+1} + 5 \equiv 0 \pmod{21} \)
Soient \( a,b,c \in \mathbb{Z} \) avec \( a \land b = 1 \). Montrer que \( a \land (bc) = a \land c \).
Pour \( x,y \in \mathbb{N} \), montrer que \( x \land y = (x+y) \land (x \lor y) \).
1) Déterminer les restes de \( 5^n \) modulo 13 selon \( n \).
2) En déduire que \( 2000^{2020} - 1 \) est divisible par 13.
3) Pour \( A_n = 1 + 5^n + 5^{2n} + 5^{3n} \), montrer que :
4) Montrer que pour tout \( n \in \mathbb{N}^* \) :
Soit \( n \in \mathbb{N} \).
1) Vérifier que :
2) Factoriser \( 6n^2 + 24n + 18 \).
3) a) Déterminer \( (6n^2 + 24n + 18) \land (4n^3 + 18n^2 + 20n + 6) \) en fonction de \( n \).
b) Déterminer \( (6n^2 + 24n + 18) \lor (4n^3 + 18n^2 + 20n + 6) \).
1) Calculer \( 168 \land 20 \).
2) Est-ce que les équations suivantes admettent des solutions dans \( \mathbb{Z} \times \mathbb{Z} \) ?
a) \( 168x + 20y = 6 \) b) \( 168x + 20y = 4 \) c) \( 42x + 5y = 2 \)
3) a) Déterminer les couples \( (m;p) \in \mathbb{Z}^2 \) tels que \( 42m + 5p = 1 \).
b) En déduire un couple \( (u_0;v_0) \) solution de \( 42x + 5y = 2 \).
c) Résoudre dans \( \mathbb{Z}^2 \) l'équation \( 42x + 5y = 2 \).
d) En déduire les solutions de \( (42x + 5y - 3)(42x + 5y + 3) = -5 \).
1) Résoudre dans \( \mathbb{Z}^2 \) : \( 5x - 2y = 1 \).
2) Résoudre dans \( \mathbb{Z} \) :
1) Résoudre \( 7u + 4v = 1 \) \((u,v \in \mathbb{Z}^2)\).
2) Soit \( (u_0,v_0) \) une solution de (1). On pose \( x_0 = 7u_0 + 20v_0 \).
3) Résoudre dans \( \mathbb{Z} \) : \( \begin{cases} x \equiv 0 \pmod{7} \\ x \equiv 0 \pmod{4} \end{cases} \).
4) Déduire les solutions du système \( (S) \).
On considère dans \( \mathbb{Z}^2 \) l'équation \( (E) : 324x - 245y = 7 \).
1) Montrer que si \( (x;y) \) est solution de \( (E) \), alors \( x \) est multiple de 7.
2) Résoudre dans \( \mathbb{Z}^2 \) l'équation \( (E) \).
3) Soit \( (x;y) \) une solution de \( (E) \), on pose \( d = x \land y \).
a) Déterminer les valeurs possibles de \( d \).
b) Déterminer les couples \( (x;y) \) solutions de \( (E) \) tels que \( x \land y = 1 \).
Montrer que la somme de trois nombres entiers naturels impairs et consécutifs est un nombre non premier.
Soit \( a,b \in \mathbb{N} \) avec \( a > 1 \) et \( b > 1 \). Montrer que \( N = a^4 + 4b^4 \) est un nombre non premier.
Résoudre dans \( \mathbb{Z} \) le système :
1) Soit \( n \in \mathbb{Z} \). Montrer que :
a) Si \( n \) est impair, \( n^2 \equiv 1 \pmod{8} \).
b) Si \( n \) est pair, \( n^2 \equiv 0 \pmod{8} \) ou \( n^2 \equiv 4 \pmod{8} \).
2) Résoudre dans \( \mathbb{N} \times \mathbb{N} \) l'équation \( 8x + 1 = y^2 \).
3) Montrer que pour tout \( n \in \mathbb{Z} \), si \( n \) est impair alors \( n^4 \equiv 1 \pmod{16} \).
Soit \( p \) un nombre premier et \( a \in \mathbb{N} \) tel que \( 2 \le a \le p-2 \).
Montrer que \( p \) est premier avec \( a^2 - 1 \).
1) Soit \( a,b \in \mathbb{N} \) tels que \( (a+b) \land ab = p^2 \), \( p \) premier.
a) Montrer que \( p^2 \mid a^2 \) et que \( p \mid a \).
b) Montrer que \( p \mid b \).
c) Montrer que \( a \land b = p \) ou \( a \land b = p^2 \).
2) On considère dans \( \mathbb{N}^2 \) le système :
a) Montrer que \( a \land b = 7 \).
b) Résoudre dans \( \mathbb{N}^2 \) le système \( (S) \).
1) Décomposer 469 en produit de nombres premiers.
2) Déterminer les couples \( (x;y) \in \mathbb{N}^2 \) tels que \( x^2 - y^3 = 469 \).
1) Soit \( p \) premier. Déterminer tous les \( \alpha \in \mathbb{Z} \) tels que \( \alpha^2 \equiv 0 \pmod{p^2} \).
2) En déduire tous les \( x \in \mathbb{Z} \) vérifiant :
Soit \( p \) un nombre premier et \( n \in \mathbb{Z} \) tels que \( n^3 \equiv 1 \pmod{p} \), \( n \not\equiv 1 \pmod{p} \) et \( p \ge 2 \).
Montrer que \( (n+1)^6 \equiv 1 \pmod{p} \).
1) Comment peut-on écrire les diviseurs positifs de 630 ?
2) Déterminer tous les \( x \in \mathbb{N} \) tels que \( x \lor 18 = 630 \).
Soit \( p \) un nombre premier, \( p \ge 5 \).
1) Montrer que \( (\exists k \in \mathbb{N}^*) : p = 6k - 1 \) ou \( p = 6k + 1 \).
2) En déduire que \( p^2 \equiv 1 \pmod{24} \).
1) Montrer que si \( p \) et \( 8p-1 \) sont premiers, alors \( 8p+1 \) n'est pas premier.
2) Montrer que si \( p \) est premier et \( p \neq 3 \), alors \( 8p^2 + 1 \) n'est pas premier.
Soit \( n \ge 2 \) tel que \( n \mid (n-1)! + 1 \). Montrer que \( n \) est premier.
Soit \( n \in \mathbb{N} \setminus \{0,1\} \). Montrer que \( 5^n - 3^n \) n'est pas premier.
1) Déterminer tous les \( x \in \mathbb{N} \) tels que \( x \lor 15 = 720 \).
2) Déterminer tous les \( x \in \mathbb{N} \) tels que \( x \land 5880 = 84 \).
Soit \( p \) premier, \( p \ge 5 \).
1) Montrer que \( p^2 \equiv 1 \pmod{3} \) et \( 2^p \equiv 2 \pmod{3} \).
2) En déduire que \( p^2 + 2^p \) n'est pas premier.
3) Montrer que si \( p^2 + 2^p \) est premier, alors \( p = 3 \).
Soit \( a,b \in \mathbb{N}^* \) avec \( a \land b = 1 \) et \( ab \) est un carré parfait.
Montrer que \( a \) et \( b \) sont des carrés parfaits.
Soit \( p \) un nombre premier.
1) Montrer que \( p \mid \binom{p}{k} \) pour tout \( k \in \{1,\dots,p-1\} \).
2) Montrer que pour tout \( n \in \mathbb{N} \), \( n^p \equiv n \pmod{p} \).
3) Applications :
a) Montrer que \( 546 \mid n^{13} - n \) pour tout \( n \in \mathbb{N} \).
b) Montrer que \( 3x^3 + 3x + 7 = y^3 \) n'a pas de solution dans \( \mathbb{Z}^3 \).
Déterminer les nombres premiers \( p \) tels que \( p \mid 2^p + 1 \).
Soit \( p \) premier, \( p \equiv 3 \pmod{4} \).
1) Montrer que \( x^2 + 1 \equiv 0 \pmod{p} \) n'a pas de solution dans \( \mathbb{Z} \).
2) Montrer que pour tout \( x,y \in \mathbb{Z} \) : \( p \mid x^2 + y^2 \iff p \mid x \) et \( p \mid y \).
3) Résoudre dans \( \mathbb{Z}^3 \) l'équation \( x^2 + y^2 = p z^2 \).
1) Montrer que \( n(n^2 - 1) \equiv 0 \pmod{7} \) pour tout \( n \in \mathbb{N} \).
2) Montrer que \( n(n^2 - 1) \equiv 0 \pmod{6} \) pour tout \( n \in \mathbb{N} \).
Montrer que \( 2222^{333} + 3333^{2222} \equiv 1 \pmod{5} \).
Pour \( n \in \mathbb{N} \), on pose \( A_n = n(n^2-1)(n^2-4) \) et \( B_n = n^5 - n \).
1) Montrer que \( A_n \equiv 0 \pmod{5} \) et \( B_n \equiv 0 \pmod{5} \).
2) Soient \( a,b \in \mathbb{Z} \).
a) Montrer que \( a^5 + b^5 \equiv 0 \pmod{5} \iff a+b \equiv 0 \pmod{5} \).
b) Déterminer \( p \in \mathbb{N} \), \( 0 \le p \le 20 \), tels que \( p^5 + 32 \equiv 0 \pmod{5} \).
Soit \( N = \overline{ababab} \) en base 10. Montrer que \( N \) est divisible par \( 10101 \).
1) Déterminer tous les \( a \in \mathbb{N} \) tels que \( a^3 \mid 18360 \).
2) En déduire les solutions de \( b \in \mathbb{N} \) : \( b^3 [ b^2 + (1+b)^2 ] = 18360 \).
3) Déterminer une base \( b \) telle que \( 36723_{10} = 442003_{(b)} \).
Existe-t-il \( (a,b) \in \mathbb{N}^2 \) tel que \( N = \overline{aabb} \) (en base 10) soit un carré parfait ?
Soit \( n = \overline{26x95y} \) en base 10. Déterminer \( (x,y) \in \mathbb{N}^2 \) tels que \( n \) soit divisible par 3 et par 11.
Soit \( N = \overline{xyz}_{(7)} = \overline{zyx}_{(9)} \).
1) Montrer que \( y = 25x - 40z \).
2) En déduire que \( y = 0 \).
3) Déterminer \( x \) et \( z \).
4) Écrire \( N \) en base 10.
Soit \( A_n = 3^n + 3^{2n} + 3^{3n} \).
1) Déterminer les restes de \( 3^n \) modulo 13 selon \( n \).
2) Déterminer \( S = \{ n \in \mathbb{N} \mid A_n \equiv 0 \pmod{13} \} \).
3) Les nombres \( \overline{1110}_{(3)} \), \( \overline{1010100}_{(3)} \), \( \overline{1001001000}_{(3)} \) sont-ils divisibles par 13 ?
1) Résoudre dans \( \mathbb{Z}^2 \) : \( 20x - 9y = 2 \).
2) Déterminer \( E = \{ (x,y) \in \mathbb{Z}^2 \mid 20x - 9y = 2,\; x \land y = 2 \} \).
3) Soit \( N = \overline{ca5}_{(6)} = \overline{bbaa}_{(4)} \).
1) Résoudre dans \( \mathbb{Z}^2 \) : \( 3x - 8y = 0 \).
2) En déduire l'ensemble des solutions de \( 3x - 8y = 1 \).
3) Soit \( A \in \mathbb{N}^* \) tel que \( A = \overline{b0a}_{(55)} = \overline{abc}_{(70)} \).
1) Soit \( a,b \in \mathbb{Z}^* \), \( A=2a+3b \), \( B=9a+5b \).
a) Montrer que \( 17 \mid A \iff 17 \mid B \).
b) Si \( a \land b = 1 \), montrer que \( A \land B = 1 \) ou \( 17 \).
2) Résoudre dans \( (\mathbb{Z}^*)^2 \) : \( (2x+3y)(9x+5y)=1156 \) et \( x \land y = 2 \).
Équation \( (E): x^3 + x^2 + 1 = 0 \).
1) Montrer que \( p \land q = 1 \iff p \land q^3 = 1 \).
2) Soit \( x = p/q \) une solution rationnelle, \( p \land q = 1 \).
a) Montrer que \( p \mid q^3 \).
b) En déduire que \( p = \pm 1 \) et que \( q, -q \) sont solutions de \( 1+x+x^3=0 \).
c) Montrer que \( n^3+n+1 \equiv 1 \pmod{2} \) pour tout \( n \). Conclure.
1) a) Restes de \( x^2 \) modulo 5.
b) Montrer que \( 2m^2+n^2 \equiv 0 \pmod{5} \implies m \equiv n \equiv 0 \pmod{5} \).
c) Si \( m \land n = 1 \), montrer que \( 5 \land (2m^2+n^2)=1 \).
2) Équation \( (E): 2x^3 + x - 5 = 0 \).
a) Montrer qu'elle admet une unique solution \( \alpha \in (1,2) \).
b) En supposant \( \alpha = m/n \) irréductible :
i) Vérifier \( (2m^2+n^2)m = 5n^3 \), puis montrer que \( m=5 \).
ii) En déduire que \( \alpha \) n'est pas rationnel.
1) Résoudre \( 11x - 24y = 1 \).
2) \( d = (10^{11}-1) \land (10^{24}-1) \).
a) Montrer que \( 9 \mid 10^{24}-1 \) et \( 9 \mid 10^{11}-1 \).
b) Avec \( (n,m) \) solution de \( 11x-24y=1 \), montrer que \( (10^{11}-1) - 10(10^{24}-1) = 9 \).
c) En déduire qu'il existe \( M,N \) tels que \( (10^{11}-1)N - (10^{24}-1)M = 9 \), puis la valeur de \( d \).
1) Montrer que si \( a \land b = 1 \), alors \( a \land (a+b)=1 \) et \( a \land b(a+b)=1 \).
2) Équation \( x(43-x)=y(x+y) \), \( x,y \in \mathbb{N}^* \).
Poser \( x=da, y=db \) avec \( d = x \land y \).
a) Montrer que \( a(43-da)=bd(a+b) \).
b) Montrer que \( a \mid d \), poser \( d=ac \).
c) Montrer que \( c(a^2+ab+b^2)=43 \), en déduire \( c=1 \).
d) Déterminer les solutions.
Suite \( u_0=0, u_1=1, u_{n+2}=3u_{n+1}-2u_n \).
1) Calculer \( u_2,\dots,u_6 \).
2) a) Montrer que \( u_{n+1}=2u_n+1 \).
b) PGCD de deux termes consécutifs.
3) a) Montrer que \( u_n = 2^n - 1 \).
b) PGCD \( (2^n-1; 2^{n+1}-1) \).
4) a) Vérifier \( u_{n+p} = u_n(1+u_p)+u_p \).
b) En déduire \( \operatorname{PGCD}(u_n,u_p) = \operatorname{PGCD}(u_n,u_{n+p}) \).
5) Avec la division euclidienne, montrer que \( \operatorname{PGCD}(u_n,u_p) = u_{\operatorname{PGCD}(n,p)} \).
6) Calculer \( \operatorname{PGCD}(u_{2004},u_{2005}) \).
1) \( x^4+4 = (x^2-2x+2)(x^2+2x+2) \).
Soit \( n\ge 2 \), \( A=n^2-2n+2 \), \( B=n^2+2n+2 \), \( d=A\land B \).
2) Montrer que \( n^4+4 \) n'est pas premier.
3) n impair :
a) \( d \mid 4n \).
b) \( d \) est impair et \( d \mid n \).
c) En déduire \( d=1 \).
4) n pair :
a) \( 4 \nmid A \).
b) \( d=2p \) avec \( p \) impair.
c) \( p \mid n \), puis \( d=2 \).
Soit \( p_n \) le \( n \)-ième nombre premier.
1) Pour \( n\ge 2 \), \( p_n \le p_1p_2\cdots p_{n-1}+1 \).
2) a) En déduire \( p_n \le p_{n-1}^{n-1}+1 \).
b) Montrer que \( p_n \le 2^{2^{n-1}} \).
I-1) a) Montrer que \( n!+2, n!+3,\dots,n!+n \) ne sont pas premiers.
b) Donner six entiers consécutifs non premiers.
2) Généralisation : \( p \) entiers consécutifs non premiers.
II- Avec \( M \) produit des premiers \( \le n \), montrer que \( M+2,\dots,M+n \) ne sont pas premiers.
Comparer avec I-2).
1) \( p\ge 5 \implies p = 6k+1 \) ou \( 6k+5 \).
2) Soit \( E \) l'ensemble des premiers de la forme \( 6k+5 \).
a) Produit de nombres \( 6k+1 \) est de la forme \( 6k+1 \).
b) Avec \( N = 2\cdot3\cdot5\cdots p - 1 \), montrer qu'il existe \( q \in E \) divisant \( N \).
c) En déduire que \( E \) est infini.
I- \( p\ge 3 \implies p \equiv 1 \) ou \( 3 \pmod{4} \).
II- \( E \) premiers de la forme \( 4k+3 \). Par l'absurde, \( E=\{p_1,\dots,p_r\} \).
1) r pair : \( a=p_1\cdots p_r+2 \). Montrer \( a\equiv 3\pmod{4} \), puis qu'aucun diviseur n'est dans \( E \), donc \( a\equiv 1\pmod{4} \). Contradiction.
2) r impair : \( b=p_1\cdots p_r+4 \). \( b\equiv 3\pmod{4} \) et \( b\equiv 1\pmod{4} \). Contradiction.
3) Conclusion : \( E \) est infini.
1) \( p\ge 5 \implies (p-1)(2p-1) \equiv 0 \pmod{6} \).
2) En déduire que \( \sum_{k=0}^{n-1} (n+k)^2 \equiv 0 \pmod{p} \) pour tout \( n \).
1) Nombre de diviseurs de \( n = \prod p_i^{\alpha_i} \) est \( \prod (1+\alpha_i) \).
2) Trouver \( x,y \) avec \( x \) a 21 diviseurs, \( y \) en a 10 et \( x\land y=18 \).
3) Si \( a \) a exactement 3 diviseurs, montrer que \( a \) est un carré parfait.
1) Nombre de diviseurs : \( \prod (1+\alpha_i) \).
2) Si \( n \) a 9 diviseurs, alors \( n = a^8 \) ou \( n=a^2b^2 \).
3) Déterminer \( n \) vérifiant : 9 diviseurs et \( 39p+1=n \), \( p \) premier.
a) \( n \ne a^8 \).
b) Montrer que \( p=5 \) ou \( p=37 \), puis donner \( n \).
Équation \( (D): 7x^3 - 13y = 5 \).
1) a) \( x \equiv 13 \pmod{3} \).
b) \( x^2 \equiv 1 \pmod{3} \).
c) \( x^3 \equiv 10 \pmod{3} \).
d) En déduire \( x^2 \equiv 3 \pmod{3} \), contradiction.
2) Pas de solution.
2969 premier, \( n^8+m^8 \equiv 0 \pmod{2969} \).
1) Si 2969 ne divise pas \( n \) :
a) Bézout : \( u n \equiv 1 \).
b) \( (u m)^8 \equiv -1 \) et \( (u m)^{2969} \equiv -1 \).
c) 2969 ne divise pas \( u m \).
d) Fermat : \( (u m)^{2969} \equiv u m \), contradiction.
2) a) Donc 2969 divise \( n \).
b) Équivalence : \( n \equiv m \equiv 0 \pmod{2969} \).
\( p = 3+4k \) premier.
1) \( x^2 \equiv 1 \pmod{p} \implies x^{p-5} \equiv 1 \pmod{p} \).
2) Réciproque :
a) \( x \) et \( p \) premiers entre eux.
b) \( x^{p-1} \equiv 1 \).
c) \( 2+(k-1)(p-1) = k(p-5) \).
d) En déduire \( x^2 \equiv 1 \).
3) Résoudre \( x^6 \equiv 1 \pmod{67} \).
2017 premier, \( 2016 = 2^5\cdot 3^2 \cdot 7 \).
Soit \( p\ge 5 \) premier, \( px + y^{p-1} = 2017 \).
1) a) \( p < 2017 \).
b) \( p \nmid y \).
c) Fermat : \( y^{p-1} \equiv 1 \pmod{p} \), donc \( p \mid 2016 \).
d) \( p=7 \).
2) Déterminer les solutions selon \( p \).
Première partie : 173 divise \( a^3+b^3 \).
1) \( a^{173} \equiv -b^{173} \).
2) 173 divise \( a \iff \) divise \( b \).
3) Si 173 divise \( a \), alors 173 divise \( a+b \).
4) Si 173 ne divise pas \( a \), Fermat donne \( a^{173} \equiv b^{173} \), puis \( a^{173} \equiv 0 \), donc \( a+b \equiv 0 \).
Deuxième partie : \( x^3+y^3 = 173(xy+1) \).
Poser \( x+y=173k \).
1) Vérifier \( k(x-y)^2 + (k-1)xy = 1 \).
2) Montrer que \( k=1 \), résoudre.
\( x^{139} \equiv 1436 \pmod{2015} \).
1) \( 1436 \land 2015 = 1 \).
2) a) Si \( d \mid x \) et \( d \mid 2015 \), alors \( d \mid 1436 \).
b) \( x \land 2015 = 1 \).
3) a) Fermat : \( x^{1440} \equiv 1 \pmod{5,13,31} \).
b) Donc \( x^{1440} \equiv 1 \pmod{2015} \).
4) En déduire \( x \equiv 1051 \pmod{2015} \).
I/ \( (E): x^{2015} \equiv 2 \pmod{13} \).
1) \( a^{2016} \equiv 1 \pmod{13} \) si \( a \land 13 = 1 \).
2) Pour \( x \) solution : \( x \land 13 = 1 \), puis \( x \equiv 7 \pmod{13} \).
3) \( S = \{ 7+13k \} \).
II/ Urne : 50 boules, probabilités.
1) Probabilité qu'une boule tirée soit solution de \( (E) \).
2) Avec remise, exactement deux fois une solution (loi binomiale).
\( a_n = \underbrace{333\dots 3}_{n \text{ fois}} \).
1) \( a_1, a_2 \) sont premiers.
2) \( 3a_n + 7 = 10^{n+1} \).
3) \( 10^{30k+2} \equiv 7 \pmod{31} \).
4) \( 3a_{30k+1} \equiv 0 \pmod{31} \), donc \( 31 \mid a_{30k+1} \).
5) Si \( n \equiv 1 \pmod{30} \), l'équation \( a_n x + 31y = 1 \) n'a pas de solution.
Propriété \( (R): 3^n-2^n \equiv 0 \pmod{n} \).
Soit \( p \) le plus petit diviseur premier de \( n \).
1) \( 3^n-2^n \equiv 0 \pmod{p} \), donc \( p \ge 5 \).
2) \( 2^{n-1} \equiv 1 \) et \( 3^{n-1} \equiv 1 \pmod{p} \).
3) Bézout : \( an - b(p-1) = 1 \).
4) Division de \( a \) par \( p-1 \) : \( nr = 1 + k(p-1) \).
5) Contradiction : il n'existe pas de \( n>1 \) vérifiant \( (R) \).
\( 143x - 195y = 52 \).
1) PGCD(195,143).
2) L'équation admet des solutions.
3) \( (-1,-1) \) solution particulière, trouver toutes les solutions.
4) \( n \) premier avec 5.
1) a) 503 est premier.
b) \( 7^{503} \equiv 7 \pmod{503} \).
2) \( 49x-6y=1 \), solution particulière \( (1,8) \), résoudre.
3) \( N = 1+7+\cdots+7^{2007} \).
a) \( (7^{2006}, N) \) est solution de \( 49x-6y=1 \).
b) \( N \equiv 0 \pmod{4} \) et \( N \equiv 0 \pmod{503} \).
c) Donc \( N \) divisible par 2012.
\( N = \underbrace{111\dots 1}_{2010 \text{ chiffres}} \).
1) \( N \) divisible par 11.
2) a) 2011 est premier, \( 10^{2010}-1 = 9N \).
b) 2011 divise \( 9N \).
c) 2011 divise \( N \).
3) \( N \) divisible par 22121.
Rappel : Critère de divisibilité par 11 : \( N \equiv a_0 - a_1 + a_2 - \cdots \pmod{11} \).
\( 10^x \equiv 2 \pmod{19} \).
1) a) \( 10^{x+1} \equiv 1 \pmod{19} \).
b) \( 10^{18} \equiv 1 \pmod{19} \).
2) \( d = 18 \land (x+1) \).
a) \( 10^d \equiv 1 \).
b) \( d=18 \).
c) \( x \equiv 17 \pmod{18} \).
1) \( m^2+1 \equiv 0 \pmod{5} \).
2) \( p=3+4k \) premier, \( n^2+1 \equiv 0 \pmod{p} \).
a) \( (n^2)^{2k} \equiv -1 \).
b) \( n \) et \( p \) premiers entre eux.
c) Par Fermat : \( (n^2)^{2k} \equiv 1 \).
d) Contradiction, donc pas de solution.
Aucun test interactif pour le moment.
