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.

$\displaystyle 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.

$\displaystyle 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

    $\displaystyle r_1=r_2$   et$\displaystyle \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ù :

    $\displaystyle A=15a+4b$   et$\displaystyle \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$,

    $\displaystyle k\binom{p}{k}=p\binom{p-1}{k-1}
$

    En déduire que pour tout $ k=1,\ldots,p-1$, $ \displaystyle\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.

$\displaystyle 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 :

    $\displaystyle 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 :

    $\displaystyle (1+\sqrt{2})^n = a_n+b_n\sqrt{2}
$

  2. Soient $ u$ et $ v$ deux entiers. Vérifier que

    $\displaystyle (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$,

    $\displaystyle 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 :

$\displaystyle \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.

$\displaystyle 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

    $\displaystyle 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

    $\displaystyle 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.)


         © UJF Grenoble, 2011                              Mentions légales