Logo maths-cours.fr
Logo maths-cours.fr
Connexion Inscription
edit_note Exercices 40 min
Non commencé

Congruences – Bac S Amérique du Nord 2009

Exercice 4

5 points - Candidats ayant suivi l'enseignement de spécialité

Soit A l'ensemble des entiers naturels de l'intervalle [1 ; 46].

  1. On considère l'équation

    (E) : $ 23x+47y=1 $

    où $ x $ et $ y $ sont des entiers relatifs.

    1. Donner une solution particulière $ \left(x_{0}, y_{0}\right) $ de (E).
    2. Déterminer l'ensemble des couples $ \left(x, y\right) $ solutions de (E).
    3. En déduire qu'il existe un unique entier $ x $ appartenant à A tel que $ 23x\equiv 1 \ \left(47\right) $.

  2. Soient $ a $ et $ b $ deux entiers relatifs.

    1. Montrer que si $ ab\equiv 0 \ \left(47\right) $ alors $ a\equiv 0 \ \left(47\right) $ ou $ b\equiv 0 \ \left(47\right) $.
    2. En déduire que si $ a^{2}\equiv 1 \ \left(47\right) $ alors $ a\equiv 1 \ \left(47\right) $ ou a $ a\equiv - 1 \ \left(47\right) $.

    1. Montrer que pour tout entier $ p $ de A, il existe un entier relatif $ q $ tel que $ p \times q\equiv 1 \ \left(47\right) $.

      Pour la suite, on admet que pour tout entier $ p $ de A, il existe un unique entier, noté $ \text{inv}\left(p\right) $, appartenant à A tel que

      $ p \times \text{inv}\left(p\right)\equiv 1 \ \left(47\right) $.

      Par exemple :

      $ \text{inv}\left(1\right)=1 $ car $ 1 \times 1\equiv 1 \ \left(47\right) $, $ \text{inv}\left(2\right)=24 $ car $ 2 \times 24\equiv 1 \ \left(47\right) $, $ \text{inv}\left(3\right)=16 $ car $ 3 \times 16\equiv 1 \ \left(47\right) $.

    2. Quels sont les entiers $ p $ de A qui vérifient $ p=\text{inv}\left(p\right) $ ?
    3. Montrer que $ 46! \equiv - 1 \ \left(47\right) $.

Corrigé

    1. Une solution peut être trouvée avec l'algorithme d'Euclide. Ici, elle est évidente:

      $ x_{0}= - 2\ ;\ y_{0}=1 $

    2. $ 23x+47y=1 \Leftrightarrow 23x+47y=23\times \left( - 2\right)+47\times 1 $

      On obtient :

      $ 23\left(x+2\right)=47\left(1 - y\right) $

      23 et 47 sont premiers entre eux donc d'après le théorème de Gauss 47 divise $ x+2 $

      En posant $ x+2=47k\ ;\ k\in \mathbb{Z} $ on trouve que les solutions sont de la forme :

      $ \left( - 2+47k;1 - 23k\right)\ ;\ k\in \mathbb{Z} $ Réciproquement, vérifiez que ces couples sont bien solutions !

    3. $ 23x\equiv 1 \ \left(47\right) $ si et seulement si il existe un entier relatif $ y $ tel que:

      $ 23x+47y=1 $

      On montre à partir du b. qu'il existe une unique solution pour laquelle $ x $ est compris entre 1 et 46 (on peut partir de l'encadrement $ 1\leqslant x\leqslant 46 $ pour trouver un encadrement de $ k $)

      Elle correspond à $ k=1 $ et donc $ x=45 $

    1. $ ab\equiv 0\ \left(47\right) $ signifie que 47 divise ab.

      On applique alors le théorème de Gauss et on arrive rapidement au résultat demandé.

    2. $ a^{2}\equiv 1 \ \left(47\right) \Leftrightarrow \left(a - 1\right)\left(a+1\right)\equiv 0 \ \left(47\right) $

      Il suffit alors d'appliquer les résultats de la question précédente

    1. Comme $ 1\leqslant p\leqslant 46 $, $ p $ et 47 sont premiers entre eux; on peut alors appliquer le théorème de Bézout qui mène directement au résultat recherché.

    2. $ p=\text{inv}\left(p\right) \Leftrightarrow p^{2}=1 $

      On applique le résultat de 2.b. et compte tenu du fait que $ p\in A $ on trouve

      $ p=1 $ ou $ p=46 $

    3. $ 46! = 1\times 2\times 3. . . \times 46 $.

      A l'exception de 1 et de 46, on peut regrouper les 44 facteurs restants en 22 paires d'entiers "inverses" l'un de l'autre dont le produit vaut 1.

      On a donc:

      $ 46! \equiv 1\times 46\equiv - 1\ \left(47\right) $