Arithmétique/Exercices/Congruences

Exercice 9-1

Quel est le reste de la division par 7 du nombre 32⁴⁵ ?

Solution

Modulo 7, $32^{3}\equiv (-3)^{3}=-27\equiv 1$ donc $32^{3\times 15}\equiv 1^{15}=1$ : le reste est donc 1.

 

Exercice 9-2

Quel est le reste de la division par 19 du nombre 57383¹¹⁴ ?

Solution

$57383=3020\times 19+3$ et modulo 19, $3^{9}\equiv -1$ donc $57383^{114}\equiv 3^{9\times 12+6}\equiv 3^{6}\equiv 8^{2}\equiv 7$ : le reste est 7.

 

Exercice 9-3

Quel est le reste de la division par 7 du nombre 91234¹⁹⁹⁸ ?

Solution

$91234=13033\times 7+3$, $3^{3}\equiv -1{\pmod {7}}$ et $6\mid 1998$, donc le reste est 1.

 

Exercice 9-4

1. Démontrez que si l'on divise un entier n par 111, on trouve le même reste qu'en divisant 1000n par 111.
2. Déduisez-en que les deux nombres 10⁸ + 10⁴ + 1 et 10¹⁰ + 10⁵ + 1 sont divisibles par 111.

Solution

1. $1000=9\times 111+1$.
2. Modulo 111, $(10^{3})^{2}\times 10^{2}+10^{3}\times 10+1\equiv 10^{2}+10+1\equiv 0$ et $(10^{3})^{3}\times 10+10^{3}\times 10^{2}+1\equiv 10+10^{2}+1\equiv 0$.

 

Exercice 9-5

Quels sont les entiers n tels que n⁶ – 1 soit divisible par 9 ?

Solution

Modulo 9, n³ est congru à 0 si n est divisible par 3, et à ±1 sinon. Les solutions sont donc tous les entiers non divisibles par 3.

 

Exercice 9-6

Soient n₁, n₂, n₃, n₄ et n₅ cinq entiers relatifs vérifiant la relation :

$n_{1}^{3}+n_{2}^{3}+n_{3}^{3}+n_{4}^{3}+n_{5}^{3}=0$.

Montrez qu'alors, au moins un de ces cinq entiers est un multiple de 7.

Solution

Soit $n$ un entier relatif :

• si $n\equiv 0{\pmod {7}}$ alors $n^{3}\equiv 0{\pmod {7}}$ ;
• si $n\equiv 1$, $2$ ou $-3{\pmod {7}}$ alors $n^{3}\equiv 1{\pmod {7}}$ ;
• si $n\equiv -1$, $-2$ ou $3{\pmod {7}}$ alors $n^{3}\equiv -1{\pmod {7}}$.

Nous voyons que si aucun des cinq entiers n'est un multiple de 7, leur cube sera congru soit à 1, soit à –1 modulo 7 et par conséquent la somme de ces cinq cubes ne pourra pas être congrue à 0 modulo 7. Un des cinq entiers relatifs est donc un multiple de 7.

 

Exercice 9-7

1. Démontrer que si les entiers p et 8p – 1 sont premiers, alors 8p + 1 n'est pas premier. (Aide : On s'aidera des congruences modulo 3.)
2. Démontrer que si p est premier et différent de 3, alors 8p² + 1 est composé.

Solution

1. Si p = 3, 8p + 1 = 25. Si p est premier et différent de 3, alors, modulo 3, p ≡ ±1 donc (8p – 1)(8p + 1) ≡ (–p – 1)(–p + 1) = p² – 1 ≡ 0.
2. Si p est premier et différent de 3, alors, modulo 3, p ≡ ±1 donc 8p² + 1 ≡ 9 ≡ 0.

 

Exercice 9-8

Trouvez tous les entiers relatifs $x$ vérifiant simultanément les trois congruences :

${\begin{cases}x\equiv 1{\pmod {2}}\\x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {4}}.\end{cases}}$

Solution

Une autre façon d'écrire ces trois congruences est :

${\begin{cases}x\equiv -1{\pmod {2}}\\x\equiv -1{\pmod {3}}\\x\equiv -1{\pmod {4}}\end{cases}}$

Nous en déduisons que $x$ est solution si et seulement si x + 1 est un multiple de PPCM(2, 3, 4) = 12, c'est-à-dire s'il existe $k\in \mathbb {Z}$ tel que $x+1=12k$, soit :

$x=12k-1$.

 

Exercice 9-9

Déterminer le chiffre des unités de $7^{7^{7}}$.

Solution

Modulo 10, $7^{4}\equiv (-1)^{2}=1$ et modulo 4, $7^{7}\equiv (-1)^{7}\equiv -1\equiv 3$ donc modulo 10, $7^{7^{7}}\equiv 7^{3}\equiv -7\equiv 3$ : le chiffre est 3.

 

Exercice 9-10

1. Trouvez tous les entiers congrus à la fois à $1{\bmod {13}}$ et à $6{\bmod {7}}$.
2. Trouvez tous les entiers congrus à la fois à $5{\bmod {8}}$ et à $1{\bmod {27}}$.
3. Trouvez tous les entiers congrus à la fois à $1{\bmod {4}}$ et à $\pm 1{\bmod {5}}$.
4. Trouvez tous les entiers congrus à la fois à $3{\bmod {4}}$ et à $\pm 2{\bmod {5}}$.
5. Trouvez tous les entiers congrus à la fois à $1{\bmod {3}}$ et à $\pm 1{\bmod {8}}$.
6. Trouvez tous les entiers congrus à la fois à $-1{\bmod {3}}$ et à $\pm 3{\bmod {8}}$.
7. Trouvez tous les entiers congrus à la fois à $\pm 2{\bmod {5}}$ et à $\pm 5{\bmod {13}}$.
8. Trouvez tous les entiers congrus à la fois à $1$ ou $3{\bmod {8}}$ et à $\pm 1{\bmod {5}}$.
9. Trouvez tous les entiers congrus à la fois à $-1$ ou $-3{\bmod {8}}$ et à $\pm 2{\bmod {5}}$.

Solution

1. Soit $n=13k+1$. Puisque $13\equiv 6\equiv -1{\bmod {7}}$,

   $n\equiv 6{\bmod {7}}\Leftrightarrow -k+1\equiv -1{\bmod {7}}\Leftrightarrow k\equiv 2{\bmod {7}}$

   donc les solutions sont :

   $n=13\left(7l+2\right)+1=91l+27$, avec $l\in \mathbb {Z}$.

2. Soit $n=27k+1$. Alors, $n\equiv 5{\bmod {8}}\Leftrightarrow 3k+1\equiv -3{\bmod {8}}\Leftrightarrow 3k\equiv -12{\bmod {8}}\Leftrightarrow k\equiv -4{\bmod {8}}$

   donc les solutions sont : $n=27\left(8l-4\right)+1=216l-107$, avec $l\in \mathbb {Z}$.

3. Soit $n=4k+1$. Alors, $n\equiv \pm 1{\bmod {5}}\Leftrightarrow -k+1\equiv \pm 1{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {5}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=4\left(5l\right)+1=20l+1$ et ceux de la forme $n=4\left(5l+2\right)+1=20l+9$, c'est-à-dire les entiers congrus à $1{\text{ ou }}9{\bmod {20}}$.

4. Soit $n=4k-1$. Alors, $n\equiv \pm 2{\bmod {5}}\Leftrightarrow -k-1\equiv \pm 2{\bmod {5}}\Leftrightarrow k\equiv -3{\text{ ou }}1{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}2{\bmod {5}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=4\left(5l+1\right)-1=20l+3$ et ceux de la forme $n=4\left(5l+2\right)-1=20l+7$, c'est-à-dire les entiers congrus à $3{\text{ ou }}7{\bmod {20}}$.

5. Soit $n=3k+1$. Alors, $n\equiv \pm 1{\bmod {8}}\Leftrightarrow 3k\equiv 0{\text{ ou }}-2{\bmod {8}}\Leftrightarrow 3k\equiv 0{\text{ ou }}6{\bmod {8}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {8}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=3\left(8l\right)+1=24l+1$ et ceux de la forme $n=3\left(8l+2\right)+1=24l+7$, c'est-à-dire les entiers congrus à $1{\text{ ou }}7{\bmod {24}}$.

6. Soit $n=3k-1$. Alors, $n\equiv \pm 3{\bmod {8}}\Leftrightarrow 3k\equiv -2{\text{ ou }}4{\bmod {8}}\Leftrightarrow 3k\equiv 6{\text{ ou }}12{\bmod {8}}\Leftrightarrow k\equiv 2{\text{ ou }}4{\bmod {8}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=3\left(8l+2\right)-1=24l+5$ et ceux de la forme $n=3\left(8l+4\right)-1=24l+11$, c'est-à-dire les entiers congrus à $5{\text{ ou }}11{\bmod {24}}$.

7. Soit $n=13k+5\varepsilon$, avec $\varepsilon =\pm 1$. Alors, $n\equiv \pm 2{\bmod {5}}\Leftrightarrow -2k\equiv \pm 2{\bmod {5}}\Leftrightarrow k\equiv \pm 1{\bmod {5}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=13\left(5l+\varepsilon \right)+5\varepsilon =65l+18\varepsilon$ et ceux de la forme $n=13\left(5l-\varepsilon \right)+5\varepsilon =65l-8\varepsilon$ avec $\varepsilon =\pm 1$, c'est-à-dire les entiers congrus à $\pm 8{\text{ ou }}\pm {18}{\bmod {65}}$.

8. Soit d'abord $n=8k+1$. Alors, $n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv 0{\text{ ou }}-2{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}1{\bmod {5}}$.
   Soit d'autre part $n=8k+3$. Alors, $n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv -2{\text{ ou }}-4{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}2{\bmod {5}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=8\left(5l\right)+1=40l+1$, $n=8\left(5l+1\right)+1=40l+9$, $n=8\left(5l+1\right)+3=40l+11$ ou $n=8\left(5l+2\right)+3=40l+19$, c'est-à-dire les entiers congrus à $1,9,11{\text{ ou }}19{\bmod {40}}$.

9. Soit d'abord $n=8k-1$. Alors, $n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv -2{\text{ ou }}4{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}-2{\bmod {5}}$.
   Soit d'autre part $n=8k-3$. Alors, $n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv 0{\text{ ou }}-4{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {5}}$.

   Les solutions sont donc les entiers $n$ de la forme $n=8\left(5l+1\right)-1=40l+7$, $n=8\left(5l-2\right)-1=40l-17$, $n=8\left(5l\right)-3=40l-3$ ou $n=8\left(5l+2\right)-3=40l+13$, c'est-à-dire les entiers congrus à $7,-17,-3{\text{ ou }}13{\bmod {40}}$.

 

Exercice 9-11

1. Montrer que pour tout entier naturel $n$, $5\mid (2^{3n+5}+3^{n+1})$.
2. Quel est le reste de la division euclidienne de $16^{(2^{1000})}$ par $7$ ?
3. Soit $n$ un entier impair non divisible par $3$. Montrer que $n^{2}\equiv 1{\bmod {24}}$.
4. Donner le dernier chiffre de l'écriture en base $10$ de $\sum _{k=0}^{10}k^{100}$.

Solution

1. Modulo 5, $2^{3n+5}+3^{n+1}\equiv 3^{n}\times 2+3^{n+1}=3^{n}\times 5\equiv 0$.
2. Modulo 7, $16\equiv 2$, or $2^{3}\equiv 1$. Modulo 3, $2^{1000}=4^{500}\equiv 1^{500}=1$. Donc $16^{(2^{1000})}\equiv 2{\bmod {7}}$.
3. Modulo 8, $n^{2}=(2k+1)^{2}=4k(k+1)+1\equiv 1$ et modulo 3, $n^{2}=(3\ell \pm 1)^{2}\equiv 1$.
4. $5+2\sum _{k=1}^{4}k^{100}$. Modulo 10,
   • $2^{5}\equiv 2$ donc $2^{4k+r}\equiv 2^{r}$ si $r>0$, donc $2^{100}\equiv 2^{4}\equiv -4$ et $4^{100}\equiv -4$ ;
   • $3^{4}\equiv 1$ donc $3^{100}\equiv 1^{25}=1$.

   $5+2(1-4+1-4)=-7\equiv 3$.

 

Exercice 9-12

On pose $A=4444^{4444}$. On note $B$ la somme des chiffres de $A$, $C$ la somme des chiffres de $B$ et $D$ la somme des chiffres de $C$. Déterminer $D$. (Indication : calculer $D$ modulo un nombre bien choisi et par ailleurs, majorer $D$.)

Solution

Modulo 9, $D\equiv A\equiv (-2)^{4444}=(-2)^{3\times 1481+1}\equiv 1^{1481}\times (-2)^{1}\equiv 7$.

Par ailleurs, $A<10^{4\times 4444}=10^{17776}$ donc $B\leq 9\times 17776=159984$ donc $C\leq 9\times 6=54$ donc $D\leq 5+9=14<9+7$.

Conclusion : $D=7$.

 

Liens externes

• « Calculatrice de restes chinois », sur dcode.fr
• « Solveur d'équation modulaire », sur dcode.fr