Quiz sur les Congruences

Correction:

$a \equiv b \pmod{m}$ signifie que $a$ et $b$ ont le même reste lorsqu'ils sont divisés par $m$. Cela signifie aussi que $a - b$ est divisible par $m$.

Correction:

$5$ divisé par $3$ donne un quotient de $1$ et un reste de $2$. Donc, $5 \equiv 2 \pmod{3}$.

Correction:

$17 = 5 \times 3 + 2$. Le reste est donc $2$. On peut aussi écrire $17 \equiv 2 \pmod{5}$.

Correction:

On peut additionner les congruences : $a + b \equiv 3 + 5 \equiv 8 \equiv 1 \pmod{7}$.

Correction:

On peut multiplier les deux membres d'une congruence par un même nombre : $2a \equiv 2 \times 4 \equiv 8 \pmod{9}$.

Correction:

$3^4 = 81$. $81$ divisé par $5$ donne un reste de $1$. Donc, $3^4 \equiv 1 \pmod{5}$. On peut aussi calculer progressivement : $3^2 \equiv 9 \equiv 4 \pmod{5}$, puis $3^4 \equiv 4^2 \equiv 16 \equiv 1 \pmod{5}$.

Correction:

On cherche un multiple de $4$ qui, lorsqu'on le divise par $7$, donne un reste de $1$. $4 \times 2 = 8$, et $8 \equiv 1 \pmod{7}$. Donc $x=2$ est une solution.

Correction:

On peut lister les nombres congrus à $5$ modulo $12$: $5, 17, 29, ...$ On cherche le premier de cette liste qui est aussi congru à $2$ modulo $5$. $17$ est le premier qui fonctionne: $17 = 5 \times 3 + 2$.

Correction:

Il faut trouver l'inverse multiplicatif de $11$ modulo $26$. On peut tester les valeurs, ou utiliser l'algorithme d'Euclide étendu. On trouve que $11 \times 19 = 209 = 26 \times 8 + 1$. Donc $11 \times 19 \equiv 1 \pmod{26}$, et $x=19$.

Correction:

$2^{10} = 1024$. $1024 = 11 \times 93 + 1$. Donc $2^{10} \equiv 1 \pmod{11}$. (C'est un cas particulier du petit théorème de Fermat).

Correction:

On remarque que $7 \equiv 2 \pmod{5}$. Donc $7^{20} \equiv 2^{20} \pmod{5}$. De plus, $2^2 = 4 \equiv -1 \pmod{5}$. Donc, $2^{20} = (2^2)^{10} \equiv (-1)^{10} = 1 \pmod{5}$ NON ! $2^{20} = (2^2)^{10} \equiv (-1)^{10} = 1 \pmod{5}$ Puis $4 \pmod{5}$. $7^{20} \equiv 2^{20} \equiv (2^{2})^{10}\equiv (4)^{10} \pmod{5}$. Donc $7^{20} \equiv 4 \pmod{5}$.

Correction:

On cherche l'inverse de $3$ modulo $5$. On remarque que $3 \times 2 = 6 \equiv 1 \pmod{5}$. Donc, on multiplie les deux côtés de l'équation par $2$: $2 \times 3x \equiv 2 \times 2 \pmod{5}$, ce qui donne $6x \equiv 4 \pmod{5}$, ou encore $x \equiv 4 \pmod{5}$.

Correction:

Trouver le chiffre des unités revient à trouver le reste de la division par 10. On calcule les premières puissances de 3 modulo 10: $3^1 \equiv 3 \pmod{10}$, $3^2 \equiv 9 \pmod{10}$, $3^3 \equiv 27 \equiv 7 \pmod{10}$, $3^4 \equiv 81 \equiv 1 \pmod{10}$. La suite des restes est donc périodique de période 4: (3, 9, 7, 1). On divise l'exposant 456 par 4: $456 = 4 \times 114 + 0$. Le reste est 0, ce qui correspond au dernier terme de la période, qui est 1. Donc, $3^{456} \equiv 1 \pmod{10}$.

Correction:

On peut utiliser le théorème des restes chinois. Une solution particulière est $x_0 = 2 \times 7 \times 3 + 3 \times 5 \times 3 = 42 + 45 = 87$. Le théorème des restes chinois nous dit que toutes les solutions sont de la forme $x \equiv x_0 \pmod{5 \times 7}$, c'est-à-dire $x \equiv 87 \pmod{35}$. Comme $87 = 35 \times 2 + 17$, on a $x \equiv 17 \pmod{35}$.

Correction:

On calcule les premières puissances de 2 modulo 15: $2^1 \equiv 2 \pmod{15}$, $2^2 \equiv 4 \pmod{15}$, $2^3 \equiv 8 \pmod{15}$, $2^4 \equiv 16 \equiv 1 \pmod{15}$. La suite des restes est périodique de période 4. On a $100 = 4 \times 25 + 0$. Le reste de la division de 100 par 4 est 0, ce qui correspond au dernier terme de la période (1). Donc $2^{100} \equiv 1 \pmod{15}$.

Correction:

Oui, la relation de congruence est symétrique. Si $a \equiv b \pmod{m}$, alors $m$ divise $a - b$. Donc $m$ divise aussi $b - a = -(a - b)$, et donc $b \equiv a \pmod{m}$.

Correction:

Oui, on peut additionner les congruences. Si $a \equiv b \pmod{m}$ et $c \equiv d \pmod{m}$, alors $m$ divise $a-b$ et $m$ divise $c-d$. Donc $m$ divise $(a-b) + (c-d) = (a+c) - (b+d)$, ce qui signifie que $a+c \equiv b+d \pmod{m}$.

Correction:

Oui, on peut multiplier les deux membres d'une congruence par un même entier. Si $a \equiv b \pmod{m}$, alors $m$ divise $a - b$. Donc $m$ divise $c(a - b) = ac - bc$, ce qui implique que $ac \equiv bc \pmod{m}$.

Correction:

Un nombre est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9. La somme des chiffres de 123456789 est $1+2+3+4+5+6+7+8+9 = 45$, qui est divisible par 9. Donc $123456789 \equiv 0 \pmod{9}$.

Correction:

Remarquons que pour $n \ge 4$, $n!$ contient les facteurs $4$ et $3$, et donc est divisible par $12$. Donc, $4! \equiv 5! \equiv ... \equiv 100! \equiv 0 \pmod{12}$. Il suffit donc de considérer la somme $1! + 2! + 3! = 1 + 2 + 6 = 9$. Donc, $1! + 2! + 3! + 4! + ... + 100! \equiv 9 \pmod{12}$.

Correction:

$5 \times 7 = 35$. En divisant 35 par 8, on obtient un quotient de 4 et un reste de 3. Donc $5 \times 7 \equiv 3 \pmod{8}$.

Correction:

C'est une application du théorème des restes chinois. On peut chercher la solution en testant les nombres congrus à 2 modulo 7, puis en vérifiant les autres congruences. Les nombres congrus à 2 modulo 7 sont: 2, 9, 16, 23, 30, ... Parmi ceux-ci, 23 est le premier qui est congru à 3 modulo 5 ($23 = 5\times4 + 3$). Il se trouve aussi qu'il est congru à 2 modulo 3. Donc 23 est la plus petite solution positive.

Correction:

Si $a \equiv 5 \pmod{11}$, alors $a^2 \equiv 5^2 \equiv 25 \equiv 3 \pmod{11}$ car $25=2\times11+3$. NON! C'EST 3. Si $a \equiv 5 \pmod{11}$, alors $a^2 \equiv 5^2 \equiv 25 \pmod{11}$. $25 \equiv 3 \pmod{11}$, donc $a^2 \equiv 3 \pmod{11}$.

Correction:

Oui, car 100 est divisible par 4 ($100 = 4 \times 25$).

Correction:

On cherche un multiple de 6 qui donne un reste de 1 quand on le divise par 13. On peut tester les valeurs: $6 \times 2 = 12 \equiv 12 \pmod{13}$, $6 \times 7 = 42 \equiv 3 \pmod{13}$, $6\times11=66 = 5\times13+1$. Donc $66 \equiv 1 \pmod{13}$, et x=11.

Correction:

On regarde les puissances cinquièmes modulo 4. On a $0^5 \equiv 0 \pmod{4}$, $1^5 \equiv 1 \pmod{4}$, $2^5 = 32 \equiv 0 \pmod{4}$, $3^5 = 243 \equiv 3 \pmod{4}$. La suite des restes des puissances cinquièmes est donc (0, 1, 0, 3), et elle se répète. La somme de ces quatre restes est $0 + 1 + 0 + 3 = 4 \equiv 0 \pmod{4}$. Comme 100 est un multiple de 4, la somme des 100 premiers termes sera aussi congrue à 0 modulo 4.

Correction:

$-2 \equiv 3 \pmod{5}$ car $-2 = 5 \times (-1) + 3$.

Correction:

$29 \times 14 = 406$. $406 = 9 \times 41+37 \equiv 37 \pmod{41}$ Donc la réponse est fausse, il faut utiliser l'algorithme d'euclide etendu. Il faut trouver l'inverse de $29$ modulo 41. On peut tester les multiplications, ou bien utiliser l'algorithme d'Euclide étendu. On trouve que $29*3 = 87 = 2*41 + 5$. $5 = 29*3 - 2*41$. Puis, $6*29 = 6*(87-41) = 522 - 246 = 174 = 4*41 + 10$. $10 = 6*29 -4*41$

On cherche l'inverse de $29$ modulo $41$. On peut tester les valeurs :
$29 \times 1 \equiv 29 \pmod{41}$
$29 \times 2 \equiv 58 \equiv 17 \pmod{41}$
$29 \times 3 \equiv 87 \equiv 5 \pmod{41}$
...
$29 \times 14 \equiv 406 \equiv 406 - 410 \equiv -4 \pmod{41}$

Correction:

On peut tester tous les restes possibles modulo 8: $0^2 \equiv 0$, $1^2 \equiv 1$, $2^2 \equiv 4$, $3^2 \equiv 9 \equiv 1$, $4^2 \equiv 16 \equiv 0$, $5^2 \equiv 25 \equiv 1$, $6^2 \equiv 36 \equiv 4$, $7^2 \equiv 49 \equiv 1$. Donc les solutions sont $x \equiv 1, 3, 5, 7 \pmod{8}$.

Correction:

$p^2 - 1 = (p-1)(p+1)$. Comme $p$ est premier et supérieur à 3, il est impair. Donc $p-1$ et $p+1$ sont deux nombres pairs consécutifs. L'un des deux est donc divisible par 4, et l'autre est divisible par 2. Donc $(p-1)(p+1)$ est divisible par 8. De plus, comme $p$ est premier et supérieur à 3, il n'est pas divisible par 3. Donc soit $p-1$, soit $p+1$ est divisible par 3. Donc $(p-1)(p+1)$ est divisible à la fois par 3 et par 8, et comme 3 et 8 sont premiers entre eux, $(p-1)(p+1)$ est divisible par $3 \times 8 = 24$.