Calculer un PGCD par l'algorithme d'Euclide

À tenir avant

• Poser une division euclidienne

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 2024 · normale3 pts
  Soient $p$ et $q$ deux nombres premiers distincts et $r$ un entier naturel premier avec $p$ et avec $q$.

  1. a) Montrer que $p$ divise $r^{q-1}-1$ et que $q$ divise $r^{p-1}-1$. b) En déduire que $p$ et $q$ divisent $r^{p+q-2}-1$. c) Montrer que $pq$ divise $r^{p+q-2}-1$.

  2)…
  Voir la correction

  la correction

  1. $p\mid r^{q-1}-1$, $q\mid r^{p-1}-1$, puis $p\mid r^{p+q-2}-1$ et $q\mid r^{p+q-2}-1$, donc $pq\mid r^{p+q-2}-1$ (car $p,q$ premiers distincts, donc premiers entre eux).
  2. L'ensemble des solutions est $x\equiv x_0 \pmod{221}$ pour une certaine valeur $x_0$ déterminée par le petit théorème de Fermat (avec $p=13,q=17$, $p+q-2=28$, donc $2024^{28}\equiv1\pmod{221}$, et $172=6\times28+4$ donc $2024^{172}\equiv2024^4\pmod{221}$; il faut résoudre $2024^4 x\equiv3\pmod{221}$ en trouvant l'inverse de $2024^4$ modulo 221).

  ce que le barème veut ·

  1a) $r$ premier avec $p$, donc par le petit théorème de Fermat $r^{p-1}\equiv1\pmod p$; de même $r^{q-1}\equiv1\pmod q$ car $r$ premier avec $q$. Donc $p\mid r^{p-1}-1$ et $q\mid r^{q-1}-1$ (attention à l'énoncé : $p\mid r^{q-1}-1$? En réalité on utilise Fermat pour chaque nombre premier séparément : $q\mid r^{q-1}-1$ et $p\mid r^{p-1}-1$; on montre alors que ces deux résultats impliquent la divisibilité de $r^{p+q-2}-1$ par $p$ et par $q$). 1b) Écrire $r^{p+q-2}-1=r^{q-1}\cdot r^{p-1}-1$; utiliser que $r^{p-1}\equiv1\pmod p$ donc $r^{p+q-2}=r^{q-1}\cdot r^{p-1}\equiv r^{q-1}\pmod p$; or il faut aussi que $r^{q-1}\equiv1\pmod p$ (ce qui se déduit du petit théorème de Fermat appliqué modulo $p$ à un exposant multiple de $p-1$, ou directement par un argument d'ordre) : ainsi $p\mid r^{p+q-2}-1$; symétriquement $q\mid r^{p+q-2}-1$. 1c) Comme $p$ et $q$ sont premiers distincts, ils sont premiers entre eux, donc par le théorème de Gauss $pq\mid r^{p+q-2}-1$. 2) Utiliser $221=13\times17$, calculer $p+q-2=13+17-2=28$; comme $2024$ est premier avec 13 et 17 (à vérifier), on a $2024^{28}\equiv1\pmod{221}$ d'après la question 1 (avec $r=2024$); réduire l'exposant $172$ modulo $28$ :…
• NATIONAL 2021 · rattrapage3 pts
  Soit $a$ un entier naturel supérieur ou égal à $2$ et soit $A=1+a+a^2+a^3+a^4+a^5+a^6$ Soit $p$ un nombre premier impair tel que : $p$ divise $A$

  1. a) Montrer que $a^7 \equiv 1 \pmod{p}$, en déduire que $\forall n\in\mathbb{N}$ ; $a^n \equiv 1 \pmod{p}$ 1 b) Montrer que $a$ et…
  Voir la correction

  la correction

  1. a) On a $A = 1+a+a^2+a^3+a^4+a^5+a^6$. C'est la somme des 7 premiers termes d'une suite géométrique de raison $a$. Donc $A = \frac{a^7-1}{a-1}$. Puisque $p$ divise $A$, on a $A \equiv 0 \pmod{p}$. Donc $\frac{a^7-1}{a-1} \equiv 0 \pmod{p}$. Cela implique $a^7-1 \equiv 0 \pmod{p}$ si $a-1 \not\equiv 0 \pmod{p}$. Si $a-1 \equiv 0 \pmod{p}$, alors $a \equiv 1 \pmod{p}$. Dans ce cas, $A = 1+1+\dots+1 = 7 \pmod{p}$. Si $p|A$, alors $p|7$, donc $p=7$. Si $a \equiv 1 \pmod{p}$, alors $a^n \equiv 1^n \equiv 1 \pmod{p}$ pour tout $n \in \mathbb{N}$. Si $a-1 \not\equiv 0 \pmod{p}$, alors $a^7-1 \equiv 0 \pmod{p}$, ce qui signifie $a^7 \equiv 1 \pmod{p}$. L'énoncé demande d'en déduire que $\forall n \in \mathbb{N}$, $a^n \equiv 1 \pmod{p}$. Ceci est une erreur dans l'énoncé, car $a^n \equiv 1 \pmod{p}$ n'est vrai que si $n$ est un multiple de l'ordre de $a$ modulo $p$, ou si $a \equiv 1 \pmod{p}$. La déduction correcte est $a^7 \equiv 1 \pmod{p}$. b) Supposons que $a$ et $p$ ne sont pas premiers entre eux. Puisque $p$ est premier, cela signifie que $p$ divise $a$. Si $p|a$, alors $a \equiv 0 \pmod{p}$. De $A = 1+a+a^2+a^3+a^4+a^5+a^6$ et $p|A$, on aurait $1+0+0+0+0+0+0 \equiv 0 \pmod{p}$,…

  ce que le barème veut ·

  1. a) Utiliser la formule de la somme d'une suite géométrique pour exprimer $A$. Utiliser la condition $p|A$ pour déduire $a^7 \equiv 1 \pmod{p}$ (en considérant le cas $a \equiv 1 \pmod{p}$ séparément). b) Supposer par contradiction que $a$ et $p$ ne sont pas premiers entre eux. Utiliser le petit théorème de Fermat pour déduire $a^{p-1} \equiv 1 \pmod{p}$ et ensuite $a^{(p-1)m} \equiv 1 \pmod{p}$.
  2. a) Utiliser les résultats de 1.a) et 1.b) ($a^7 \equiv 1 \pmod{p}$ et $a^{p-1} \equiv 1 \pmod{p}$). Utiliser la propriété que si $a^x \equiv 1 \pmod{p}$ et $a^y \equiv 1 \pmod{p}$, alors $a^{\text{pgcd}(x,y)} \equiv 1 \pmod{p}$. Utiliser la condition que $7$ ne divise pas $p-1$. b) Utiliser le résultat de 2.a) ($a \equiv 1 \pmod{p}$) et la définition de $A$ pour montrer que $A \equiv 7 \pmod{p}$. Puisque $p|A$, déduire $p=7$.
  3. Utiliser les résultats $a^7 \equiv 1 \pmod{p}$ et $a^{p-1} \equiv 1 \pmod{p}$. Soit $k$ l'ordre de $a$ modulo $p$. $k$ doit diviser $7$ et $p-1$. Analyser les deux cas possibles pour $k$ (1 ou 7) et en déduire les conditions sur $p$.
• NATIONAL 2020 · normale3 pts
  On considère dans $\mathbb{Z}\times\mathbb{Z}$ l'équation $(D) : 7x - 13y = 5$ 1- Soit $(x, y)\in \mathbb{Z}\times\mathbb{Z}$ une solution de l'équation $(D)$ a) Montrer que $x$ et $13$ sont premiers entre eux. b) En déduire que : $x^{12} \equiv 1 \pmod{13}$ c) Montrer que :…
  Voir la correction

  la correction

  1- a) Soit $d = \text{pgcd}(x, 13)$. Puisque $d|x$ et $d|13$, et que $13$ est un nombre premier, alors $d=1$ ou $d=13$. De l'équation $(D)$, on a $7x - 13y = 5$. Si $d=13$, alors $13|7x$ et $13|13y$, donc $13|(7x-13y)$, ce qui signifie $13|5$. Ceci est absurde. Par conséquent, $d=1$, donc $x$ et $13$ sont premiers entre eux. b) Puisque $13$ est un nombre premier et $x$ n'est pas un multiple de $13$ (car $\text{pgcd}(x, 13)=1$), d'après le petit théorème de Fermat, on a $x^{13-1} \equiv x^{12} \equiv 1 \pmod{13}$. c) De l'équation $(D)$, on a $7x - 13y = 5$, ce qui implique $7x \equiv 5 \pmod{13}$. Pour trouver $x \pmod{13}$, on peut multiplier par l'inverse de $7 \pmod{13}$. On a $7 \times 2 = 14 \equiv 1 \pmod{13}$, donc $2$ est l'inverse de $7 \pmod{13}$. $2 \times 7x \equiv 2 \times 5 \pmod{13} \implies 14x \equiv 10 \pmod{13} \implies x \equiv 10 \pmod{13}$. Alors $x^{60} \equiv 10^{60} \pmod{13}$. On sait que $10 \equiv -3 \pmod{13}$. Donc $10^{60} \equiv (-3)^{60} \pmod{13}$. $(-3)^{60} = ((-3)^{12})^5 \pmod{13}$. D'après la question 1.b), $x^{12} \equiv 1 \pmod{13}$. Puisque $x \equiv 10 \pmod{13}$, on a $10^{12} \equiv 1 \pmod{13}$. Donc…

  ce que le barème veut ·

  1.a) Utiliser la définition du pgcd et la propriété des nombres premiers. 1.b) Appliquer le petit théorème de Fermat. 1.c) Résoudre la congruence $7x \equiv 5 \pmod{13}$ pour trouver $x \pmod{13}$, puis élever à la puissance $60$ en utilisant le résultat de 1.b). 1.d) Élever le résultat de 1.c) au carré. 2) Comparer les résultats obtenus pour $x^{120}$ à partir de 1.b) et 1.d) pour montrer une contradiction.
• NATIONAL 2012 · normale3 pts
  1. On considère dans $\mathbb{Z}^2$ l'équation $(E) : 143x - 195y = 52$. a) Déterminer le plus grand commun diviseur de 143 et 195, puis en déduire que l'équation $(E)$ admet des solutions dans $\mathbb{Z}^2$. b) Sachant que $(-1, -1)$ est une solution particulière de…
  Voir la correction

  la correction

  1. a) $\gcd(143, 195) = \gcd(143, 52) = \gcd(39, 52) = \gcd(39, 13) = 13$. Puisque $13 \mid 52$, l'équation admet des solutions. b) Résolution générale : $(x, y) = (-1 + 15k, -1 + 11k)$ pour $k \in \mathbb{Z}$ (où $\gcd(143, 195) = 13$, et $\frac{143}{13} = 11$, $\frac{195}{13} = 15$).
  2. Par le petit théorème de Fermat, si $\gcd(n, 5) = 1$, alors $n^4 \equiv 1 \pmod{5}$ (l'ordre de $n$ divise $\phi(5) = 4$).
  3. a) Si $x \equiv y \pmod{4}$ et $\gcd(2, 5) = 1$, alors $2^x \equiv 2^y \pmod{5}$ (la relation de congruence dans l'exposant découle de $2^4 \equiv 1 \pmod{5}$). b) Utiliser la congruence pour $n \equiv 0, 1, 2, 3, 4 \pmod{5}$ et $n \equiv 0, 1 \pmod{2}$ séparément par le théorème chinois : $n^x \equiv n^y \pmod{10}$.
  4. Si $(x, y)$ satisfait $(E) : 143x - 195y = 52$, alors $143x \equiv 195y + 52 \pmod{10}$, soit $3x \equiv 5y + 2 \pmod{10}$. Montrer que $x \equiv y \pmod{4}$ modulo des calculs spécifiques, d'où $n^x \equiv n^y \pmod{10}$.

  ce que le barème veut ·

  1. a) Utiliser l'algorithme d'Euclide : $\gcd(195, 143) = \gcd(143, 52) = \gcd(52, 39) = \gcd(39, 13) = \gcd(13, 0) = 13$. Vérifier que $13 \mid 52$ (oui, $52 = 4 \times 13$). b) La solution générale d'une équation diophantienne $ax + by = c$ est : si $(x_0, y_0)$ est une solution particulière et $\gcd(a, b) = d$, alors $(x, y) = (x_0 + \frac{b}{d}t, y_0 + \frac{a}{d}t)$ pour $t \in \mathbb{Z}$. Ici : $(x, y) = (-1 + 15k, -1 + 11k)$.
  2. Le petit théorème de Fermat stipule que si $p$ est premier et $\gcd(n, p) = 1$, alors $n^{p-1} \equiv 1 \pmod{p}$. Appliquer avec $p = 5$ : $n^4 \equiv 1 \pmod{5}$.
  3. a) Si $x \equiv y \pmod{4}$, alors $2^x \equiv 2^y \pmod{5}$ car $2^4 \equiv 1 \pmod{5}$ (l'exposant modulo 4 suffit). b) Utiliser le théorème des restes chinois : $n^x \equiv n^y \pmod{2}$ (trivial pour $n$ pair/impair) et $n^x \equiv n^y \pmod{5}$ (par 2a si $\gcd(n,5)=1$, ou trivial sinon). Donc $n^x \equiv n^y \pmod{10}$.
  4. Vérifier que si $(x, y) = (-1 + 15k, -1 + 11k)$, alors $x - y = 4(k-1) \equiv 0 \pmod{4}$. Appliquer 3b : $n^x \equiv n^y \pmod{10}$ pour tous $n \in \mathbb{N}^*$.
• NATIONAL 2011 · rattrapage2 pts
  Deuxième exercice :(2.5points) Soit x un nombre entier_naturel tel que :10* =2 [19] 0.25 1- a) vérifier que : 10*+1 =1 [19] 0.5 b) Montrer que : 1018 =1 [19] 2- Soit d le plus grand diviseur commun des deux nombres 18 et x+1 a) Montrer que : 10º =1 [19] 0.75 0.5 b) Montrer que: d…Voir la correction

  la correction

  1.a) On a $10^x \equiv 2 \pmod{19}$. On veut vérifier $10^{x+1} \equiv 1 \pmod{19}$. $10^{x+1} = 10^x \times 10^1 \equiv 2 \times 10 \pmod{19}$. $10^{x+1} \equiv 20 \pmod{19}$. $20 \equiv 1 \pmod{19}$. Donc $10^{x+1} \equiv 1 \pmod{19}$. 1.b) Montrons que $10^{18} \equiv 1 \pmod{19}$. 19 est un nombre premier. 10 n'est pas un multiple de 19. D'après le petit théorème de Fermat, si $p$ est un nombre premier et $a$ n'est pas un multiple de $p$, alors $a^{p-1} \equiv 1 \pmod{p}$. Ici, $p=19$ et $a=10$. Donc $10^{19-1} \equiv 10^{18} \equiv 1 \pmod{19}$.

  2. Soit $d = \gcd(18, x+1)$. 2.a) Montrons que $10^d \equiv 1 \pmod{19}$. On sait que $10^{x+1} \equiv 1 \pmod{19}$ (d'après 1.a)). On sait aussi que $10^{18} \equiv 1 \pmod{19}$ (d'après 1.b)). Soit $k = \text{ord}_{19}(10)$ l'ordre de 10 modulo 19. Par définition, $k$ est le plus petit entier positif tel que $10^k \equiv 1 \pmod{19}$. Puisque $10^{x+1} \equiv 1 \pmod{19}$, $k$ divise $x+1$. Puisque $10^{18} \equiv 1 \pmod{19}$, $k$ divise $18$. Donc $k$ est un diviseur commun de $x+1$ et $18$. Par conséquent, $k$ divise $d = \gcd(18, x+1)$. Si $k$ divise $d$, alors $d = mk$ pour un certain entier $m \ge 1$. Alors…

  ce que le barème veut ·

  1.a) Utiliser la propriété des congruences $a \equiv b \pmod n \implies ac \equiv bc \pmod n$. 1.b) Appliquer le petit théorème de Fermat. 2.a) Utiliser la propriété que si $a^k \equiv 1 \pmod n$ et $a^m \equiv 1 \pmod n$, alors $a^{\gcd(k,m)} \equiv 1 \pmod n$. 2.b) Calculer les puissances successives de 10 modulo 19 pour trouver l'ordre de 10 modulo 19, et en déduire $d$. 2.c) Utiliser la définition du PGCD pour déduire la relation de congruence pour $x$.