Maths-cours

Cours & exercices de mathématiques

  • Troisième
  • Seconde
  • Première ES/L
  • Première S
  • Terminale ES/L
  • Terminale S
  • Quiz
  • 3ème
  • 2nde
  • 1ES/L
  • 1S
  • TES/L
  • TS

Terminale S

difficulté moyenneExercice corrigé

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)
  Signaler une erreur

Dans ce chapitre...

Cours

  • PGCD et nombres premiers (Spécialité)

Exercices

  • difficulté moyenne Cryptographie – Bac S Pondichéry 2016 (spé)
  • difficulté moyenne Théorème des restes chinois
  • difficulté moyenne Congruences-Bac S Liban 2009
  • très difficile Différence de deux puissances
  • difficulté moyenne Arithmétique : Suite d’entiers – Bac S Amérique du Nord 2011
  • assez facile Déterminer le PGCD

Méthodes

  • Calcul du PGCD – Algorithme d’Euclide
  • Algorithme d’Euclide étendu

Outils

  • Outil : Th. de Bézout – Calcul des coefficients

VOIR AUSSI…

Derniers quiz

  1. [1esl]Pourcentages (moyen)
  2. [Ts]Limites de fonctions (moyen)
  3. [1s]Second degré (facile)
  4. [2nde]Les fonctions (facile)
  5. [Ts]Les suites (facile)

© 2019 - Maths-cours.fr - Nous contacter

Nous utilisons des cookies pour vous garantir la meilleure expérience sur notre site. Si vous continuez à utiliser ce dernier, nous considérerons que vous acceptez l'utilisation des cookies.Ok