Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

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 23x+47y=1

    xx et yy sont des entiers relatifs.

    1. Donner une solution particulière (x0,y0)\left(x_{0}, y_{0}\right) de (E).

    2. Déterminer l'ensemble des couples (x,y)\left(x, y\right) solutions de (E).

    3. En déduire qu'il existe un unique entier xx appartenant à A tel que 23x1 (47)23x\equiv 1 \ \left(47\right).

  2. Soient aa et bb deux entiers relatifs.

    1. Montrer que si ab0 (47)ab\equiv 0 \ \left(47\right) alors a0 (47)a\equiv 0 \ \left(47\right) ou b0 (47)b\equiv 0 \ \left(47\right).

    2. En déduire que si a21 (47)a^{2}\equiv 1 \ \left(47\right) alors a1 (47)a\equiv 1 \ \left(47\right) ou a a1 (47)a\equiv - 1 \ \left(47\right).

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

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

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

      Par exemple :

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

    2. Quels sont les entiers pp de A qui vérifient p=inv(p)p=\text{inv}\left(p\right) ?

    3. Montrer que 46!1 (47)46! \equiv - 1 \ \left(47\right).

Corrigé

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

      x0=2 ; y0=1x_{0}= - 2\ ;\ y_{0}=1

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

      On obtient :

      23(x+2)=47(1y)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+2x+2

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

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

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

      23x+47y=123x+47y=1

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

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

    1. ab0 (47)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. a21 (47)(a1)(a+1)0 (47)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 1p461\leqslant p\leqslant 46, pp 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=inv(p)p2=1p=\text{inv}\left(p\right) \Leftrightarrow p^{2}=1

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

      p=1p=1 ou p=46p=46

    3. 46!=1×2×3...×4646! = 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!1×461 (47)46! \equiv 1\times 46\equiv - 1\ \left(47\right)