Exercice 4
5 points-Candidats ayant suivi l’enseignement de spécialité
Soit A l’ensemble des entiers naturels de l’intervalle [1 ; 46].
- On considère l’équation
(E) : 23x+47y=1
où x et y sont des entiers relatifs.- Donner une solution particulière \left(x_{0}, y_{0}\right) de (E).
- Déterminer l’ensemble des couples \left(x, y\right) solutions de (E).
- En déduire qu’il existe un unique entier x appartenant à A tel que 23x\equiv 1 \ \left(47\right).
- Soient a et b deux entiers relatifs.
- Montrer que si ab\equiv 0 \ \left(47\right) alors a\equiv 0 \ \left(47\right) ou b\equiv 0 \ \left(47\right).
- 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).
- 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). - Quels sont les entiers p de A qui vérifient p=\text{inv}\left(p\right) ?
- Montrer que 46! \equiv -1 \ \left(47\right).
- Montrer que pour tout entier p de A, il existe un entier relatif q tel que p \times q\equiv 1 \ \left(47\right).
Corrigé
- Une solution peut être trouvée avec l’algorithme d’Euclide. Ici, elle est évidente:
x_{0}=-2\ ;\ y_{0}=1 - 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 ! - 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
- Une solution peut être trouvée avec l’algorithme d’Euclide. Ici, elle est évidente:
- 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é. - 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
- ab\equiv 0\ \left(47\right) signifie que 47 divise ab.
- 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é.
- 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 - 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)