Examen National 2020 (Session de Rattrapage) : Arithmétique
-
-
Par hypothèse, on a :
\[ 9^{p+q-1} \equiv 1 \pmod{pq} \]
On peut réécrire cette congruence en isolant un facteur $9$ :
\[ 9 \times 9^{p+q-2} \equiv 1 \pmod{pq} \]
Cette égalité prouve que $9$ admet un inverse (qui est $9^{p+q-2}$) modulo $pq$.
Or, un élément est inversible modulo $n$ si et seulement s'il est premier avec ce module. On en déduit donc directement que : \[ 9 \land pq = 1 \] Puisque $9$ est premier avec le produit $pq$, il est nécessairement premier avec chacun de ses facteurs. Par conséquent : \[ 9 \land p = 1 \quad \text{et} \quad 9 \land q = 1 \] - Puisque $p$ est premier et que $p \land 9 = 1$, le petit théorème de Fermat donne : \[ 9^{p-1} \equiv 1 \pmod p \] Or, l'hypothèse $9^{p+q-1} \equiv 1 \pmod{pq}$ implique que la congruence reste vraie modulo $p$ : \[ 9^{p+q-1} \equiv 1 \pmod p \] En décomposant l'exposant, on obtient : \begin{align*} 9^{p-1} \times 9^q &\equiv 1 \pmod p \\ 1 \times 9^q &\equiv 1 \pmod p \qquad (\text{car } 9^{p-1} \equiv 1 \pmod p) \end{align*} Soit : \[ 9^q \equiv 1 \pmod p \]
-
Par hypothèse, on a :
\[ 9^{p+q-1} \equiv 1 \pmod{pq} \]
On peut réécrire cette congruence en isolant un facteur $9$ :
\[ 9 \times 9^{p+q-2} \equiv 1 \pmod{pq} \]
Cette égalité prouve que $9$ admet un inverse (qui est $9^{p+q-2}$) modulo $pq$.
-
- On sait que $p-1 < q$ et que $q$ est un nombre premier. Leurs seuls diviseurs communs possibles sont $1$ ou $q$. Or $q$ ne peut pas diviser $p-1$ (qui est strictement plus petit que lui). On a donc nécessairement : \[ (p-1) \land q = 1 \]
-
Pour déterminer la valeur de $p$, nous pouvons procéder de deux manières différentes :
Méthode 1 : Par l'identité de Bachet-Bézout
Puisque $(p-1)$ et $q$ sont premiers entre eux, il existe un couple d'entiers naturels $(u,v)$ tel que : \[ u(p-1) - vq = 1 \implies u(p-1) = vq + 1 \] En élevant $9$ à cette puissance : \begin{align*} 9^{u(p-1)} &= 9^{vq+1} \\ (9^{p-1})^u &= (9^q)^v \times 9 \end{align*} En passant cette équation modulo $p$, et en utilisant les résultats de la question 1 ($9^{p-1} \equiv 1 \pmod p$ et $9^q \equiv 1 \pmod p$), il vient : \begin{align*} 1^u &\equiv 1^v \times 9 \pmod p \\ 1 &\equiv 9 \pmod p \\ 8 &\equiv 0 \pmod p \end{align*}Méthode 2 : Par l'ordre d'un élément (Théorie des groupes)
Soit $d = \text{ord}_p(9)$ l'ordre de $9$ dans le groupe multiplicatif $(\mathbb{Z}/p\mathbb{Z})^*$.
D'après la question 1, on a $9^q \equiv 1 \pmod p$, ce qui implique que l'ordre $d$ divise $q$ ($d \mid q$). Puisque $q$ est premier, les seules valeurs possibles pour $d$ sont $1$ ou $q$.
D'autre part, le petit théorème de Fermat donne $9^{p-1} \equiv 1 \pmod p$, ce qui implique également que $d \mid (p-1)$.
L'ordre $d$ divise à la fois $q$ et $p-1$, il divise donc leur PGCD. Or, d'après la question précédente, $(p-1) \land q = 1$.
On en déduit rigoureusement que $d = 1$.
Par définition de l'ordre d'un élément, cela signifie que $9^1 \equiv 1 \pmod p$, soit : \[ 8 \equiv 0 \pmod p \] Conclusion (commune aux deux méthodes) :
La congruence $8 \equiv 0 \pmod p$ signifie que $p$ divise $8$. Puisque $p$ est un nombre premier, la seule possibilité est : \[ p = 2 \]
-
-
D'après la question 1.a), nous avons déjà démontré que $9 \land q = 1$.
Puisque $q$ est un nombre premier, le petit théorème de Fermat s'applique directement et donne : \[ 9^{q-1} \equiv 1 \pmod q \] -
On a par hypothèse $9^{p+q-1} \equiv 1 \pmod{pq}$. Sachant que $p=2$, on obtient :
\[ 9^{q+1} \equiv 1 \pmod{2q} \]
Ce qui implique que la congruence est vraie modulo $q$ :
\begin{align*}
9^{q+1} &\equiv 1 \pmod q \\
9^2 \times 9^{q-1} &\equiv 1 \pmod q
\end{align*}
D'après la question précédente, $9^{q-1} \equiv 1 \pmod q$. L'équation se simplifie en :
\begin{align*}
9^2 &\equiv 1 \pmod q \\
81 &\equiv 1 \pmod q \\
80 &\equiv 0 \pmod q
\end{align*}
Par conséquent, $q$ divise $80 = 2^4 \times 5$.
Puisque $q$ est un nombre premier impair (car $q > p-1 \implies q > 1$ et les rôles de $p$ et $q$ garantissent $q \neq 2$), la seule possibilité est : \[ q = 5 \]
Vérification (Réciproque) :
Si $(p,q) = (2,5)$, vérifions l'hypothèse initiale : \[ 9^{2+5-1} = 9^6 = 531441 \] Et $pq = 10$. On a bien $531441 \equiv 1 \pmod{10}$.
Le couple solution est donc bien $(2,5)$.
-
D'après la question 1.a), nous avons déjà démontré que $9 \land q = 1$.