Exercices

Exercice 1   Soit $n$ un entier supérieur ou égal à $2$.

1. Démontrer que si $n$ n'est divisible par aucun entier inférieur ou égal à $\sqrt{n}$, alors $n$ est premier.
2. Démontrer que les nombres $n!+2$, $n!+3$,..., $n!+n$ ne sont pas premiers.
3. En déduire que pour tout $n$, il existe $n$ entiers consécutifs non premiers.

Exercice 2   On choisit un nombre entier, on le divise par $7$ et on trouve un reste égal à $5$. On divise à nouveau le quotient obtenu par $7$, on trouve un reste égal à $3$ et un quotient égal à $12$. Quel était le nombre de départ ?

Exercice 3   On donne l'égalité suivante.

$$96 842=256\times375+842$$

Déterminer, sans effectuer la division, le quotient et le reste de la division euclidienne de $96 842$ par $256$ et par $375$.

Exercice 4   On donne les deux égalités suivantes.

$$3379026=198765\times 17+21,\qquad 609806770=35870986\times 17+8.$$

On s'intéresse au nombre entier $N=3379026\times 609806770$. Quel est le reste de la division euclidienne de $N$ par $17$ ?

Exercice 5   Quel est le plus petit entier naturel, qui divisé par $8$, $15$, $18$ et $24$ donne pour restes respectifs $7$, $14$, $17$ et $23$ ?

Exercice 6   Dans une UE de maths à l'université Joseph Fourier, il y a entre $500$ et $1000$ inscrits. L'administration de l'université a remarqué qu'en les répartissant en groupes de $18$, ou bien en groupes de $20$, ou bien aussi en groupes de $24$, il restait toujours $9$ étudiants. Quel est le nombre d'inscrits ?

Exercice 7   Soient $a$ et $b$ deux entiers tels que $1\leqslant a<b$.

1. Soient $q_1$ et $r_1$ (respectivement : $q_2$ et $r_2$) le quotient et le reste de la division euclidienne de $a$ (respectivement : $b$) par $b-a$. Démontrer que
   $$r_1=r_2$$   et$$\quad q_2=q_1+1$$

2. On note $q$ le quotient de la division euclidienne de $b-1$ par $a$. Soit $n\geqslant 0$ un entier. Exprimer en fonction de $q$ et $n$ le quotient de la division euclidienne de $ba^n-1$ par $a^{n+1}$.
3. Soit $d$ le pgcd de $a$ et $b$. Déterminer le pgcd de $A$ et $B$, où :
   $$A=15a+4b$$   et$$\quad B=11a+3b$$

4. Montrer que $d=\mathrm{pgcd}(a+b,\mathrm{ppcm}(a,b))$.
5. Démontrer que si $d=1$, alors pour tout $m,n\in\mathbb{N}$, $a^m$ et $b^n$ sont premiers entre eux.
6. En déduire que pour tout $n\in\mathbb{N}$, le pgcd de $a^n$ et $b^n$ est $d^n$.

Exercice 8   Soient $a$, $b$ et $c$ trois entiers relatifs.

1. Montrer que $\mathrm{pgcd}(ca,cb)=\vert c\vert\times\mathrm{pgcd}(a,b)$.
2. Montrer que si $\mathrm{pgcd}(a,b)=1$ et si $c$ divise $a$, alors $\mathrm{pgcd}(c,b)=1$.
3. Montrer que $\mathrm{pgcd}(a,bc)=1$ si et seulement si $\mathrm{pgcd}(a,b)=\mathrm{pgcd}(a,c)=1$.
4. Montrer que si $\mathrm{pgcd}(b,c)=1$ alors $\mathrm{pgcd}(a,bc)=\mathrm{pgcd}(a,b)\mathrm{pgcd}(a,c)$.

Exercice 9   Soient $a,b\in\mathbb{N}$ deux entiers tels que $0<a<b$.

1. Démontrer que si $a$ divise $b$, alors pour tout $n\in\mathbb{N}^*$, $n^a-1$ divise $n^b-1$.
2. Démontrer que le reste de la division euclidienne de $n^b-1$ par $n^a-1$ est $n^r-1$, où $r$ est le reste de la division euclidienne de $b$ par $a$.
3. Démontrer que le pgcd de $n^b-1$ et $n^a-1$ est $n^d-1$, où $d$ est le pgcd de $a$ et $b$.

Exercice 10   Soit $p$ un nombre premier.

1. On rappelle que pour tout $k=1,\ldots,p-1$,
   $$k\binom{p}{k}=p\binom{p-1}{k-1}$$
   En déduire que pour tout $k=1,\ldots,p-1$, $$\binom{p}{k}$$ est divisible par $p$.
2. Grâce à la formule du binôme, en déduire que pour tous entiers relatifs $a$ et $b$ dans $\mathbb{Z}$, $(a+b)^p-a^p-b^p$ est divisible par $p$.
3. Démontrer par récurrence que pour tout $a\in\mathbb{N}$, $a^p-a$ est divisible par $p$. (Bravo ! Vous venez de démontrer le Petit Théorème de Fermat.)

Exercice 11   Soit $n$ un entier relatif. On pose $a=2n+3$ et $b=5n-2$.

1. Calculer $5a-2b$. En déduire le pgcd de $a$ et $b$ en fonction de $n$.
2. Procéder de même pour exprimer en fonction de $n$ le pgcd de $2n-1$ et $9n+4$.

Exercice 12   Donner la décomposition en facteurs premiers des entiers suivants.

$$60\quad;\quad 360\quad;\quad 2400\quad;\quad 4675\quad;\quad 9828 \quad;\quad 15200\quad;\quad 45864\quad;\quad 792792.$$

Exercice 13   On considère les couples d'entiers $(a,b)$ suivants.

$\bullet$

$a=60$, $b=84$

$\bullet$

$a=360$, $b=240$

$\bullet$

$a=160$, $b=171$

$\bullet$

$a=360$, $b=345$

$\bullet$

$a=325$, $b=520$

$\bullet$

$a=720$, $b=252$

$\bullet$

$a=955$, $b=183$

$\bullet$

$a=1665$, $b=1035$

$\bullet$

$a=18480$, $b=9828$

Pour chacun de ces couples :

1. Calculer $\mathrm{pgcd}(a,b)$ par l'algorithme d'Euclide.
2. En déduire une identité de Bézout.
3. Calculer $\mathrm{ppcm}(a,b)$.
4. Déterminer l'ensemble des couples $(u,v)$ d'entiers relatifs tels que :
   $$au+bv=\mathrm{pgcd}(a,b)\;.$$

5. Donner la décomposition en facteurs premiers de $a$ et $b$.
6. En déduire la décomposition en facteurs premiers de $\mathrm{pgcd}(a,b)$ et $\mathrm{ppcm}(a,b)$, et retrouver les résultats des questions 1 et 3.

Exercice 14   Soit $n$ un entier naturel.

1. Démontrer qu'il existe deux entiers $a_n$ et $b_n$ tels que :
   $$(1+\sqrt{2})^n = a_n+b_n\sqrt{2}$$

2. Soient $u$ et $v$ deux entiers. Vérifier que
   $$(v-u)a_{n+1}+(2u-v)b_{n+1} = ua_n+vb_n$$

3. Démontrer par récurrence que pour tout $n$, $a_n$ et $b_n$ sont premiers entre eux.
4. Démontrer que $a_n$ est premier avec $b_{n+1}$, pour tout $n$.
5. Démontrer que $b_n$ est premier avec $a_{n+1}$ et avec $b_{n+1}$, pour tout $n$.

Exercice 15   Soit $a$ un entier naturel impair.

1. Démontrer que $a^2\equiv 1 [8]$.
2. Démontrer que $a^4\equiv 1 [16]$.
3. Démontrer que si $a\equiv 1 [2^n]$, alors $a^2\equiv 1 [2^{n+1}]$.
4. Démontrer par récurrence que pour tout $n\geqslant 3$,
   $$a^{2^{n-2}}\equiv 1 [2^n]$$

Exercice 16   Soient $a$ et $b$ deux entiers naturels premiers entre eux.

1. Démontrer que pour tout entier relatif $n$, il existe un couple d'entiers relatifs $(s,t)$ tels que $n=sa+tb$.
2. Soit $q$ un entier strictement plus grand que $a$, et $r$ un entier tel que $0\leqslant r\leqslant a$. Vérifier que $qa+r = (q-r)a+r(a+1)$. En déduire que pour tout entier $n\geqslant a(a+1)$, il existe un couple d'entiers naturels $(s,t)$ tels que $n=sa+t(a+1)$.
3. En utilisant une identité de Bézout, montrer qu'il existe deux entiers naturels consécutifs, l'un multiple de $a$, l'autre multiple de $b$.
4. Déduire des questions précédentes qu'il existe un entier $n_0$ tel que pour tout $n\geqslant n_0$, il existe un couple d'entiers naturels $(s,t)$ tels que $n=sa+tb$.
5. Au rugby, on peut marquer un essai ($5$ points), une transformation suivant un essai ($2$ points), un drop ($3$ points) ou une pénalité ($3$ points). Montrer que le nombre de points qu'une équipe de rugby ne peut pas atteindre à la fin d'un match est fini. Quel est le plus grand score non réalisable ?

Exercice 17   Soient $k$ un entier supérieur ou égal à $2$ et $m_1,\ldots,m_k$ des entiers, premiers entre eux deux à deux. Pour tout $i=1,\ldots,k$, soit $a_i\in\mathbb{Z}/m_i\mathbb{Z}$. On note $E$ l'ensemble des entiers $n$ tels que :

$$\forall i=1,\ldots,k\;,\quad n\equiv a_i\;[m_i]\;.$$

1. On note $M$ le produit $m_1\cdots m_k$ et pour tout $i=1,\ldots,k$, $\widehat{m}_i=M/m_i$. Montrer que $m_i$ et $\widehat{m}_i$ sont premiers entre eux.
2. Pour tout $i=1,\ldots,k$, soient $u_i$ et $v_i$ deux entiers tels que $u_im_i+v_i\widehat{m}_i=1$. On pose $e_i=v_i\widehat{m}_i$. Montrer que $e_i\equiv 1\;[m_i]$ et $e_i\equiv 0\;[m_j]$, $\forall j\neq i$.
3. On pose $n_0=a_1e_1+\cdots+a_ke_k$. Montrer que $n_0\in E$.
4. Soit $n$ un élément quelconque de $E$. Montrer que $n-n_0$ est un multiple de $M$.
5. Démontrer que $E=n_0+M\mathbb{Z}=\{n=n_0+h M ,\;h\in\mathbb{Z}\}$. (Bravo ! Vous venez de démontrer le Théorème des Restes Chinois.)

Exercice 18   Calculer le reste de la division par $3$, par $4$, par $5$, par $6$, par $7$, des nombres suivants.

$$314^{314}\quad;\quad 999^{999}\quad;\quad 2007^{2007}\quad;\quad 31416^{31416}$$

Exercice 19    

1. Montrer que $7$ divise $2222^{5555}+5555^{2222}$
2. Montrer que $11$ divise
   $$5^{10^{5^{10^{5^{10}}}}}+10^{5^{10^{5^{10^{5}}}}}$$

Exercice 20   Soient $a,b,c$ trois entiers relatifs quelconques.

1. Démontrer que $a+b+c$ divise $a^3+b^3+c^3-3abc$.
2. Démontrer que si $7$ divise $a^3+b^3+c^3$, alors $7$ divise $abc$.

Exercice 21   Démontrer que chacune des relations suivantes est vraie pour tout $n\in\mathbb{N}$.

1. $5$ divise $2^{2n+1}+3^{2n+1}$
2. $6$ divise $n^3-n$
3. $6$ divise $5n^3+n$
4. $6$ divise $4(4^{2n}-1)$
5. $7$ divise $3^{2n+1}+2^{n+2}$
6. $8$ divise $5^n+2\times 3^{n-1}+1$
7. $9$ divise $4^n-1-3n$
8. $11$ divise $3^{n+3}-4^{4n+2}$
9. $11$ divise $2^{6n+3}+3^{2n+1}$
10. $16$ divise $5^{n}-1-4n$
11. $17$ divise $2^{6n+3}+3^{4n+2}$
12. $17$ divise $2^{7n+1}+3^{2n+1}+5^{10n+1}+7^{6n+1}$
13. $18$ divise $2^{2n+2}+24n+14$
14. $19$ divise $2^{3n+4}+3^{3n+1}$
15. $19$ divise $2^{2^{6n+2}}+3$
16. $21$ divise $2^{4^{n+1}}+5$

Exercice 22   Déterminer l'ensemble des entiers relatifs $x$, solutions des équations suivantes.

1. $35x-7\equiv 0 [4]$
2. $22x-33\equiv 0 [5]$
3. $2x+3\equiv 0 [7]$
4. $9x+5\equiv 0 [8]$
5. $x^2+x+7\equiv 0 [13]$
6. $x^2\equiv 1 [16]$
7. $x^4\equiv 7 [11]$
8. $x^2+x+7\equiv 0 [13]$
9. $x^2-4x+3\equiv 0 [12]$
10. $x^2+(x+1)^2+(x+3)^2\equiv 0 [10]$

Exercice 23   Déterminer l'ensemble des entiers naturels $x$, solutions des équations suivantes.

1. $2^{2x}+2^x+1\equiv 0 [21]$
2. $2^{2x}+2^x+1\equiv 0 [7]$
3. $3^{x}+4x+1\equiv 0 [8]$
4. $1^x+2^x+3^x+4^x \equiv 0 [5]$

Exercice 24   Dans tout l'exercice, $a$ et $b$ sont deux entiers naturels.

1. Démontrer que
   $$a\mathbb{Z}\cap b\mathbb{Z}= \mathrm{ppcm}(a,b)\mathbb{Z}\;.$$

2. Démontrer que $a$ divise $b$ si et seulement si $b\mathbb{Z}\subset a\mathbb{Z}$.
3. Démontrer que $2\mathbb{Z}\cup 3\mathbb{Z}$ n'est pas un sous groupe de $\mathbb{Z}$.
4. Démontrer que $a\mathbb{Z}\cup b\mathbb{Z}$ est un sous-groupe de $\mathbb{Z}$ si et seulement si $a$ divise $b$ ou $b$ divise $a$.

Exercice 25    

1. Écrire l'ensemble des multiples de $\mathfrak{cl}(x)$ dans $\mathbb{Z}/5\mathbb{Z}$, pour $x=0,\ldots,4$.
2. Écrire l'ensemble des multiples de $\mathfrak{cl}(x)$ dans $\mathbb{Z}/6\mathbb{Z}$, pour $x=0,\ldots,5$.
3. Écrire l'ensemble des multiples de $\mathfrak{cl}(x)$ dans $\mathbb{Z}/8\mathbb{Z}$, pour $x=0,\ldots,7$.
4. Soient $n$ et $x$ deux entiers naturels. Démontrer que les trois propositions suivantes sont équivalentes.
   1. $\mathfrak{cl}(x)$ admet un inverse pour la multiplication dans $\mathbb{Z}/n\mathbb{Z}$.
   2. $x$ et $n$ sont premiers entre eux.
   3. tout élément de $\mathbb{Z}/n\mathbb{Z}$ est multiple de $\mathfrak{cl}(x)$ dans $\mathbb{Z}/n\mathbb{Z}$.
5. Calculer l'inverse de $\mathfrak{cl}(4)$ dans $\mathbb{Z}/9\mathbb{Z}$.
6. Calculer l'inverse de $\mathfrak{cl}(8)$ dans $\mathbb{Z}/15\mathbb{Z}$.
7. Soit $n$ un entier non premier. Montrer qu'il existe deux éléments de $\mathbb{Z}/n\mathbb{Z}$ dont le produit est $\mathfrak{cl}(0)$. En déduire que $(n-1)!$ est divisible par $n$.
8. Soit $p$ un entier premier. Montrer que pour tout entier $x=2,\ldots,p-2$ il existe un entier $y=2,\ldots,p-2$, différent de $x$, tel que le produit $xy$ soit congru à $1$ modulo $p$. En déduire que $(p-1)!+1$ est divisible par $p$. (Bravo ! vous venez de démontrer le Théorème de Wilson.)