Logo maths-cours.fr maths-cours.fr
Logo maths-cours.fr maths-cours.fr
Connexion Inscription
PGCD et nombres premiers Exercices

Congruences – Bac S Amérique du Nord 2009

Durée estimée
20 minutes
Difficulté
Votre progression

Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.

Créer un compte

Objectif travaillé

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érifier 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) $