Introduction à la théorie des nombres/Exercices/Résidus quadratiques

Exercice 4-1

Soient un nombre premier $p>2$ et $a,b,c$ trois entiers, avec $a$ et $b$ non divisibles par $p$. Montrer qu'il existe des entiers $x,y$ tels que $ax^{2}+by^{2}\equiv c{\bmod {p}}$. (Indication : combien y a-t-il de carrés dans $\mathbb {Z} /p\mathbb {Z}$ ?)

Solution

Dans $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$, il y a $\left(p-1\right)/2$ carrés ($x^{2}=(-x)^{2},x\neq -x$) donc dans $\mathbb {Z} /p\mathbb {Z}$, il y en a $\left(p+1\right)/2$. Il y a donc $\left(p+1\right)/2$ éléments de la forme $ax^{2}$ et autant de la forme $c-by^{2}$. Ces deux parties de $\mathbb {Z} /p\mathbb {Z}$ sont donc non disjointes.

 

Exercice 4-2

Soient $p$ un nombre premier congru à $3$ modulo $4$ et $a$ un carré dans $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$. Exprimer en fonction de $a$ et $p$ les deux racines carrées de $a$.

Solution

$a^{\left(p-1\right)/2}=1$ donc $a^{\left(p+1\right)/2}=a$ donc les deux racines carrées de $a$ sont $\pm a^{\left(p+1\right)/4}$.

 

Exercice 4-3

Que donne le lemme de Gauss pour $a=-1$ ?

Solution

Le critère d'Euler pour $a=-1$.

 

Exercice 4-4

Soit $p$ un nombre premier congru à $1$ modulo $4$. Montrer que la somme des entiers compris entre $1$ et $p-1$ qui sont des carrés ${\bmod {p}}$ est égale à $p\left(p-1\right)/4$. (Indication : $a+\left(p-a\right)=p$.)

Solution

$-1$ est un carré ${\bmod {p}}$ donc si $a$ fait partie de ces entiers, $p-a$ aussi. Leur moyenne vaut donc $p/2$. Or il y en a $\left(p-1\right)/2$.

 

Exercice 4-5

Soit un nombre premier $p>2$.

1. Démontrer le théorème de Wilson : $\left(p-1\right)!\equiv -1{\bmod {p}}$.
2. En déduire que le produit des carrés non nuls de $\mathbb {Z} /p\mathbb {Z}$ est égal à $(-1)^{\left(p+1\right)/2}{\pmod {p}}$. (Indication : $k\left(p-k\right)\equiv -k^{2}$.)

Solution

1. En regroupant, dans le produit des $p-1$ éléments de $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$, chaque produit d'un élément par son inverse, à l'exception des éléments $1$ et $-1$ qui sont chacun leur propre inverse, on obtient : $\left(p-1\right)!\equiv 1^{\left(p-3\right)/2}\times 1\times -1{\bmod {p}}$. (Remarque : pour $p=2$, on a aussi, évidemment $\left(p-1\right)!\equiv -1{\bmod {p}}$.)
2. Modulo $p$, le produit des carrés non nuls de $\mathbb {Z} /p\mathbb {Z}$ est congru à $\prod _{1\leq k<p/2}k^{2}\equiv (-1)^{\left(p-1\right)/2}\prod _{1\leq k<p/2}-k^{2}\equiv (-1)^{\left(p-1\right)/2}\prod _{1\leq k<p/2}k\left(p-k\right)=(-1)^{\left(p-1\right)/2}\left(p-1\right)!\equiv (-1)^{\left(p+1\right)/2}$.

 

Exercice 4-6

Soient $p=1+mn$ un nombre premier et $a$ un entier non divisible par $p$.

1. Montrer que $a$ est une puissance $n$-ième ${\bmod {p}}$ si (et seulement si) $a^{m}\equiv 1{\bmod {p}}$.
2. Pour $n=2$ (donc $p\neq 2$), en déduire le « critère d'Euler » usuel : $a^{\left(p-1\right)/2}\equiv \left({\frac {a}{p}}\right){\bmod {p}}$.

Solution

1. Modulo $p$, si $a\equiv b^{n}$ alors $a^{m}\equiv b^{mn}=b^{p-1}\equiv 1$, d'après le petit théorème de Fermat.
   Réciproquement, supposons que $a^{m}\equiv 1{\bmod {p}}$ et considérons le polynôme à coefficients dans $\mathbb {Z} /p\mathbb {Z}$
   $X^{mn}-1=\left(X^{n}-{\bar {a}}\right)\left(X^{(m-1)n}+X^{(m-2)n}{\bar {a}}+\dots X^{n}a^{m-2}+{\bar {a}}^{m-1}\right)$,
   où ${\bar {a}}$ désigne la classe de $a{\bmod {p}}$. À nouveau d'après le petit théorème de Fermat, les $mn$ éléments non nuls de $\mathbb {Z} /p\mathbb {Z}$ sont racines de ce polynôme mais, pour des raisons de degré, au plus $\left(m-1\right)n$ d'entre elles sont racines du facteur de droite. Celles qui restent sont donc racines de $X^{n}-{\bar {a}}$. Si ${\bar {b}}$ est l'une d'entre elles, $a\equiv b^{n}{\bmod {p}}$.
2. Pour tout entier $r$, si $r^{2}\equiv 1{\bmod {p}}$ alors $r\equiv \pm 1{\bmod {p}}$. Appliquée à $r=a^{\left(p-1\right)/2}$ (pour $p\neq 2$), cette remarque complète le critère dans le cas $n=2$ : si $a$ n'est pas un carré ${\bmod {p}}$, non seulement $r$ n'est pas congru à $1$, mais il est congru à $-1$.

 

Exercice 4-7

1. Montrer que pour tout nombre premier $p\equiv 3{\bmod {4}}$, si $p':=2p+1$ est premier alors $2^{p}\equiv 1{\bmod {p}}'$.
2. Application : montrer que le nombre de Mersenne $2^{251}-1$ n'est pas premier.

Solution

1. $p'\equiv -1{\bmod {8}}$ donc $1=\left({\frac {2}{p'}}\right)\equiv 2^{(p'-1)/2}{\bmod {p'}}$, et $\left(p'-1\right)/2=p$.
2. $p=251=4\times 62+3$ est premier car ${\sqrt {251}}<16$ et $251$ n'est pas divisible par $2,3,5,7,11,13$). $p'=2p+1=503$ est premier aussi (${\sqrt {503}}<23$), et diviseur strict de $2^{251}-1$.

 

Exercice 4-8

Soient $p$ un nombre premier impair et $\varepsilon :={\begin{cases}~~1{\text{ si }}p\equiv \pm 1{\bmod {8}}\\-1{\text{ si }}p\equiv \pm 3{\bmod {8}}.\end{cases}}$

On se propose de redémontrer que $\left({\frac {2}{p}}\right)=\varepsilon$, par une méthode voisine (en plus simple) de celle vue en cours pour le théorème fondamental.

On considère pour cela, dans l'anneau ${\rm {F}}_{p}[\zeta ]:={\rm {F}}_{p}[X]/\left(X^{4}+1\right)$ (non intègre car $X^{4}+1=\Phi _{8}(X)$, le 8^e polynôme cyclotomique, n'est pas irréductible sur $\mathrm {F} _{p}$), l'élément $\tau :=\zeta +\zeta ^{-1}$. Démontrer que :

1. $\tau ^{2}=2$ ;
2. $\left({\frac {2}{p}}\right)=\tau ^{p-1}$ ;
3. $\tau$ est inversible ;
4. $\tau ^{p}=\varepsilon \tau$ (indication : remarquer que $\tau ^{p}=\zeta ^{p}+\zeta ^{-p}$).
5. Conclure.

Solution

Adaptée de Kenneth Ireland et Michael Rosen, A Classical Introduction to Modern Number Theory, 1990, 2^e éd. [lire en ligne], p. 69-70 .

1. $\zeta ^{4}=-1$ donc $\zeta ^{-2}=-\zeta ^{2}$ donc $\tau ^{2}=(\zeta +\zeta ^{-1})^{2}=2$ ;
2. donc (dans ${\rm {F}}_{p}[\zeta ]$) $\left({\frac {2}{p}}\right)=2^{\left(p-1\right)/2}=\tau ^{p-1}$ ;
3. donc $\tau ^{-1}=\pm \tau ^{p-2}$.
4. $\tau ^{p}=(\zeta +\zeta ^{-1})^{p}=\zeta ^{p}+\zeta ^{-p}$ (car les autres coefficients binomiaux sont nuls dans ${\rm {F}}_{p}$). Soit $r\in \{\pm 1,\pm 3\}$ tel que $p=8k+r$ ; on a donc $\zeta ^{p}=\zeta ^{r}$ (car $\zeta ^{8}=1$). Si $r=\pm 1$, $\zeta ^{p}+\zeta ^{-p}=\tau$ tandis que si $r=\pm 3$, $\zeta ^{p}+\zeta ^{-p}=\zeta ^{3}+\zeta ^{-3}=-\zeta ^{-1}-\zeta =-\tau$. Dans les deux cas, $\zeta ^{p}+\zeta ^{-p}=\varepsilon \tau$.
5. D'après les questions 4 et 3, $\tau ^{p-1}=\varepsilon$ donc d'après la question 2, $\left({\frac {2}{p}}\right)=\varepsilon$.

 

Exercice 4-9

Le but de cet exercice est de déterminer les carrés modulo les puissances d'un nombre premier impair.

1. Soient $P$ un polynôme à coefficients entiers, $p$ un nombre premier, $k$ un entier positif et $r\in \mathbb {Z}$ tel que $P\left(r\right)\equiv 0{\bmod {p^{k}}}$ et $P'\left(r\right)\not \equiv 0{\bmod {p}}$.
   Montrer qu'il existe un entier $s\equiv r{\bmod {p^{k}}}$ tel que $P\left(s\right)\equiv 0{\bmod {p^{2k}}}$.
2. En déduire que si $p$ est impair, tout entier non divisible par $p$ qui est un carré ${\bmod {p}}$ est aussi un carré ${\bmod {p^{m}}}$ pour tout $m\in \mathbb {N} ^{*}$.
3. Ce n'est pas aussi simple si $p=2$ : trouver un entier impair qui est un carré ${\bmod {2}}$ mais pas ${\bmod {4}}$, et un entier impair qui est un carré ${\bmod {4}}$ mais pas ${\bmod {8}}$.

Solution

1. (C'est un cas particulier du lemme de Hensel.) On cherche $s$ sous la forme $r+p^{k}t$. Si $P=\sum a_{n}X^{n}$, $P\left(s\right)\equiv \sum a_{n}(r^{n}+nr^{n-1}p^{k}t)=P\left(r\right)+P'\left(r\right)p^{k}t{\bmod {p^{2k}}}$. Par hypothèse, $P\left(r\right)=bp^{k}$, donc on cherche $t$ tel que $b+P'\left(r\right)t\equiv 0{\bmod {p^{k}}}$. Un tel $t$ existe (et est unique ${\bmod {p^{k}}}$) car $P'\left(r\right)$ est inversible ${\bmod {p^{k}}}$.
2. Si $a\equiv r^{2}{\bmod {p}}$ (avec $p$ impair et $a$ non divisible par $p$), $P\left(r\right)\equiv 0{\bmod {p}}$ pour $P\left(X\right)=X^{2}-a$, et $P'\left(r\right)=2r\not \equiv 0{\bmod {p}}$.
3. Tout entier est un carré ${\bmod {2}}$, mais les carrés ${\bmod {4}}$ sont seulement $0$ et $1$ ${\pmod {4}}$. Et les carrés ${\bmod {8}}$ sont seulement $0$, $1$ et $4$ ${\pmod {8}}$ donc par exemple : $3$ est un carré ${\bmod {2}}$ mais pas ${\bmod {4}}$ et $5$ est un carré ${\bmod {4}}$ mais pas ${\bmod {8}}$.

 

Exercice 4-10

Le but de cet exercice est de déterminer les carrés modulo les puissances de $2$. Soit un entier $r\geq 3$.

1. Quel est l'ordre du groupe multiplicatif $\left(\mathbb {Z} /2^{r}\mathbb {Z} \right)^{\times }$ ?
2. Trouver le nombre de carrés dans ce groupe, en considérant les carrés des entiers impairs compris entre $0$ et $2^{r-2}$.
3. Vérifier que tout carré impair est congru à $1{\bmod {8}}$.
4. En déduire quels sont les carrés dans $\left(\mathbb {Z} /2^{r}\mathbb {Z} \right)^{\times }$.
5. Et dans $\mathbb {Z} /2^{r}\mathbb {Z}$ ?

Solution

Notons $n:=2^{r}$ et $m:=2^{r-2}$.

1. $\varphi \left(p^{r}\right)=p^{r-1}\left(p-1\right)$ donc $\varphi \left(n\right)=2^{r-1}=2m$.
2. Les éléments du groupe sont les classes des $2m$ entiers impairs compris (strictement) entre $-n/2=-2m$ et $n/2=2m$. Leurs carrés sont donc les classes des carrés des $m$ entiers impairs compris entre $0$ et $2m$. Les ${\frac {m}{2}}$ entiers impairs compris entre $0$ et $m$ suffisent même, car $\left(2m-k\right)^{2}\equiv k^{2}{\bmod {4m}}$. Et pour ces $k$ (impairs), les $k^{2}$ sont distincts ${\bmod {n}}$, car si $n=4m\mid k^{2}-\ell ^{2}$ c'est-à-dire $m=2^{r-2}\mid {\frac {k+\ell }{2}}{\frac {k-\ell }{2}}$, un seul des deux termes du produit est pair puisque leur somme est $k$ (impaire), donc $m$ divise l'un de ces deux termes, or $0<{\frac {k+\ell }{2}}<m$ et $-m<{\frac {k-\ell }{2}}<m$ donc $k=\ell$. Le nombre de carrés est donc exactement ${\frac {m}{2}}=2^{r-3}$ (remarque : c'est un quart du groupe alors que dans $\left(\mathbb {Z} /p^{r}\mathbb {Z} \right)^{\times }$ pour $p\neq 2$ et dans $\mathbb {Z} /4\mathbb {Z}$, c'est la moitié d'après l'exercice précédent. On peut en fait élucider complètement la structure du groupe $\left(\mathbb {Z} /p^{r}\mathbb {Z} \right)^{\times }$ pour p ≠ 2 et pour p = 2).
3. $\left(4k\pm 1\right)^{2}\equiv 1{\bmod {8}}$.
4. Dans $\left(\mathbb {Z} /2^{r}\mathbb {Z} \right)^{\times }$, il n'y a que $2^{r-3}$ éléments congrus à $1{\bmod {8}}$, donc tous sont des carrés d'après les deux questions précédentes.
5. Dans $\mathbb {Z} /2^{r}\mathbb {Z}$, les carrés sont $0$ et les classes de la forme $2^{2k}c{\bmod {2}}^{r}$ avec $2k<r$ et $c$ carré dans $\left(\mathbb {Z} /2^{r-2k}\mathbb {Z} \right)^{\times }$ c'est-à-dire : si $r=2k+1$, $c$ impair ; si $r=2k+2$, $c\equiv 1{\bmod {4}}$ (c'est-à-dire, dans ces deux cas, $2^{2k}c=4^{k}{\bmod {2}}^{r}$) ; si $r\geq 2j+3$, $c\equiv 1{\bmod {8}}$. Somme toute, ${\bmod {2}}^{r}$, ce sont simplement $0$ et les entiers de la forme $4^{k}\left(8m+1\right)$.

 

Exercice 4-11

Soit un nombre premier $p\geq 5$.

1. Déduire de la loi de réciprocité quadratique (jointe à sa première loi complémentaire) que $p\equiv 1{\bmod {3}}\Leftrightarrow \left({\frac {-3}{p}}\right)=1$.
   La suite de l'exercice va consister à redémontrer directement que $3\mid p-1$ si et seulement si $-3$ est un carré modulo $p$.
2. Montrer que $p\equiv 1{\bmod {3}}$ si et seulement si le groupe $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ contient un élément d'ordre $3$.
3. Montrer que les éventuels éléments d'ordre $3$ de $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ sont exactement les racines dans $\mathbb {Z} /p\mathbb {Z}$ du polynôme $X^{2}+X+1$.
4. Conclure.

Solution

1. $\left({\frac {-3}{p}}\right)=\left({\frac {-1}{p}}\right)\left({\frac {3}{p}}\right)=(-1)^{\frac {p-1}{2}}(-1)^{\frac {(p-1)(3-1)}{4}}\left({\frac {p}{3}}\right)=\left({\frac {p}{3}}\right)$ et modulo $3$, le seul carré non nul est $(-1)^{2}=1$.
2. Si $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ contient un élément d'ordre $3$ alors, d'après le théorème de Lagrange, $3\mid p-1$. Réciproquement, si $3\mid p-1$ alors il existe, dans le groupe $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$, un élément $x$ d'ordre $3$ : on peut par exemple prendre, comme Euler, $x=z^{\left(p-1\right)/3}$ où $z$ est un élément du groupe tel que $z^{\left(p-1\right)/3}\neq 1$ (il existe de tels $z$ puisque $\left(p-1\right)/3<p-1$), ou encore, invoquer le théorème de Cauchy sur les groupes ou son cas particulier pour les groupes abéliens, bien plus élémentaire. Un autre argument, à condition de savoir que le groupe $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ est cyclique, est d'utiliser la description des sous-groupes d'un groupe cyclique.
3. $X^{3}-1=\left(X-1\right)\left(X^{2}+X+1\right)$ et si un élément de $\mathbb {Z} /p\mathbb {Z}$ est racine de $X^{2}+X+1$ alors il est différent de $0$ et $1$.
4. D'après les deux questions précédentes, $p\equiv 1{\bmod {3}}$ si et seulement si, dans $\mathbb {Z} /p\mathbb {Z}$, $X^{2}+X+1$ est scindé, c'est-à-dire si son discriminant, $-3$, est un carré.

 

Exercice 4-12

Soit $p$ un nombre premier différent de $2$ et $5$.

1. Déduire de la loi de réciprocité quadratique que $p\equiv \pm 1{\bmod {5}}\Longleftrightarrow \left({\frac {5}{p}}\right)=1$.
   La suite de l'exercice va consister à redémontrer directement que $5\mid p^{2}-1$ si et seulement si $5$ est un carré ${\bmod {p}}$.
   On note ${\rm {F}}_{p^{2}}$ le corps fini à p² éléments.
2. Montrer que $5\mid p^{2}-1$ si et seulement si le groupe $\left({\rm {F}}_{p^{2}}\right)^{*}$ contient un élément d'ordre $5$.
3. Montrer que les éventuels éléments d'ordre $5$ de $\left({\rm {F}}_{p^{2}}\right)^{*}$ sont exactement les racines dans ${\rm {F}}_{p^{2}}$ du polynôme $X^{4}+X^{3}+X^{2}+X+1$.
4. Vérifier qu'un élément $x$ est racine de $X^{4}+X^{3}+X^{2}+X+1$ si et seulement si $x\neq 0$ et l'élément $t:=x+{\frac {1}{x}}$ est racine de $T^{2}+T-1$.
5. Montrer que si $p\equiv \pm 1{\bmod {5}}$ et si $x$ est un élément d'ordre $5$ de $\left({\rm {F}}_{p^{2}}\right)^{*}$ alors l'élément $t:=x+{\frac {1}{x}}$ appartient non seulement au corps ${\rm {F}}_{p^{2}}$ mais au sous-corps ${\rm {F}}_{p}:=\mathbb {Z} /p\mathbb {Z}$. (Indication : développer $\left(x+{\frac {1}{x}}\right)^{p}$.)
6. En déduire que $5\mid p^{2}-1$ si et seulement s'il existe $t\in {\rm {F}}_{p}$ tel que $t^{2}+t-1=0$.
7. Conclure.

Solution

1. $\left({\frac {5}{p}}\right)=(-1)^{\frac {(p-1)(5-1)}{4}}\left({\frac {p}{5}}\right)=\left({\frac {p}{5}}\right)$ et modulo $5$, les seuls carrés non nuls sont $(-1)^{2}=1$ et $(-2)^{2}\equiv -1$.
2. Même raisonnement que dans l'exercice précédent.
3. Même raisonnement que dans l'exercice précédent.
4. Calcul élémentaire.
5. $t^{p}=x^{p}+{\frac {1}{x^{p}}}$ et $x^{p}$ est égal soit à $x$ (si $5\mid p-1$), soit à ${\frac {1}{x}}$ (si $5\mid p+1$) donc $t^{p}=t$. D'après le petit théorème de Fermat, les $p$ éléments du sous-corps ${\rm {F}}_{p}$ sont racines du polynôme $T^{p}-T$, qui est de degré $p$, donc $t\in {\rm {F}}_{p}$.
6. Si $5\mid p^{2}-1$ alors il existe $t\in {\rm {F}}_{p}$ tel que $t^{2}+t-1=0$, d'après les questions 2 à 5. Réciproquement, soit $t\in {\rm {F}}_{p}$ tel que $t^{2}+t-1=0$. Comme l'équation $X^{2}-tX+1=0$ est de degré $2$ et à coefficients dans ${\rm {F}}_{p}$, elle a une solution $x\in {\rm {F}}_{p^{2}}$ donc $5\mid p^{2}-1$, d'après les questions 2 à 4.
7. Même raisonnement que dans l'exercice précédent (le discriminant de $T^{2}+T-1$ est $5$).

 

Exercice 4-13

Soient $p$ et $q$ deux nombres premiers impairs distincts. On se propose de redémontrer que $\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {\left(p-1\right)\left(q-1\right)}{4}}$.

1. Montrer que $\left({\frac {p}{q}}\right)=(-1)^{l}$ où $l$ est le nombre de couples $\left(x,y\right)\in \mathbb {Z} ^{2}$ tels que $0<x<q/2{\text{ et }}-q/2<px-qy<0$.
2. Montrer qu'un tel couple $\left(x,y\right)$ appartient au rectangle $0<x<q/2,\;0<y<p/2$.
3. Montrer que de même, $\left({\frac {q}{p}}\right)=(-1)^{m}$ où $m$ est le nombre de points $\left(x,y\right)\in \mathbb {Z} ^{2}$ de ce même rectangle tels que $-p/2<qy-px<0$.
4. Montrer que ${\frac {\left(p-1\right)\left(q-1\right)}{4}}-\left(l+m\right)$ est le nombre de points $\left(x,y\right)\in \mathbb {Z} ^{2}$ de ce rectangle vérifiant soit $px-qy\leq -q/2$, soit $qy-px\leq -p/2$, et que ces deux zones sont en bijection.
5. Conclure.

Solution

(Baker, p. 29-30.)

1. D'après le lemme de Gauss, $\left({\frac {p}{q}}\right)=(-1)^{l}$ où $l$ est le nombre d'entiers $x\in \left]0,q/2\right[$ pour lesquels $px$ est de la forme $qy-z$ avec $y$ et $z$ entiers et $0<z<q/2$. C'est donc bien le nombre annoncé.
2. On a $qy>(x-1/2)p\geq p/2>0$ et $qy<px<pq/2$, donc $0<y<p/2$.
3. En échangeant $p$ avec $q$ et $x$ avec $y$, on en déduit que :
   • $\left({\frac {q}{p}}\right)=(-1)^{m}$ où $m$ est le nombre de couples $\left(x,y\right)\in \mathbb {Z} ^{2}$ tels que $0<y<p/2{\text{ et }}-p/2<qy-px<0$ ;
   • ces couples vérifient : $0<y<p/2,\;0<x<q/2$.
4. Quand on enlève aux ${\frac {\left(p-1\right)\left(q-1\right)}{4}}$ points à coordonnées entières du rectangle les $l+m$ points des deux bandes (disjointes) précédemment considérées, il reste les deux coins des $\left(x,y\right)$ vérifiant soit $px-qy\leq -q/2$, soit $qy-px\leq -p/2$. Ces deux coins sont en bijection par l'involution $\left(x,y\right)\mapsto \left({\frac {q+1}{2}}-x,{\frac {p+1}{2}}-y\right)$ de l'ensemble des points à coordonnées entières du rectangle.
5. $l+m$ a donc même parité que ${\frac {\left(p-1\right)\left(q-1\right)}{4}}$, ce qui conclut.

 

Exercice 4-14

Le symbole de Jacobi $\left({\frac {a}{n}}\right)$ est défini pour tout $n\in \mathbb {N}$ impair et tout $a\in \mathbb {Z}$ comme produit de symboles de Legendre, en faisant intervenir la décomposition en facteurs premiers de $n$ : pour toute suite finie de nombres premiers impairs $p_{i}$ (non nécessairement distincts), $\left({\frac {a}{\prod p_{i}}}\right)=\prod _{1\leq i\leq k}\left({\frac {a}{p_{i}}}\right)$.

1. Montrer que $\left({\frac {a}{n}}\right)=\pm 1$ si $a$ et $n$ sont premiers entre eux et que $\left({\frac {a}{n}}\right)=0$ sinon.
2. A-t-on $\left({\frac {a}{n}}\right)=-1\Rightarrow a$ n'est pas un carré ${\bmod {n}}$ ? A-t-on $\left({\frac {a}{n}}\right)=1\Rightarrow a$ est un carré ${\bmod {n}}$ ?
3. Calculer $\left({\frac {123}{917}}\right)$.
4. Montrer que (pour $p_{i}$ impairs) $\prod p_{i}=\prod \left(1+p_{i}-1\right)\equiv 1+\sum \left(p_{i}-1\right){\bmod {4}}$, et en déduire que $\left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}$.
5. Montrer de même que (pour $m,n\in \mathbb {N}$ impairs) $\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {\left(m-1\right)\left(n-1\right)}{4}}$.
6. Montrer que $\left({\frac {2}{n}}\right)=(-1)^{\frac {n^{2}-1}{8}}$ (indication : $\prod p_{i}^{2}=\prod \left(1+p_{i}^{2}-1\right)\equiv \dots {\bmod {\dots }}$).

Solution

Apostol p. 188-190.

1. Immédiat, par définition du symbole de Legendre.
2. • Si $\left({\frac {a}{n}}\right)=-1$ alors $a$ n'est pas un carré ${\bmod {n}}$, puisqu'il n'en est pas un ${\bmod {p}}$ pour un certain diviseur premier $p$ de $n$.
   • Si $\left({\frac {a}{n}}\right)=1$, $a$ n'est pas nécessairement un carré ${\bmod {n}}$. Par exemple si $\left({\frac {a}{p}}\right)=-1$ alors $\left({\frac {a}{p^{2}}}\right)=(-1)^{2}=1$ mais $a$ n'est pas un carré ${\bmod {p^{2}}}$.
3. $\left({\frac {123}{7}}\right)\left({\frac {123}{131}}\right)=\left({\frac {4}{7}}\right)\left({\frac {-8}{131}}\right)=\left({\frac {-2}{131}}\right)=1$ (car $131\equiv 3{\bmod {8}}$ donc $\left({\frac {2}{131}}\right)=-1$ et $\left({\frac {-1}{131}}\right)=-1$).
4. $n=\prod \left(1+p_{i}-1\right)\equiv 1+\sum \left(p_{i}-1\right)+$ des multiples de $\left(p_{i}-1\right)\left(p_{j}-1\right)$ donc de $4$.
   $\left({\frac {-1}{n}}\right)=\prod \left({\frac {-1}{p_{i}}}\right)=\prod (-1)^{\frac {p_{i}-1}{2}}=(-1)^{\sum {\frac {p_{i}-1}{2}}}$ est donc égal à $(-1)^{\frac {n-1}{2}}$.
5. Soient $n=\prod _{i}p_{i},\;m=\prod _{j}q_{j}$ avec, sans perte de généralité, $p_{i}\neq q_{j}$. Alors, $\left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=\prod _{i,j}\left({\frac {p_{i}}{q_{j}}}\right)\left({\frac {q_{j}}{p_{i}}}\right)=(-1)^{r}$ avec $r=\sum _{i,j}{\frac {\left(p_{i}-1\right)\left(q_{j}-1\right)}{4}}$. Or on a vu dans la question précédente que $\sum {\frac {p_{i}-1}{2}}\equiv {\frac {n-1}{2}}{\bmod {2}}$ et de même pour $q_{j},m$. Donc $r\equiv {\frac {(m-1)(n-1)}{4}}{\bmod {2}}$.
6. $n^{2}=\prod p_{i}^{2}=\prod \left(1+p_{i}^{2}-1\right)\equiv 1+\sum \left(p_{i}^{2}-1\right){\bmod {64}}$ donc $\sum {\frac {p_{i}^{2}-1}{8}}\equiv {\frac {n^{2}-1}{8}}{\bmod {8}}$ et a fortiori ${\bmod {\,}}2$.
   $\left({\frac {2}{n}}\right)=\prod \left({\frac {2}{p_{i}}}\right)=\prod (-1)^{\frac {p_{i}^{2}-1}{8}}=(-1)^{\sum {\frac {p_{i}^{2}-1}{8}}}$ est donc égal à $(-1)^{\frac {n^{2}-1}{8}}$.

 

Exercice 4-15

Soit $a$ un entier relatif non carré. On se propose de démontrer qu'alors, il existe une infinité de nombres premiers modulo lesquels $a$ n'est pas un carré. On s'autorisera pour cela à utiliser non seulement la loi de réciprocité quadratique, mais aussi le théorème de la progression arithmétique de Dirichlet (pour une solution plus astucieuse qui se passe de ce théorème, voir le devoir « Principe local-global pour les carrés »).

On va distinguer trois cas, selon la parité des exposants $r_{i}$ (non tous pairs) dans la décomposition

$a=(-1)^{r_{0}}2^{r_{1}}p_{2}^{r_{2}}\dots p_{m}^{r_{m}}$,

où les $p_{i}$ sont des nombres premiers impairs distincts.

1. On suppose dans cette question que $r_{2},\dots ,r_{m}$ ne sont pas tous pairs : par exemple (quitte à permuter les $p_{i}$) $r_{2}$ est impair.
   1. Montrer qu'il existe un entier $x$ non carré ${\bmod {p_{2}}}$ et congru à à $1{\bmod {8p_{3}\dots p_{m}}}$.
   2. Montrer qu'il existe alors une infinité de nombres premiers $p$ congrus à $x{\bmod {8p_{2}\dots p_{m}}}$ et que modulo chacun de ces $p$, l'entier $a$ n'est pas un carré.
2. On suppose maintenant que $r_{2},\dots ,r_{m}$ sont pairs et $r_{1}$ impair (autrement dit : $a=\pm 2b^{2}$). Montrer qu'il existe une infinité de nombres premiers $p$ congrus à $-3{\bmod {8}}$ et que pour une infinité d'entre eux, $\left({\frac {a}{p}}\right)=-1$.
3. On suppose enfin que $r_{1},\dots ,r_{m}$ sont pairs et $r_{0}$ impair (autrement dit : $a=-b^{2}$). Montrer qu'il existe une infinité de nombres premiers $p$ congrus à $-1{\bmod {4}}$ et que pour une infinité d'entre eux, $\left({\frac {a}{p}}\right)=-1$.

Solution

1. 1. Soit $y$ non carré ${\bmod {p_{2}}}$. D'après le théorème des restes chinois, il existe un entier $x$ congru à $y{\bmod {p_{2}}}$ et à $1{\bmod {8p_{3}\dots p_{m}}}$.
   2. Un tel $x$ est premier avec $8p_{2}\dots p_{m}$ (car $x\equiv 1{\bmod {8p_{3}\dots p_{m}}}$ et $x\not \equiv 0{\bmod {p_{2}}}$) donc il existe (par Dirichlet) une infinité de nombres premiers $p\equiv x{\bmod {8p_{2}\dots p_{m}}}$. Un tel $p$ étant congru à $1{\bmod {8}}$, on a :
      • $\left({\frac {-1}{p}}\right)=\left({\frac {2}{p}}\right)=1$ ;
      • pour $i\geq 3$, $\left({\frac {p_{i}}{p}}\right)=\left({\frac {p}{p_{i}}}\right)=\left({\frac {1}{p_{i}}}\right)=1$ ;
      • $\left({\frac {p_{2}}{p}}\right)=\left({\frac {p}{p_{2}}}\right)=\left({\frac {x}{p_{2}}}\right)=-1$

      donc $\left({\frac {a}{p}}\right)=\left({\frac {-1}{p}}\right)^{r_{0}}\left({\frac {2}{p}}\right)^{r_{1}}\prod _{i\geq 2}\left({\frac {p_{i}}{p}}\right)^{r_{i}}=(-1)^{r_{2}}=-1$.

2. Puisque $-3$ et $8$ sont premiers entre eux, il existe (par Dirichlet) une infinité de premiers $p\equiv -3{\bmod {8}}$. Pour un tel $p$ qui de plus ne divise pas $b$ (ce qui n'en exclut qu'un nombre fini), on a $\left({\frac {-1}{p}}\right)=1$, $\left({\frac {2}{p}}\right)=-1$ et $\left({\frac {b^{2}}{p}}\right)=\left({\frac {b}{p}}\right)^{2}=1$, donc $\left({\frac {a}{p}}\right)=-1$.
3. Puisque $-1$ et $4$ sont premiers entre eux, il existe (par Dirichlet) une infinité de premiers $p\equiv -1{\bmod {4}}$. Pour un tel $p$ qui de plus ne divise pas $b$ (ce qui n'en exclut qu'un nombre fini), on a $\left({\frac {-1}{p}}\right)=-1$ et $\left({\frac {b^{2}}{p}}\right)=1$, donc $\left({\frac {a}{p}}\right)=-1$.

Remarques

• Dans les questions 2 et 3, on peut en fait se passer du théorème de Dirichlet, car sa preuve dans ces deux cas particuliers est élémentaire : voir l'article de Wikipédia sur les nombres premiers pythagoriciens.
• Sur un sujet distinct mais connexe, voir la discussion « Proving that an integer is the nth power », sur math.stackexchange, qui fournit, sur ce problème particulier, les deux références suivantes :
  • Paul B. Garrett, Abstract Algebra, CRC Press, 2007 [lire en ligne], p. 287  (même principe que le présent exercice mais moins bien structuré) ;
  • Marshall Hall, « Quadratic residues in factorization », Bull. Amer. Math. Soc., vol. 39, n^o  10, 1933, p. 758-763 [texte intégral] (assez pointu mais commence par des remarques simples, comme le fait qu'une puissance impaire de $2$ n'est jamais un carré ${\bmod {3}}$).

 

Exercice 4-16

Cet exercice généralise le précédent, avec les mêmes outils.

Soient $P$ un ensemble fini de nombres premiers impairs et $Q$ l'ensemble $P\cup \{-1,2\}$.

1. Soit $\varepsilon$ une application de $Q$ dans $\{-1,1\}$. Montrer que pour une infinité de nombres premiers $p$, on a : $\forall q\in Q\quad \left({\frac {q}{p}}\right)=\varepsilon (q)$.
2. Soit $A$ un ensemble de produits d'éléments de $Q$ tel qu'aucun produit d'éléments de $A$ ne soit un carré à part l'inévitable produit vide, et soit $g$ une application de $A$ dans $\mathbb {Z} /2\mathbb {Z}$.
   1. Pour tout $a\in A$, on note $v_{a}$ le vecteur du $\mathbb {Z} /2\mathbb {Z}$-espace vectoriel $\left(\mathbb {Z} /2\mathbb {Z} \right)^{Q}$ dont la composante $v_{a}(q)\in \mathbb {Z} /2\mathbb {Z}$ d'indice $q$, pour chaque $q\in Q$, est la parité de l'exposant de $q$ dans la décomposition de $a$ en facteurs « premiers » (lorsqu'on incorpore $-1$ à l'ensemble des nombres premiers).
      Montrer qu'il existe au moins une forme linéaire $f$ sur $\left(\mathbb {Z} /2\mathbb {Z} \right)^{Q}$ telle que $\forall a\in A\quad f\left(v_{a}\right)=g\left(a\right)$.
   2. En déduire, grâce à la première question, qu'il existe une infinité de nombres premiers $p$ tels que $\forall a\in A\quad \left({\frac {a}{p}}\right)=(-1)^{g(a)}$.
   3. En utilisant la version quantitative du théorème de la progression arithmétique, préciser la densité asymptotique relative (dans l'ensemble des nombres premiers) de cet ensemble infini de solutions $p$.

Solution

1. Cherchons $p$ parmi les nombres premiers n'appartenant pas à $Q$.

   Outre la condition $(-1)^{(p^{2}-1)/8}=\varepsilon (2)$, il faut, d'après la loi de réciprocité quadratique :

   • si $\varepsilon (-1)=1$ : que $p\equiv 1{\bmod {4}}$ et $\forall q\in P\quad \left({\frac {p}{q}}\right)=\varepsilon (q)$ ;
   • si $\varepsilon (-1)=-1$ : que $p\equiv -1{\bmod {4}}$ et $\forall q\in P\quad \left({\frac {p}{q}}\right)=\varepsilon (q)(-1)^{q-1}$.

   La condition $(-1)^{(p^{2}-1)/8}=\varepsilon (2)$ impose de plus, dans chacun des deux cas, un choix entre deux classes ${\bmod {8}}$ :

   • dans le premier cas, $p\equiv {\begin{cases}1{\bmod {8}}&{\text{si }}\varepsilon (2)=1\\-3{\bmod {8}}&{\text{si }}\varepsilon (2)=-1~;\end{cases}}$
   • dans le second cas, $p\equiv {\begin{cases}-1{\bmod {8}}&{\text{si }}\varepsilon (2)=1\\3{\bmod {8}}&{\text{si }}\varepsilon (2)=-1.\end{cases}}$

   Il s'agit donc de montrer que pour tout $z\in \{\pm 1,\pm 3\}$ et toute application $\eta :P\to \{-1,1\}$, il existe une infinité de nombres premiers $p\equiv z{\bmod {8}}$ tels que $\forall q\in P\quad \left({\frac {p}{q}}\right)=\eta (q)$.

   Choisissons, pour chaque $q\in P$, un entier $y_{q}$ tel que $\left({\frac {y_{q}}{q}}\right)=\eta (q)$.

   D'après le théorème des restes chinois, il existe un entier $x\equiv z{\bmod {8}}$ tel que $\forall q\in P\quad x\equiv y_{q}{\bmod {q}}$.

   Par construction, $x$ est impair et premier avec tous les $q\in P$. D'après le théorème de la progression arithmétique, il existe donc une infinité de nombres premiers $p\equiv x{\bmod {8}}\prod _{q\in P}q$, ce qui conclut.

2. 1. Par hypothèse sur $A$, la famille $\left(v_{a}\right)_{a\in A}$ est libre, d'où — d'après les propriétés de la dualité — l'existence de $f$.
   2. Notons $\left(e_{q}\right)_{q\in Q}$ la base canonique de $\left(\mathbb {Z} /2\mathbb {Z} \right)^{Q}$. D'après la première question, il existe une infinité de nombres premiers $p$ tels que $\forall q\in Q\quad \left({\frac {q}{p}}\right)=(-1)^{f\left(e_{q}\right)}$. Pour ces $p$, on a : $\forall a\in A\quad \left({\frac {a}{p}}\right)=\prod _{q\in Q}\left({\frac {q}{p}}\right)^{v_{a}(q)}=\prod _{q\in Q}(-1)^{f\left(e_{q}\right)v_{a}(q)}=(-1)^{\sum _{q\in Q}f\left(e_{q}\right)v_{a}(q)}=(-1)^{f\left(\sum _{q\in Q}v_{a}(q)e_{q}\right)}=(-1)^{f\left(v_{a}\right)}=(-1)^{g(a)}$.
   3. Soit $n:=8\prod _{q\in P}q$. D'après la recherche exhaustive des questions précédentes, l'ensemble des solutions $p$ est, à un ensemble fini près, l'ensemble des nombres premiers appartenant à certaines classes de congruence ${\bmod {n}}$. Chacune a pour densité relative ${\frac {1}{\varphi (n)}}$, et le nombre de ces classes est le produit du nombre de choix pour $f$, soit $2^{|Q|-|A|}$ choix, par le nombre de classes ${\bmod {n}}$ adéquates pour chaque $f$, soit $\prod _{q\in P}{\frac {q-1}{2}}$ classes. La densité relative de l'ensemble des solutions est donc : ${\frac {1}{\varphi (n)}}2^{|Q|-|A|}\prod _{q\in P}{\frac {q-1}{2}}={\frac {1}{\varphi (8)}}2^{|Q|-|A|-|P|}=2^{-|A|}$.

 

Exercice 4-17

À l'aide de la loi de réciprocité quadratique, caractériser :

1. parmi les nombres premiers $p>5$, ceux tels que $-40$ est un carré ${\bmod {4p}}$ ;
2. parmi les nombres premiers $p>3$, ceux tels que $-24$ est un carré ${\bmod {4p}}$.

Solution

Remarquons d'abord que pour tous entiers $a$ et $b$, $4a$ est un carré ${\bmod {4b}}$ (si et) seulement si $a$ est un carré ${\bmod {b}}$.

1. $-40$ est un carré ${\bmod {4p}}$ si et seulement si $-10$ est un carré ${\bmod {p}}$, c'est-à-dire $\left({\frac {-1}{p}}\right)\left({\frac {2}{p}}\right)\left({\frac {5}{p}}\right)=1$. Or le nombre
   $\left({\frac {-1}{p}}\right)\left({\frac {2}{p}}\right)\left({\frac {5}{p}}\right)=(-1)^{(p-1)/2}(-1)^{(p^{2}-1)/8}(-1)^{(p-1)(5-1)/4}\left({\frac {p}{5}}\right)=(-1)^{(p-1)(p+5)/8}\left({\frac {p}{5}}\right)$
   est égal à $1$ si et seulement si : ou bien [$(p-1)(p+5)$ est divisible par $16$ et $p$ est un carré ${\bmod {5}}$], ou bien [$(p-1)(p+5)$ n'est pas divisible par $16$ et $p$ n'est pas un carré ${\bmod {5}}$], c'est-à-dire :
   ou bien [$p\equiv 1$ ou $3{\bmod {8}}$ et $p\equiv \pm 1{\bmod {5}}$], ou bien [$p\equiv -1$ ou $-3{\bmod {8}}$ et $p\equiv \pm 2{\bmod {5}}$].
2. $-24$ est un carré ${\bmod {4p}}$ si et seulement si $-6$ est un carré ${\bmod {p}}$. Or le nombre
   $\left({\frac {-6}{p}}\right)=\left({\frac {-2}{p}}\right)\left({\frac {3}{p}}\right)=(-1)^{\frac {p-1}{2}}(-1)^{\tfrac {p^{2}-1}{8}}(-1)^{\frac {(p-1)(3-1)}{4}}\left({\frac {p}{3}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}\left({\frac {p}{3}}\right)$
   est égal à $1$ si et seulement si $(-1)^{\tfrac {p^{2}-1}{8}}=\left({\frac {p}{3}}\right)=1$ ou $(-1)^{\tfrac {p^{2}-1}{8}}=\left({\frac {p}{3}}\right)=-1$.
   $(-1)^{\tfrac {p^{2}-1}{8}}=1\Leftrightarrow 16\mid (p+1)(p-1)\Leftrightarrow p\equiv \pm 1{\bmod {8}}$, donc $(-1)^{\tfrac {p^{2}-1}{8}}=-1\Leftrightarrow p\equiv \pm 3{\bmod {8}}$.
   $\left({\frac {p}{3}}\right)=1\Leftrightarrow p\equiv 1{\bmod {3}}$, donc $\left({\frac {p}{3}}\right)=-1\Leftrightarrow p\equiv -1{\bmod {3}}$.
   Par conséquent, $-24$ est un carré ${\bmod {4p}}$ si et seulement si :
   ou bien [$p\equiv \pm 1{\bmod {8}}$ et $p\equiv 1{\bmod {3}}$], ou bien [$p\equiv \pm 3{\bmod {8}}$ et $p\equiv -1{\bmod {3}}$].