Terminale – Maths expertes – Arithmétique – Congruences

Arithmétique

Congruences

Exercice 1

Pour chacune des valeurs de $a$ données, trouver un entier $x$ tel que $a\equiv x ~[4]$ et $0\pp x <7$.

  1. $a=36$
    $\quad$
  2. $a=184$
    $\quad$
  3. $a=-3$
    $\quad$
  4. $a=7~006$
    $\quad$
  5. $a=-4~901$
    $\quad$
Correction Exercice 1

  1. $a=36$
    $36=5\times 7+1$ donc $36\equiv 1~[7]$ et $x=1$
    $\quad$
  2. $a=184$
    $184=26\times 7+2$ donc $184 \equiv 2~[7]$ et $x=2$
    $\quad$
  3. $a=-3$
    $-3=-1\times 7+4$ donc $-3\equiv 4~[7]$ et $x=4$
    $\quad$
  4. $a=7~006$
    $7~006=1~000\times 7+6$ donc $7~006 \equiv 6~[7]$ et $x=6$
    $\quad$
  5. $a=-4~901$
    $-4~901=-701\times 7+6$ don c$-4~901\equiv 6~[7]$ et $x=6$.
    $\quad$

 

[collapse]

$\quad$

Exercice 2

Résoudre dans $\Z$ les systèmes suivants :

  1. $x\equiv -2~[5]$ et $x>0$
    $\quad$
  2. $x+2\equiv -1~[7]$ et $100 \pp x<125$
    $\quad$
Correction Exercice 2

  1. $x\equiv -2~[5]$ et $x>0$
    Il existe $k\in \Z$ tel que $x=5k-2$.
    Or $x>0$ donc $k\in \N^*$.
    Réciproquement, pour tout $k\in \N^*$, $5k-2\equiv -2~[5]$.
    L’ensemble solution est donc $\acco{5k-2,~\forall k\in \N^*}$.
    $\quad$
  2. $x+2\equiv -1~[7]$ et $100 \pp x<125$
    Il existe $k \in \Z$ tel que $x+2=7k-1$ soit $x=7k-3$.
    $\begin{align*} 100 \pp x<125&\ssi 100\pp 7k-3<125 \\
    &\ssi 103 \pp 7k \pp 128 \\
    &\ssi \dfrac{103}{7} \pp k < \dfrac{128}{7}\end{align*}$
    Or $\dfrac{103}{7} \approx 14,7$ et $\dfrac{128}{7} \approx 18,3$.
    Ainsi $k\in \acco{15;16;17;18}$
    Réciproquement, pour tout $k\in \acco{15;16;17;18}$, $7k-3\equiv -3~[7]$ et donc $7k-3+2\equiv -1~[7]$.
    L’ensemble solution est donc $k\in \acco{7k-3,~\forall k\in \acco{15;16;17;18}} = \acco{102;109;116;123}$.
    $\quad$

[collapse]

$\quad$

Exercice 3

Déterminer les entiers naturels $x$ et $y$ tels que $x\equiv y~[9]$

$\quad$

Correction Exercice 3

$x$ et $y$ ont donc le même reste $r$ dans la division euclidienne par $9$.

Ainsi $x=9q+r$ et $y=9q’+r$ pour tout $(k,k’)\in \N^2$.
$\quad$

[collapse]

$\quad$

$\quad$

Exercice 4

Déterminer tous les couples d’entiers naturels $(x, y)$ tels que : $3( x-2) = 5 ( y + 3)$

$\quad$

Correction Exercice 4

$3$ et $5$ sont premiers entre eux. Par conséquent $3$ divise $y+3$.

Il existe donc $k\in \N$ tel que $y+3=3k$.
Par conséquent $3(x-2)=5\times 3k$ soit $x-2=5k$.
Ainsi $y=3k-3$ et $x=5k+2$.
$x$ et $y$ sont des entiers naturels. On en déduit donc que $y\pg 0$ et donc que $k\pg 1$.

Réciproquement, soit $k\in \N^*$ et considérons les entiers $x=5k+2$ et $y=3k-3$. On a bien $x\in \N$ et $y\in \N$.
$\begin{align*} 3(x-2)&=3\times 5k \\
&=5(3k-3+3) \\
&=5(y+3)\end{align*}$

Par conséquent, tous les couples $(5k+2,3k-3)$, pour tout $k\in \N^*$, sont solution de l’équation $3(x-2)=5(y+3)$.

$\quad$

[collapse]

$\quad$

Exercice 5

Soient $x$ et $y$ deux entiers naturels tels que $x \equiv 7~[9]$ et $y \equiv 4~ [9]$.
Déterminer les restes dans la division par $9$ de :

  1. $3x + 4 y$
    $\quad$
  2. $x^2 + y^2$
    $\quad$
  3. $2x^2-5 y^2$
    $\quad$
Correction Exercice 5

  1. $3x\equiv 21~[9]$ c’est-à-dire $3x\equiv 3~[9]$
    $4y\equiv 16~[9]$ c’est-à-dire $4y\equiv -2~[9]$
    Donc $3x+4y\equiv 1~[9]$.
    $\quad$
  2. $x^2\equiv 49~[9]$ ou encore $x^2\equiv 4~[9]$
    $y^2\equiv 16~[9]$ ou encore $y^2\equiv -2~[9]$
    Donc $x^2+y^2\equiv 2~[9]$.
    $\quad$
  3. D’après la question précédente $2x^2\equiv 8~[9]$ et $5y^2\equiv -10~[9]$
    Ainsi $2x^2-5y^2\equiv 18~[9]$ et donc $2x^2-5y^2\equiv 0~[9]$.
    $\quad$

[collapse]

$\quad$

Exercice 6

Démontrer que pour tout $n \in \N$ , $n\left(n^2 + 5\right)$ est divisible par $6$.

$\quad$

Correction Exercice 6

Raisonnons par disjonction de cas :

  • Si $n\equiv 0~[6]$ alors $n\left(n^2+5\right)\equiv 0~[6]$.
  • Si $n\equiv 1~[6]$ alors $n^2+5\equiv 6~[6]$ et $n\left(n^2+5\right)\equiv 0~[6]$.
  • Si $n\equiv 2~[6]$ alors $n^2+5\equiv 9~[6]$ et $n\left(n^2+5\right)\equiv 18~[6]$ soit $n\left(n^2+5\right)\equiv 0~[6]$.
  • Si $n\equiv 3~[6]$ alors $n^2+5\equiv 14~[6]$ et $n\left(n^2+5\right)\equiv 42~[6]$ soit $n\left(n^2+5\right)\equiv 0~[6]$.
  • Si $n\equiv 4~[6]$ alors $n^2+5\equiv 21~[6]$ et $n\left(n^2+5\right)\equiv 48~[6]$ soit $n\left(n^2+5\right)\equiv 0~[6]$.
  • Si $n\equiv 5~[6]$ alors $n^2+5\equiv 30~[6]$, c’est-à-dire $n^2+5\equiv 0~[6]$ et $n\left(n^2+5\right)\equiv 0~[6]$.

Ainsi, pour tout $n\in \N$, $n\left(n^2+5\right)$ est divisible par $6$.

$\quad$

[collapse]

$\quad$

Exercice 7

Démontrer les congruences suivantes :

  1. $15^5-3^5\equiv 0~[12]$
    $\quad$
  2. $9^{10}-5^{10}\equiv 0~[7]$
    $\quad$
Correction Exercice 7

  1. On a $15\equiv 3~[12]$ donc $15^5 \equiv 3^5~[12]$
    Par conséquent $15^5-3^5 \equiv 0~[12]$
    $\quad$
  2. D’une part $9\equiv 2~[7]$ donc $9^{10}\equiv 2^{10}~[7]$
    D’autre part $5\equiv -2~[7]$ donc $5^{10}\equiv (-2)^{10}~[7]$ soit $5^{10}\equiv 2^{10}~[7]$
    Par conséquent $9^{10}-5^{10}\equiv 0~[7]$.
    $\quad$

[collapse]

$\quad$

Exercice 8

  1. Vérifier que $999$ est divisible par $27$.
    $\quad$
  2. Soit $n\in \N$. Démontrer que $10^{3n}\equiv 1~[27]$.
    $\quad$
  3. Quel est le reste dans la division de $10^{100} + 100^{10}$ par $27$ ?
    $\quad$
Correction Exercice 8

  1. $999=9\times 111 = 9\times 3\times 37$.
    Ainsi $999=27\times 37$ et $999$ est divisible par $27$.
    $\quad$
  2. On a $10^{3n}=\left(10^3\right)^n$
    Or $1~000=999+1$ et $999\equiv 0~[27]$ donc $1~000\equiv 1~[27]$
    Ainsi, pour tout $n\in \N$ on a $1~000^n\equiv 1~[27]$ c’est-à-dire $10^{3n}\equiv 1~[27]$.
    $\quad$
  3. $10^{100}=10^{3\times 33+1}=10^{3\times 33}\times 10$
    D’après la question précédente $10^{3\times 33}\equiv 1~[27]$ donc $10^{100}\equiv 10~[27]$.
    $\quad$
    $\begin{align*} 100^{10}&=\left(10^2\right)^{10} \\
    &=10^{20} \\
    &=10^{3\times 6+2} \\
    &=10^{3\times 6}\times 100\end{align*}$
    Pour les mêmes raisons qu’au calcul précédent $100^{10}\equiv 100~[27]$.
    $\quad$
    Par conséquent $10^{100}+100^{10}\equiv 110~[27]$ soit $10^{100}+100^{10}\equiv 2~[27]$.
    $\quad$

[collapse]

$\quad$

Exercice 9

On considère deux entiers naturels $a$ et $b$.
Calculer $(a+b)^3$. En déduire que $(a+b)^3\equiv a^3+b^3~[3]$.

$\quad$

Correction Exercice 9

On a $(a+b)^3=a^3+3a^2b+3ab^2+b^3$.
Or $3a^2b\equiv 0~[3]$ et $3ab^2\equiv 0~[3]$.
Par conséquent $(a+b)^3\equiv a^3+b^3~[3]$.

$\quad$

[collapse]

$\quad$

Exercice 10

On considère un entier naturel $n$ et $a=5\left(n^2+n\right)^2$.
Prouver que $a$ est divisible par $20$.

$\quad$

Correction Exercice 10

Montrons que $a$ est divisible par $4$.

$\begin{array}{|l|c|c|c|c|}
\hline
n\equiv\ldots~[4]&0&1&2&3\\
\hline
n^2\equiv\ldots~[4]&0&1&0&1\\
\hline
\left(n^2+n\right)^2\equiv\ldots~[4]&0&0&0&0\\ \hline\end{array}$

Ainsi $a$ est divisible par $4$.

Par construction $a$ est divisible par $5$. Comme $4$ et $5$ sont premiers entre eux, $a$ est divisible par $4\times 5=20$.

$\quad$

[collapse]

$\quad$

Exercice 11

  1. Démontrer que, pour tout $n\in \N$, $2^{3n}-1\equiv 0~[7]$.
    $\quad$
  2. En déduire que $2^{3n+1}-2\equiv 0~[7]$ et $2^{3n+2}-4\equiv 0~[7]$.
    $\quad$
  3. Déterminer les restes de la division par $7$ des puissances de $2$.
    $\quad$
Correction Exercice 11

  1. Pour tout $n\in \N$ on a $2^{3n}=\left(2^3\right)^n=8^n$.
    Or $8\equiv 1~[7]$ donc $8^n\equiv 1~[7]$.
    Par conséquent $2^{3n}-1\equiv 0~[7]$.
    $\quad$
  2. Pour tout $n\in \N$, $2^{3n+1}-2=2\left(2^{3n}-1\right)$
    D’après la question précédente $2^{3n}-1\equiv 0~[7]$.
    Par conséquent $2^{3n+1}-2\equiv 0~[7]$.
    $\quad$
    On a de même $2^{3n+2}-4=4\left(2^{3n}-1\right)$
    Par conséquent $2^{3n+2}-4\equiv 0~[7]$.
    $\quad$
  3. D’après les questions précédentes, pour tout $n\in \N$ :
    $\bullet$ $2^{3n}\equiv 1~[7]$
    $\bullet$ $2^{3n+1}\equiv 2~[7]$
    $\bullet$ $2^{3n+2}\equiv 4~[7]$
    $\quad$

[collapse]

$\quad$

Exercice 12

  1. Résoudre dans $\Z\times \Z$ l’équation $5p-3q=1$.
    $\quad$
  2. En déduire les solutions du système : $\begin{cases} x\equiv 1~[5]\\x\equiv 2~[3]\end{cases}$.
    $\quad$
Correction Exercice 12

  1. On a donc $1+3q=5p$. Par conséquent $1+3q\equiv 0~[5]$
    Ainsi $3q\equiv 4~[5]$ ou encore $3q\equiv 9~[5]$.
    Il existe donc un entier $k$ tel que $3q=5k+9$.
    Donc $5k=3(q-3)$.
    $5$ et $3$ sont premiers entre eux. Ainsi $3$ divise $k$.
    Il existe donc $k’\in \Z$ tel que $k=3k’$. Par conséquent $3q=15k’+9$ et donc $q=5k’+3$.
    $\quad$
    $5p=1+3q\ssi 5p=1+15k’+9 \ssi 5p=10+15k’ \ssi p=2+3k’$.
    Réciproquement, soit $k\in \Z$ et considérons $p=2+3k$ et $q=3+5k$.
    $\begin{align*} 5p-3q&=5(2+3k)-3(3+5k) \\
    &=10+15k-9-15k\\
    &=1\end{align*}$
    $\quad$
    Les solutions de l’équation $5p-3q=1$ dans $\Z\times \Z$ sont donc les couples $(2+3k;3+5k)$ pour tout $k\in \Z$.
    $\quad$
  2. $x\equiv 1~[5]$. Il existe donc $p\in \Z$ tel que $x=5p+1$.
    $x\equiv 2~[3]$. Il existe donc $q\in \Z$ tel que $x=3q+2$
    Ainsi $5p+1=3q+2 \ssi 5p-3q=1$.
    D’après la question précédente, il existe $k\in \Z$ tel que $p=2+3k$ et $q=3+5k$.
    Par conséquent $x=11+15k$.
    $\quad$
    Réciproquement, soit $k\in \Z$. Posons $x=11+15k$.
    On a alors $x\equiv 11~[5]$ soit $x\equiv 1~[5]$ et $x\equiv 11~[3]$ soit $x\equiv 2~[3]$
    $\quad$
    L’ensemble des solutions du système $\begin{cases} x\equiv 1~[5]\\x\equiv 2~[3]\end{cases}$ est donc $\acco{11+15k,~\forall k\in \Z}$.
    $\quad$

[collapse]