Congruence au bac
Le premier exercice est extrait d’une épreuve du bac S spé maths (centres étrangers, juin 2018). Son corrigé très détaillé illustre comment se référer à certaines propriétés de la congruence (l'exercice se poursuit en page d'exercices sur équations diophantiennes puis de codage RSA). Le second exercice est également extrait d’une épreuve du bac S (Liban, mai 2016).
Énoncé 1
- 1. Cette question envisage de calculer le reste dans la division euclidienne par 55 de certaines puissances de l’entier 8.
- a. Vérifier que \({8^7} \equiv 2\;\bmod \;55\)
En déduire le reste dans la division euclidienne par 55 du nombre \({8^{21}}\)
- b. Vérifier que \({8^2} \equiv 9\;\bmod \;55\), puis déduire de la question a. le reste dans la division euclidienne par 55 de \({8^{23}}\).
Corrigé 1
1. L’idée est de partir d’une faible puissance de 8 puis, grâce aux propriétés de la congruence, de s’élever jusqu’à \({8^7}\).
On sait que \(8 × 8 = 64.\) Or, \(64 = 55 + 9.\)
Par conséquent : \({8^2} \equiv 9\;[55].\)
Rappelons à présent la propriété suivante : si \(a \equiv b[n]\), alors \({a^p} \equiv {b^p}[n]\), avec \(p \in {\mathbb{N}^*}\).
Soit \(p = 3\).
\({\left( {{8^2}} \right)^3} \equiv {9^3}[55]\)
\( \Rightarrow {8^{6}} \equiv 729[55]\).
Ne conservons pas un reste aussi grand que 729. Par la division euclidienne de 729 par 55, on trouve un quotient de 13.
\(13 × 55 = 715.\) Le reste est donc de \(729 - 715 = 14.\)
\({8^6} \equiv 14[55]\)
Notez que nous aurions aussi pu commencer par élever 8 au cube avant d’appliquer la propriété avec \(p\) = 2 afin de parvenir à la puissance 6.
Pour établir la congruence à la puissance 7, il faut rappeler la propriété de multiplication par un entier relatif \(k\).
Si \(a \equiv b[n]\), alors \(ka \equiv kb[n]\).
Donc \({8^7} \equiv 8 \times 14[55]\)
\(14 × 8 = 112.\) Or, \(112 = 55 × 2 + 2.\)
Par conséquent \({8^7} \equiv 2[55]\).
On obtient bien le résultat que l’énoncé donne pour ne pas que les candidats se trouvent bloqués en début d’exercice.
Utilisons pour la seconde fois la propriété avec les puissances.
\(\begin{array}{l} {\left( {{8^7}} \right)^3} \equiv {2^3}[55]\\ \Rightarrow {8^{21}} \equiv 8[55] \end{array}\)
Le reste est donc égal à 8.
b. Nous devons vérifier que \({8^2} \equiv 9\;[55]\). C’est la première étape que nous avons choisie pour la question précédente. Nous ne la referons pas.
La question suivante requiert la propriété de multiplication.
Rappel : soit \(a \equiv b[n]\) et \(c \equiv d[n]\). Alors \(ac \equiv bd[n]\).
\(\left\{ {\begin{array}{*{20}{c}}
{{8^2} \equiv 9[55]}\\
{{8^{21}} \equiv 8[55]}
\end{array}} \right.\)
\(\begin{array}{l} {8^{23}} \equiv 8 \times 9[55]\\ \Rightarrow {8^{23}} \equiv 72[55] \end{array}\)
Comme \(72 = 55 + 17,\) alors \({8^{23}} \equiv 17[55].\)
Le reste de la division de \({8^{23}}\) par 55 est 17.
Énoncé 2
- Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse en justifiant la réponse. Un point est attribué par réponse exacte justifiée. Une réponse non justifiée ne sera pas prise en compte et l’absence de réponse n’est pas pénalisée.
On considère le système d’inconnue \(n\) entier relatif.
- \(\left\{ {\begin{array}{*{20}{c}}
{n \equiv 1[5]}\\
{n \equiv 3[4]}
\end{array}} \right.\)
- Affirmation 1. Si \(n\) est solution de ce système alors \(n - 11\) est divisible par 4 et par 5.
- Affirmation 2. Pour tout entier relatif \(k\), l’entier \(11 + 20k\) est solution du système.
- Affirmation 3. Si un entier relatif \(n\) est solution du système alors il existe un entier relatif \(k\) tel que \(n = 11 + 20k\).
Corrigé 2
Affirmation 1
Si \(n\) est solution du système, alors \(n - 11 \equiv 0[5]\) et \(n - 11 \equiv 0[4]\).
\(\begin{array}{l}
\left\{ {\begin{array}{*{20}{c}}
{n - 11 \equiv 1 - 11[5]}\\
{n - 11 \equiv 3 - 11[4]}
\end{array}} \right.\\
\left\{ {\begin{array}{*{20}{c}}
{n - 11 \equiv - 10[5]}\\
{n - 11 \equiv - 8[4]}
\end{array}} \right.
\end{array}\)
Or \(-10\) \(=\) \(5 × (-2)\) et \(-8 = 4 × (-2).\) Nous avons bien \(\left\{ {\begin{array}{*{20}{c}}
{n - 11 \equiv 0[5]}\\
{n - 11 \equiv 0[4]}
\end{array}} \right.\)
Si \(n\) est solution du système, \(n - 11\) est divisible par 4 et par 5. L’affirmation 1 est vraie.
Affirmation 2
Rappelons la propriété d’addition. Soit \(a \equiv b[n]\) et \(c \equiv d[n].\) Alors \(a + c \equiv b + d[n]\).
Nous savons que \(11 \equiv 1[5]\) (puisque \(11 = 2 × 5 + 1\) et \(20k \equiv 0[5]\) (puisque 20 est un multiple de 5 et que les multiples de 20 sont aussi des multiples de 5).
Donc, par propriété d’addition, \(11 + 20k \equiv 1[5]\).
Nous savons aussi que \(11 \equiv 3[4]\) (puisque 11 = 4 × 2 + 3) et \(20k \equiv 0[4]\) (puisque 20 est un multiple de 4 et que les multiples de 20 sont aussi des multiples de 4).
Donc \(11 + 20k \equiv 3[4].\)
Les deux congruences du système sont vérifiées. \(11 + 20k\) est solution du système et l’affirmation 2 est vraie.
Affirmation 3
Comme 20 est un multiple de 4 et de 5, alors \(20k \equiv 0[4]\) et \(20k \equiv 0[5].\) Donc \(20k = n - 11\) (Cf. le système obtenu en question 1) et \(n = 20k + 11.\)
Nous pouvons l’étayer par une démonstration plus aboutie : nous vérifions qu’une solution particulière du système est \(n = 11\) (obtenu avec \(k = 0.\)) Ensuite nous appliquons le théorème de Gauss : si \(a\) divise \(bc\) et si \(a\) et \(b\) sont premiers entre eux, alors \(a\) divise \(c\).
En l’occurrence, 4 et 5 sont premiers entre eux et 4 divise \(n - 11.\) Donc \(n - 11 = 4c\). Et donc 5 divise \(c.\) On pose alors \(c = 5k.\)
Nous obtenons \(n - 11 = 4 × 5k.\)
\( \Leftrightarrow n = 20k + 11\)
L’affirmation 3 est vraie.
