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\le x <7.
- a=36
- a=184
- a=-3
- a=7~006
- a=-4~901
- a=36
36=5\times 7+1 donc 36\equiv 1~[7] et x=1 - a=184
184=26\times 7+2 donc 184 \equiv 2~[7] et x=2 - a=-3
-3=-1\times 7+4 donc -3\equiv 4~[7] et x=4 - a=7~006
7~006=1~000\times 7+6 donc 7~006 \equiv 6~[7] et x=6 - a=-4~901
-4~901=-701\times 7+6 don c-4~901\equiv 6~[7] et x=6.
Exercice 2
Résoudre dans \Z les systèmes suivants :
- x\equiv -2~[5] et x>0
- x+2\equiv -1~[7] et 100 \le x<125
- 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 \{5k-2,~\forall k\in \N^*\}. - x+2\equiv -1~[7] et 100 \le x<125
Il existe k \in \Z tel que x+2=7k-1 soit x=7k-3.
\begin{align*} 100 \le x<125&\iff 100\le 7k-3<125 \\ &\iff 103 \le 7k \le 128 \\ &\iff \dfrac{103}{7} \le k < \dfrac{128}{7}\end{align*}
Or \dfrac{103}{7} \approx 14,7 et \dfrac{128}{7} \approx 18,3.
Ainsi k\in \{15;16;17;18\}
Réciproquement, pour tout k\in \{15;16;17;18\}, 7k-3\equiv -3~[7] et donc 7k-3+2\equiv -1~[7].
L’ensemble solution est donc k\in \{7k-3,~\forall k\in \{15;16;17;18\}\} = \{102;109;116;123\}.
Exercice 3
Déterminer les entiers naturels x et y tels que x\equiv y~[9]
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.
Exercice 4
Déterminer tous les couples d’entiers naturels (x, y) tels que : 3( x-2) = 5 ( y + 3)
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\ge 0 et donc que k\ge 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).
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 :
- 3x + 4 y
- x^2 + y^2
- 2x^2-5 y^2
- 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]. - 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]. - 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].
Exercice 6
Démontrer que pour tout n \in \N , n\left(n^2 + 5\right) est divisible par 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.
Exercice 7
Démontrer les congruences suivantes :
- 15^5-3^5\equiv 0~[12]
- 9^{10}-5^{10}\equiv 0~[7]
- On a 15\equiv 3~[12] donc 15^5 \equiv 3^5~[12]
Par conséquent 15^5-3^5 \equiv 0~[12] - 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].
Exercice 8
- Vérifier que 999 est divisible par 27.
- Soit n\in \N. Démontrer que 10^{3n}\equiv 1~[27].
- Quel est le reste dans la division de 10^{100} + 100^{10} par 27 ?
- 999=9\times 111 = 9\times 3\times 37.
Ainsi 999=27\times 37 et 999 est divisible par 27. - 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]. - 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].\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].Par conséquent 10^{100}+100^{10}\equiv 110~[27] soit 10^{100}+100^{10}\equiv 2~[27].
Exercice 9
On considère deux entiers naturels [/katex]a[/katex] et [/katex]b[/katex].
Calculer (a+b)^3. En déduire que (a+b)^3\equiv a^3+b^3~[3].
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].
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.
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.
Exercice 11
- Démontrer que, pour tout n\in \N, 2^{3n}-1\equiv 0~[7].
- En déduire que 2^{3n+1}-2\equiv 0~[7] et 2^{3n+2}-4\equiv 0~[7].
- Déterminer les restes de la division par 7 des puissances de 2.
- 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]. - 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].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]. - 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]
Exercice 12
- Résoudre dans \Z\times \Z l’équation 5p-3q=1.
- En déduire les solutions du système : \begin{cases} x\equiv 1~[5]\\x\equiv 2~[3]\end{cases}.
- 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.5p=1+3q\iff 5p=1+15k’+9 \iff 5p=10+15k’ \iff 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*}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.
- 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 \iff 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.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]L’ensemble des solutions du système \begin{cases} x\equiv 1~[5]\\x\equiv 2~[3]\end{cases} est donc \{11+15k,~\forall k\in \Z\}.