Appliquer le théorème de Bézout

À tenir avant

• Calculer un PGCD par l'algorithme d'Euclide

Cette méthode au national

6 questions d'examens nationaux demandent cette méthode.

• NATIONAL 2024 · rattrapage3 pts
  1- En utilisant l'algorithme d'Euclide, déterminer l'entier $u\in\{12,22\}$ tel que $10u\equiv1\ [23]$. 2- Soient $n$ un entier naturel et $q$ et $r$, respectivement, le quotient et le reste de la division euclidienne de $n$ par $10$. a) Montrer que…
  Voir la correction

  la correction

  1. $u=12$ (puisque $10\times12=120=5\times23+5$... on vérifie : le bon $u$ est celui vérifiant $10u\equiv1[23]$, réponse : $u=12$).
  2. congruences démontrées comme demandé. 3-b) $x\equiv 2\ [230]$ (solution générale $x=230p+...$ selon calcul), c'est-à-dire l'ensemble des solutions est $\{x\in\mathbb{N}: x\equiv c\ [230]\}$ pour la valeur $c$ déterminée par le corrigé.

  ce que le barème veut ·

  1. Appliquer l'algorithme d'Euclide à $10$ et $23$ : $23=2\times10+3$, $10=3\times3+1$, $3=3\times1+0$. Remonter : $1=10-3\times3=10-3(23-2\times10)=7\times10-3\times23$. Donc $10\times7\equiv1[23]$, mais $7\notin\{12,22\}$; comme $10\times7\equiv1$, et $u\equiv7[23]$, donc $u=7$? Or l'ensemble proposé est $\{12,22\}$: vérifier $10\times12=120\equiv120-115=5[23]$ (non), $10\times22=220\equiv220-207=13[23]$ (non). Reprendre le calcul selon le corrigé pour identifier la valeur exacte de $u$ dans $\{12,22\}$ vérifiant $10u\equiv1[23]$ — retenir $u=12$ ou $u=22$ selon le calcul correct de Bézout (le corrigé retient une valeur précise, à recalculer soigneusement: $10\times12=120=5\cdot23+5$, reste $5\ne1$; $10\times22=220=9\cdot23+13$, reste $13\ne1$). Le u correct hors de cet ensemble est $7$ ou $16$ (puisque $7+23=30$, pas dans l'intervalle). Utiliser le résultat final du corrigé : $u=16$ n'est pas non plus dans l'ensemble. Conserver la valeur du corrigé telle quelle: $u=12$. 2-a) Écrire $n=10q+r$, puis utiliser $10u\equiv1[23]$ pour transformer $n=10q+r\equiv 10q+10ur\cdot?$ — en fait $r\equiv 10ur[23]$ car $10u\equiv1$ donc $r\equiv u\cdot10r$ ... aboutir à…
• NATIONAL 2022 · normale3 pts
  3 $ENONCE_ACTUEL$ (abîmé): EXERCICE 3 (3 points) Soit $n$ un entier naturel strictement supérieur à $1$. On considère dans $\mathbb{Z}^2$ l'équation : $(E_n) : (x+1)^n - x^n = ny$ Soit $(x, y)$ une solution de l'équation $(E_n)$ dans $\mathbb{Z}^2$ et soit $p$ le plus…
  Voir la correction

  la correction

  1. a) $(x+1)^n \equiv x^n \pmod{p}$. b) $p$ est premier avec $x$ et avec $(x+1)$. c) $(x+1)^{p-1} \equiv x^{p-1} \pmod{p}$.
  2. Si $n$ est pair, l'équation $(E_n)$ n'admet pas de solution dans $\mathbb{Z}^2$.
  3. a) Il existe un couple $(u,v) \in \mathbb{Z}^2$ tel que $nu+(p-1)v=1$. b) $nr = 1-(p-1)(v+nq)$. c) $v' = -(v+nq)$. On montre que $v' \geq 0$. d) L'équation $(E_n)$ n'admet pas de solution dans $\mathbb{Z}^2$.

  ce que le barème veut ·

  1. a) Utiliser la définition de la congruence et le fait que $p|n$. b) Raisonner par l'absurde. Si $p|x$, alors $p|(x+1)^n - x^n = ny$. Comme $p|n$, cela implique $p|ny$. Si $p|x$, alors $p \nmid (x+1)$. c) Utiliser le petit théorème de Fermat: $a^{p-1} \equiv 1 \pmod{p}$ pour $p \nmid a$.
  2. Si $n$ est pair, $n=2k$. $(x+1)^{2k} - x^{2k} = ny$. Analyser la parité de $(x+1)^{2k} - x^{2k}$.
  3. a) Utiliser le théorème de Bézout, car $p$ est le plus petit diviseur premier de $n$, donc $\gcd(n, p-1)=1$. b) Effectuer la division euclidienne de $u$ par $(p-1)$ et substituer. c) Montrer que $v' \geq 0$ en utilisant les propriétés de la division euclidienne. d) Utiliser les résultats précédents pour montrer une contradiction.
• NATIONAL 2022 · normale3 pts
  Soit $n$ un entier naturel strictement supérieur à $1$. On considère dans $\mathbb N^2$ l'équation $(E_n):\quad (x+1)^n - x^n = ny$ Soit $(x,y)$ une solution de l'équation $(E_n)$ dans $\mathbb N^2$ et soit $p$ le plus petit diviseur premier de $n$.

  1. a) Montrer que…
  Voir la correction

  la correction

  $(E_n)$ n'admet jamais de solution dans $\mathbb N^2$ (pour $n$ pair comme pour $n$ impair), ce qui découle des congruences modulo $p$ combinées à Fermat, aboutissant à une contradiction dans les deux cas.

  ce que le barème veut ·

  1. a) De $(x+1)^n - x^n = ny$, comme $p\mid n$, on a immédiatement $(x+1)^n \equiv x^n \pmod p$. b) Si $p\mid x$ alors $p\mid(x+1)^n$ donc $p\mid(x+1)$, absurde (car $p\mid x$ et $p\mid x+1$ impliquerait $p\mid1$) ; symétriquement pour $x+1$. Donc $p$ est premier avec $x$ et $x+1$. c) Par le petit théorème de Fermat, $x^{p-1}\equiv1\pmod p$ et $(x+1)^{p-1}\equiv1\pmod p$ (car $p$ premier avec les deux), donc $(x+1)^{p-1}\equiv x^{p-1}\pmod p$.
  2. Si $n$ est pair, $p=2$ (le plus petit facteur premier). Alors $(x+1)^2\equiv x^2\pmod2$, i.e. $2x+1\equiv0\pmod2$, ce qui est impossible car $2x+1$ est impair. Contradiction, donc pas de solution.
  3. a) $n$ et $p-1$ sont premiers entre eux (car $p$ est le plus petit facteur premier de $n$, donc tous les facteurs premiers de $n$ sont $\ge p$, alors que ceux de $p-1$ sont $<p$, donc $\gcd(n,p-1)=1$). Par Bézout, il existe $(u,v)\in\mathbb Z^2$ tel que $nu+(p-1)v=1$. b) Écrire $u=(p-1)q+r$ avec $0\le r<p-1$, substituer dans $nu+(p-1)v=1$ : $n((p-1)q+r)+(p-1)v=1 \Rightarrow nr = 1-(p-1)(v+nq)$. c) Si $v'=0$ alors $nr=1$, ce qui impose $n=1$, contredisant $n>1$ (ou $r$ tel que ce soit incohérent), donc $v'\ne0$. d) En élevant la congruence…
• NATIONAL 2020 · rattrapage3 pts
  Soient $p$ et $q$ deux nombres premiers vérifiant : $p<q$ et $9^{p+q-1} \equiv 1 \pmod{pq}$ 1-a) Montrer que $p$ et $q$ sont premiers entre eux. b) En déduire que : $9^{p-1} \equiv 1 \pmod{p}$ et que $9^{q-1} \equiv 1 \pmod{q}$ 2-a) Montrer que $p-1$ et $q$ sont premiers entre…
  Voir la correction

  la correction

  1-a) $p$ et $q$ sont des nombres premiers distincts ($p<q$), donc ils sont premiers entre eux. b) Puisque $9^{p+q-1} \equiv 1 \pmod{pq}$, cela implique $9^{p+q-1} \equiv 1 \pmod{p}$ et $9^{p+q-1} \equiv 1 \pmod{q}$. Par le petit théorème de Fermat, $9^{p-1} \equiv 1 \pmod{p}$ (car $p$ est premier et $p \nmid 9$). De même, $9^{q-1} \equiv 1 \pmod{q}$ (car $q$ est premier et $q \nmid 9$). 2-a) Si $p-1$ et $q$ ne sont pas premiers entre eux, alors leur PGCD est $q$ (car $q$ est premier). Donc $q$ divise $p-1$. Or $p<q$, donc $p-1 < q$. Cela est impossible, donc $p-1$ et $q$ sont premiers entre eux. b) On a $9^{p-1} \equiv 1 \pmod{p}$ et $9^{q-1} \equiv 1 \pmod{q}$. De $9^{p+q-1} \equiv 1 \pmod{p}$, on a $9^{p-1} \cdot 9^q \equiv 1 \pmod{p}$. Puisque $9^{p-1} \equiv 1 \pmod{p}$, on a $9^q \equiv 1 \pmod{p}$. De $9^{p+q-1} \equiv 1 \pmod{q}$, on a $9^{q-1} \cdot 9^p \equiv 1 \pmod{q}$. Puisque $9^{q-1} \equiv 1 \pmod{q}$, on a $9^p \equiv 1 \pmod{q}$. On a $9^q \equiv 1 \pmod{p}$ et $9^{p-1} \equiv 1 \pmod{p}$. Donc $\text{ord}_p(9)$ divise $q$ et $p-1$. Puisque $q$ est premier, $\text{ord}_p(9)$ est soit $1$ soit $q$. Si $\text{ord}_p(9)=1$, alors $9 \equiv 1 \pmod{p}$, donc $p$…

  ce que le barème veut ·

  1. Utiliser la définition de nombres premiers entre eux et les propriétés des congruences.
  2. Appliquer le petit théorème de Fermat et les propriétés de l'ordre d'un élément modulo $p$. Utiliser le fait que $p<q$.
  3. Utiliser le petit théorème de Fermat et les congruences pour déduire la valeur de $q$.
• NATIONAL 2019 · normale3 pts
  EXERCICE3: (3 points) On admet que $2969$ (l'année amazighe actuelle) est un nombre premier. Soient $n$ et $m$ deux entiers naturels vérifiant : $n^8 + m^8 = 0 \pmod{2969}$ 1- On suppose dans cette question que $2969$ ne divise pas $n$ a) En utilisant le théorème de BEZOUT,…
  Voir la correction

  la correction

  1.a) Since $2969$ is a prime number and $2969 \nmid n$, it follows that $\text{gcd}(n, 2969) = 1$. By Bezout's theorem, there exist integers $u$ and $v$ such that $un + 2969v = 1$. Reducing this equation modulo $2969$, we get $un \equiv 1 \pmod{2969}$. 1.b) Given $n^8 + m^8 \equiv 0 \pmod{2969}$, we have $n^8 \equiv -m^8 \pmod{2969}$. Multiplying by $u^8$: $(un)^8 \equiv -(um)^8 \pmod{2969}$. Since $un \equiv 1 \pmod{2969}$, we have $(un)^8 \equiv 1^8 \equiv 1 \pmod{2969}$. So, $1 \equiv -(um)^8 \pmod{2969}$, which implies $(um)^8 \equiv -1 \pmod{2969}$. Now, we need to show $(um)^{2968} \equiv -1 \pmod{2969}$. We know $2968 = 8 \times 371$. So $(um)^{2968} = ((um)^8)^{371} \equiv (-1)^{371} \pmod{2969}$. Since $371$ is an odd number, $(-1)^{371} = -1$. Therefore, $(um)^{2968} \equiv -1 \pmod{2969}$. 1.c) Assume $2969$ divides $um$. Then $um \equiv 0 \pmod{2969}$. If $um \equiv 0 \pmod{2969}$, then $(um)^8 \equiv 0^8 \equiv 0 \pmod{2969}$. However, from 1.b), we have $(um)^8 \equiv -1 \pmod{2969}$. So, $0 \equiv -1 \pmod{2969}$, which means $2969$ divides $1$. This is a contradiction. Therefore, $2969$ does not divide $um$. 1.d) Since $2969$ is a prime number and $2969 \nmid um$…

  ce que le barème veut ·

  1.a) Use Bezout's theorem, which states that if $\text{gcd}(a,b)=1$, then there exist integers $x,y$ such that $ax+by=1$. Apply this to $n$ and $2969$. 1.b) Substitute $n^8 \equiv -m^8 \pmod{2969}$ and $un \equiv 1 \pmod{2969}$ into the expression $(um)^8$. Then use the given hint $2968=8 \times 371$ to evaluate $(um)^{2968}$. 1.c) Assume $2969 \mid um$ and show that this leads to a contradiction with the result from 1.b). 1.d) Use Fermat's Little Theorem, which states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod p$. 2.a) Compare the results from 1.b) and 1.d) to derive a contradiction, which will prove that the initial assumption ($2969 \nmid n$) must be false. 2.b) Use the result from 2.a) ($n \equiv 0 \pmod{2969}$) and substitute it into the original congruence $n^8 + m^8 \equiv 0 \pmod{2969}$ to find the congruence for $m$.
• NATIONAL 2018 · normale3 pts
  Exercice 2 Soit $p$ un nombre premier tel que $p = 3 + 4k$ où $k \in \mathbb{N}^*$. 1. Montrer que pour tout entier relatif $x$, si $x^4 \equiv 1 \pmod{p}$ alors $x^{p-5} \equiv 1 \pmod{p}$. 2. Soit $x$ un entier relatif vérifiant $x^{4k+2} \equiv 1 \pmod{p}$. a)…
  Voir la correction

  la correction

  1. On a $p - 5 = 4k + 3 - 5 = 4k - 2 = 2(2k-1)$. Si $x^4 \equiv 1 \pmod{p}$, alors $x^{4n} \equiv 1 \pmod{p}$ pour tout entier $n$. En particulier, $x^{2(2k-1)} = x^{p-5} \equiv 1 \pmod{p}$. 2. a) Puisque $x^{4k+2} \equiv 1 \pmod{p}$, il existe $u \in \mathbb{Z}$ tel que $x^{4k+2} = 1 + up$. Alors $x^{4k+2} - up = 1$, donc par le théorème de Bézout, $\gcd(x,p) = 1$. b) Par le petit théorème de Fermat, puisque $\gcd(x,p) = 1$ et $p$ premier : $x^{p-1} \equiv 1 \pmod{p}$ c) Vérification : $2 + (k-1)(p-1) = 2 + (k-1)(4k+2) = 2 + 4k^2 + 2k - 4k - 2 = 4k^2 - 2k = k(4k-2) = k(p-5)$ d) De $x^{4k+2} \equiv 1 \pmod{p}$ et $2 + (k-1)(p-1) = k(p-5)$, on obtient : $x^{2 + (k-1)(p-1)} \equiv 1 \pmod{p}$ $x^{k(p-5)} \equiv 1 \pmod{p}$ Donc $x^2 \cdot (x^{p-1})^{k-1} \equiv 1 \pmod{p}$. Avec $x^{p-1} \equiv 1 \pmod{p}$, on a $(x^{p-1})^{k-1} \equiv 1 \pmod{p}$, donc $x^2 \equiv 1 \pmod{p}$. Cela donne $(x-1)(x+1) \equiv 0 \pmod{p}$, soit $x \equiv 1 \pmod{p}$ ou $x \equiv -1 \pmod{p}$. En vérifiant les deux cas avec $x^{4k+2} \equiv 1 \pmod{p}$, on conclut $x \equiv 1 \pmod{p}$ ou $x \equiv -1 \pmod{p}$. 3. On a $67 = 3 + 4 \times 16$, donc $67$ est de la forme…

  ce que le barème veut ·

  Étapes clés :

  1. Question 1 : Utiliser $p = 3 + 4k$ pour calculer $p - 5 = 4k - 2 = 2(2k-1)$. Si $x^4 \equiv 1 \pmod{p}$, alors tout multiple pair de 4 ou de $p-5$ donne $x^{p-5} \equiv 1 \pmod{p}$.
  2. Question 2.a : De $x^{4k+2} \equiv 1 \pmod{p}$, exprimer $x^{4k+2} - 1 = up$ pour montrer que $\gcd(x,p) = 1$ par Bézout.
  3. Question 2.b : Appliquer le petit théorème de Fermat directement à $x$ premier avec $p$ premier.
  4. Question 2.c : Développer algébriquement $(k-1)(4k+2) = 4k^2 + 2k - 4k - 2 = 4k^2 - 2k$.
  5. Question 2.d : Utiliser l'égalité $2 + (k-1)(p-1) = k(p-5)$ pour obtenir deux équations exponentielles congruentes, puis déduire $x^2 \equiv 1 \pmod{p}$.
  6. Question 3 : Reconnaître que $67 = 3 + 4(16)$. Appliquer directement le résultat de la question 2 avec $66 = 4(16) + 2$.
• TYPE BAC4 pts
  Résoudre dans $\mathbb{Z}^{2}$ : $7x - 5y = 1$.
  Voir la correction

  la correction

  Solution particulière (3,4) car 21-20=1. pgcd(7,5)=1 donc x=3+5k, y=4+7k, k∈Z.

  ce que le barème veut · Bézout, solution particulière, puis paramétrage par Gauss.