# Arithmétique/Exercices/Congruences
## Exercice 9-1

Quel est le reste de la division par 7 du nombre 32$^{45}$ ?
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$^{114}$ ?
$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$^{1998}$ ?
$91234=13033\times 7+3$, $3^{3}\equiv -1{\pmod {7}}$ et $6\mid 1998$, donc le reste est 1.

## Exercice 9-4

* Démontrez que si l'on divise un entier n par 111, on trouve le même reste qu'en divisant 1000n par 111.
* Déduisez-en que les deux nombres 10$^8$ + 10$^4$ + 1 et 10$^{10}$ + 10$^5$ + 1 sont divisibles par 111.
* $1000=9\times 111+1$.
* 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$^6$ – 1 soit divisible par 9 ?
Modulo 9, n$^3$ 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$_1$, n$_2$, n$_3$, n$_4$ et n$_5$ 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.
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

* 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.)
* Démontrer que si p est premier et différent de 3, alors 8p$^2$ + 1 est composé.
* 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$^2$ – 1 ≡ 0.
* Si p est premier et différent de 3, alors, modulo 3, p ≡ ±1 donc 8p$^2$ + 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}}$
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}}$.
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

* Trouvez tous les entiers congrus à la fois à $1{\bmod {13}}$ et à $6{\bmod {7}}$.
* Trouvez tous les entiers congrus à la fois à $5{\bmod {8}}$ et à $1{\bmod {27}}$.
* Trouvez tous les entiers congrus à la fois à $1{\bmod {4}}$ et à $\pm 1{\bmod {5}}$.
* Trouvez tous les entiers congrus à la fois à $3{\bmod {4}}$ et à $\pm 2{\bmod {5}}$.
* Trouvez tous les entiers congrus à la fois à $1{\bmod {3}}$ et à $\pm 1{\bmod {8}}$.
* Trouvez tous les entiers congrus à la fois à $-1{\bmod {3}}$ et à $\pm 3{\bmod {8}}$.
* Trouvez tous les entiers congrus à la fois à $\pm 2{\bmod {5}}$ et à $\pm 5{\bmod {13}}$.
* Trouvez tous les entiers congrus à la fois à $1$ ou $3{\bmod {8}}$ et à $\pm 1{\bmod {5}}$.
* Trouvez tous les entiers congrus à la fois à $-1$ ou $-3{\bmod {8}}$ et à $\pm 2{\bmod {5}}$.
* 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}$.
* 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}$.
* 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}}$.
* 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}}$.
* 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}}$.
* 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}}$.
* 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}}$.
* 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}}$.
* 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

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