Calculer avec des congruences

À tenir avant

• Poser une division euclidienne

Cette méthode au national

8 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 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 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 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 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 2021 · rattrapage4 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 = \frac{a^7 - 1}{a - 1}$ Soit $p$ un nombre premier impair tel que : $p \mid A$.

  1. a) Montrer que $a^7 \equiv 1 \pmod{p}$, en déduire que pour tout $k \in \mathbb{N}$ :…
  Voir la correction

  la correction

  1. a) Si $p \mid A$ et $A = 1 + a + a^2 + \cdots + a^6$, alors : $a^7 - 1 = (a-1)A \equiv 0 \pmod{p}$ Puisque $\gcd(a-1, p)$ peut être traité : si $p \mid (a-1)$ alors $a \equiv 1 \pmod{p}$ et $a^7 \equiv 1 \pmod{p}$. Sinon, $p \mid (a^7-1)$, donc $a^7 \equiv 1 \pmod{p}$. Par récurrence : $a^{7k} \equiv 1 \pmod{p}$ pour tout $k \in \mathbb{N}$. b) Si $p \mid (a^7 - 1)$ et $p$ est premier, alors $p \nmid a$ (sinon $p \mid 1$, absurde). Donc $\gcd(a,p) = 1$. Par le petit théorème de Fermat, l'ordre de $a$ modulo $p$ divise $p-1$. On a $a^m \equiv 1 \pmod{p}$ ssi l'ordre divise $m$. 2. a) L'ordre $d$ de $a$ modulo $p$ divise $7$ (car $a^7 \equiv 1 \pmod{p}$). Donc $d \in \{1, 7\}$. Si $7 \nmid (p-1)$, alors $7$ ne divise pas l'ordre maximal possible (qui est $p-1$), donc $d = 1$, i.e., $a \equiv 1 \pmod{p}$. b) Si $a \equiv 1 \pmod{p}$, alors $A = 1 + 1 + \cdots + 1 = 7 \pmod{p}$. Donc $p \mid 7$, ce qui implique $p = 7$ (puisque $p$ est premier impair). 3. Si $p \mid A$ et $p$ est premier impair, alors :

  • Cas 1 : $7 \mid (p-1)$, donc $p \equiv 1 \pmod{7}$.
  • Cas 2 : $7 \nmid (p-1)$, donc $p = 7$ (par la question 2).

  Conclusion : $p = 7$ ou…

  ce que le barème veut ·

  Divisibilité et congruence : À partir de $p \mid A$ avec $A(a-1) = a^7 - 1$, on déduit $a^7 \equiv 1 \pmod{p}$. Ordre multiplicatif : L'ordre de $a$ modulo $p$ est le plus petit entier positif $d$ tel que $a^d \equiv 1 \pmod{p}$. Cet ordre divise $\phi(p) = p-1$ par le théorème de Fermat. Cas 1 : $7 \mid (p-1)$ : L'ordre de $a$ peut être $7$, ce qui est compatible avec $a^7 \equiv 1 \pmod{p}$ mais $a \not\equiv 1 \pmod{p}$. Donc $p \equiv 1 \pmod{7}$ est possible. Cas 2 : $7 \nmid (p-1)$ : L'ordre de $a$ doit diviser $\gcd(7, p-1)$. Puisque $7 \nmid (p-1)$, on a $\gcd(7, p-1) = 1$, donc l'ordre est $1$. Cela signifie $a \equiv 1 \pmod{p}$, d'où $p \mid 7$, donc $p = 7$. Conclusion : Par le théorème de l'ordre (Lagrange), les seuls premiers divisant $A$ sont $7$ et ceux pour lesquels $7 \mid (p-1)$, i.e., $p \equiv 1 \pmod{7}$.
• 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$.