\documentclass[11pt]{amsart}
\usepackage{kbexo}

\num{2}
\def\exoskip{2pt plus 5pt minus 2pt}
\course{MHT203 -- Cryptologie}
\begin{document}

\exotitle[Congruences]
\smallskip

\exo
\Q Écrire la table d'addition et de multiplication dans $\ZM/6\ZM$; 
donner la liste des $x\in \ZM/6\ZM$ tels qu'il existe $y\in\ZM/6\ZM$ tel
que $xy = 1$.
\Q Donner la liste des $x\in\ZM/6\ZM$ tels qu'il existe $y\in\ZM/6\ZM$,
$y\neq 0$, tel que $xy = 0$.
\Q Mêmes questions dans $\ZM/7\ZM$.

\exo
\Q Déterminer $35$ modulo $11$; montrer que $2^5\equiv 10\pmod{11}$ et
en déduire que $35^{57}-7$ est un multiple de $11$.
\Q En procédant de manière analogue, montrer que $9518^{42}\equiv 4 \pmod{5}$.

\exo
\Q Que signifie la phrase «$n$ est congru à $1$ modulo $3$» ?
\Q Traduire à l'aide d'une congruence «$n$ est divisible par $3$».
\Q Pour chacun des nombres suivants, donner l'entier positif le
plus petit auquel il est congru modulo $3$ : $1$, $10$, $100$, $1000$,
$10^k$ où $k$ est un entier positif.
\Q À l'aide de la question précédente, déterminer le plus petit
entier positif auquel est congru $4520$ modulo $3$.

\Q Soit $n = a_k \cdot 10^k+a_{k-1}\cdot 10^{k-1}+\dots +a_0\cdot 10^0$
un entier. Montrer que $n \equiv a_k+a_{k-1}+\cdots+a_0 \pmod{3}$. En déduire
qu'un entier est divisible par trois si et seulement si la somme de ces
chiffres est divisible par trois.

\Q Trouver des critères analogue de divisibilité par $9$, puis par $11$.

\exo Le but de cet exercice est de montrer que, pour tout 
$n\in\NM$, le nombre $A=n(n^2-1)$ est égal à $0$ modulo $6$.
\Q Calculer $A$, puis $A$ modulo $6$ dans chacun des cas suivants : $n=5;$
$n=16$; $n=32$.
\Q En donnant dans un tableau les différentes valeurs de $n$ modulo $6$, de
$n-1$ modulo $6$ et de $n+1$ modulo $6$, démontrer le résultat.

\exo
\Q Écrire les tables d'addition et de multiplication dans $\ZM/4\ZM$, puis
résoudre dans $\ZM/4\ZM$ les équations
$$ 3x+2=1;\quad 2x=0;\quad 2x=1; \quad 2x=2;\quad 2x=3.$$

\Q Soient $a, b, c \in \ZM/4\ZM$. S'il existe $a'\in\ZM/4\ZM$ tel que $aa' =
1$, que peut-on dire de l'équation $ax+b=c$ ?

\exo
Résoudre l'équation $18x-14y=22$ où $x$ et $y$ sont des entiers.
\end{document}
