Cours Stage - Divisibilité et congruence

Congruences

L'énoncé

Prenez un brouillon pour répondre aux questions suivantes


Question 1

Déterminer le reste de la division euclidienne par $11$ de $12^{15}$

On a : $12 \equiv 1[11]$

Donc : $12^{15} \equiv 1^{15}[11]$

Ainsi : $12^{15} \equiv 1[11]$

Conclusion,  le reste de la division euclidienne par $11$ de $12^{15}$ vaut $1$.

Ecrire la division euclidienne de $12$ par $11$.


En déduire une congruence de $12$ modulo $11$

Question 2

Résoudre l'équation suivante :

$3x\equiv 7 [9]$

On travaille modulo $9$ donc les restes possibles dans la division euclidiennes sont les entiers de $0$ à $8$.

 

$x$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$
$3x$ $0$ $3$ $6$ $0$ $3$ $6$ $0$

$3$

$6$

Pour info, voic le détail du résultat pour $x=5$

On a : $3x=15$ et $15=1\times 9 +6$

Le reste de la division euclidienne de $15$ par $9$ vaut donc $6$.

 

Résolvons à présent : $3x\equiv 7 [9]$

Cette équation n'a pas de solution. En effet les seuls restes possibles sont $0\ ;\ 3\ ;\ 6$

 

Faire un tableau avec les valeurs des différents restes possibles dans la division euclidienne par $9$.

Question 3

Quel est le reste de la division euclidienne de $57383^{114}$ par $19$ ?

On travaille modulo $19$.

On a : $57383=3020\times 19 +3$ donc $57383\equiv 3[19]$

On constate que : $3^2\equiv -10[19]$

$3^6\equiv 7[19]$

$3^{18}\equiv 1[19]$

Ce dernier résultat est intéressant que toute puissance entière de $1$ vaut toujours $1$

On écrit donc la division euclidienne de $114$ par $18$ :   $114=6\times 18+6$

On en déduit que $57383^{114}=57383^{6\times 18+6}$

Ainsi, $57383^{114}\equiv 3^{114}[19]$

$57383^{114}\equiv 3^{6\times 18+6}[19]$

$57383^{114}\equiv (3^{18})^6\times 3^6[19]$

$57383^{114}\equiv 1^6\times 7[19]$

$57383^{114}\equiv  7[19]$

 

Conclusion : le reste de la division euclidienne de $57383^{114}$ par $19$ est $7$

Ecrire la division euclidienne de $57383$ par $19$ pour commencer.


Chercher un entier $p$ vérifiant $3^p\equiv 1[19]$