Appliquer le théorème de Gauss

À tenir avant

• Appliquer le théorème de Bézout

Cette méthode au national

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

• 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

  $p\mid r^{q-1}-1$, $q\mid r^{p-1}-1$ (petit théorème de Fermat) ; $pq \mid r^{p+q-2}-1$ ; pour l'équation, ensemble des solutions à déterminer via Fermat avec $p=13$, $q=17$.

  ce que le barème veut ·

  1a) Comme $r$ est premier avec $p$, le petit théorème de Fermat donne $r^{p-1}\equiv1\ [p]$, et de même $r^{q-1}\equiv1\ [q]$ (en échangeant p et q selon l'énoncé exact) : donc $p\mid r^{q-1}-1$ et $q\mid r^{p-1}-1$ par Fermat appliqué respectivement. Attention : en fait on applique Fermat à $p$ avec exposant $p-1$ et à $q$ avec exposant $q-1$; puis on relie via $r^{p+q-2}=r^{p-1}\cdot r^{q-1}$ pour la suite. 1b) Écrire $r^{p+q-2}-1=r^{p-1}(r^{q-1}-1)+(r^{p-1}-1)$, donc $p$ divise cette expression (car $p\mid r^{p-1}-1$ et on montre aussi $p\mid r^{q-1}-1$ par un argument similaire d'échange), de même pour $q$; ainsi $p$ et $q$ divisent tous deux $r^{p+q-2}-1$. 1c) Puisque $p$ et $q$ sont premiers entre eux (nombres premiers distincts) et divisent tous deux $r^{p+q-2}-1$, leur produit $pq$ divise aussi $r^{p+q-2}-1$ (lemme de Gauss / PPCM de deux nombres premiers entre eux). 2) Utiliser $p=13,q=17$, donc $p+q-2=28$. Comme $2024$ est premier avec $221=13\times17$ (à vérifier), on a d'après 1c) que $221\mid 2024^{28}-1$, donc $2024^{28}\equiv1\ [221]$. L'ordre de $2024$ modulo $221$ divise $28$. On réduit l'exposant $172x \mod 28$ (ou mod l'ordre) pour ramener à une puissance…
• NATIONAL 2023 · normale3 pts
  EXERCICE4 :(3 points) Soit $p$ un nombre premier impair. On considère dans $\mathbb Z$ l'équation $(E): x^{2}\equiv2[p]$ 1- a) Montrer que : $2^{p-1}\equiv1 [p]$ b) En déduire que : $2^{\frac{p-1}{2}}\equiv1[p]$ ou $2^{\frac{p-1}{2}}\equiv-1[p]$ (On remarque que :…
  Voir la correction

  la correction

  1- a) $2^{p-1}\equiv1 [p]$ (Petit théorème de Fermat, car $p$ est un nombre premier impair, donc $p \nmid 2$). b) Puisque $2^{p-1}-1 = (2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)$, et $2^{p-1}\equiv1 [p]$, alors $(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)\equiv0 [p]$. Comme $p$ est premier, cela implique $2^{\frac{p-1}{2}}-1\equiv0 [p]$ ou $2^{\frac{p-1}{2}}+1\equiv0 [p]$, d'où $2^{\frac{p-1}{2}}\equiv1[p]$ ou $2^{\frac{p-1}{2}}\equiv-1[p]$. 2- a) Supposons que $p$ et $x$ ne sont pas premiers entre eux. Puisque $p$ est premier, cela signifie $p|x$. Si $p|x$, alors $x \equiv 0 [p]$. L'équation $(E)$ devient $0^2 \equiv 2 [p]$, soit $2 \equiv 0 [p]$. Cela signifie $p|2$. Comme $p$ est un nombre premier impair, $p$ ne peut pas être 2. Donc $p$ et $x$ sont premiers entre eux. b) Si $x$ est une solution de $(E)$, alors $x^2 \equiv 2 [p]$. Puisque $p$ et $x$ sont premiers entre eux (d'après 2a), on peut appliquer le Petit Théorème de Fermat à $x$: $x^{p-1} \equiv 1 [p]$. On a $x^{p-1} = (x^2)^{\frac{p-1}{2}} \equiv 2^{\frac{p-1}{2}} [p]$. Donc $2^{\frac{p-1}{2}} \equiv 1 [p]$. 3- Pour tout $k\in\{1,2,...,p-1\}$, on a $kC_p^k = pC_{p-1}^{k-1}$. Puisque $C_{p-1}^{k-1}$ est un entier, $p$…

  ce que le barème veut ·

  1. Apply Fermat's Little Theorem. 2. Use the property of prime numbers and the result from 1b. 3. Use the identity $kC_p^k = pC_{p-1}^{k-1}$ and Gauss's Lemma. 4. Use De Moivre's formula and the binomial expansion modulo $p$. 5. Combine results from 2b and 4b, and analyze the congruence $p\equiv5[8]$.
• NATIONAL 2011 · normale2 pts
  Exercice 2 – Arithmétique Soit $N$ l'entier naturel dont l'écriture en base 10 est : $N = \underbrace{11\ldots11}_{2010 \text{ fois}}$ (repunit de 2010 chiffres 1).

  1. Montrer que le nombre $N$ est divisible par 11.
  2. a) Vérifier que le nombre 2011 est premier et que…
  Voir la correction

  la correction

  1. $N = \underbrace{11\ldots11}_{2010} = \frac{10^{2010} - 1}{9}$. Comme 2010 est pair, $10^{2010} \equiv 1 \pmod{11}$ (car $10 \equiv -1 \pmod{11}$), donc $10^{2010} - 1 \equiv 0 \pmod{11}$. Puisque $\gcd(9, 11) = 1$, on a $N \equiv 0 \pmod{11}$.
  2. a) 2011 est premier : vérification par test de divisibilité. $10^{2010} - 1 = 9 \times \underbrace{1111\ldots1}_{2010}= 9N$. b) Par le petit théorème de Fermat, puisque 2011 est premier et $\gcd(10, 2011) = 1$ : $10^{2010} \equiv 1 \pmod{2011}$, donc $2011 \mid 10^{2010} - 1$. c) On a $9N = 10^{2010} - 1$. Puisque $2011 \mid 10^{2010} - 1$ et $\gcd(9, 2011) = 1$, par le lemme de Gauss : $2011 \mid N$.
  3. On a montré : $11 \mid N$ et $2011 \mid N$. Puisque $\gcd(11, 2011) = 1$ (tous deux premiers), on a $11 \times 2011 = 22121 \mid N$.

  ce que le barème veut ·

  Divisibilité par 11 : $N = 1 + 10 + 10^2 + \cdots + 10^{2009} = \frac{10^{2010} - 1}{10 - 1}$. Modulo 11 : $10 \equiv -1 \pmod{11}$, donc $10^{2010} \equiv (-1)^{2010} = 1 \pmod{11}$, ainsi $10^{2010} - 1 \equiv 0 \pmod{11}$. Comme $9 \equiv -2 \pmod{11}$ et $\gcd(9, 11) = 1$, on déduit $N \equiv 0 \pmod{11}$. Divisibilité par 2011 : Par le petit théorème de Fermat : $10^{2010} \equiv 1 \pmod{2011}$ (ordre de 10 divise $\phi(2011) = 2010$). Donc $9N = 10^{2010} - 1 \equiv 0 \pmod{2011}$. Puisque $\gcd(9, 2011) = 1$, par Gauss : $2011 \mid N$. Divisibilité par 22121 : $11$ et $2011$ sont premiers distincts, donc $\gcd(11, 2011) = 1$. Par le théorème chinois : $11 \mid N$ et $2011 \mid N$ impliquent $11 \times 2011 = 22121 \mid N$.
• 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.