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 $a{x}^2+b{y}^2\equiv cmodp$. (Indication : combien y a-t-il de carrés dans $\mathbb{Z}/p\mathbb{Z}$ ?) Modèle:Solution

Exercice 4-2

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

Exercice 4-3

Que donne le lemme de Gauss pour $a=-1$ ? Modèle:Solution

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 $modp$ est égale à $p(p-1)/4$. (Indication : $a+(p-a)=p$.) Modèle:Solution

Exercice 4-5

Soit un nombre premier $p>2$.

1. Démontrer le théorème de Wilson : $(p-1)!\equiv -1modp$.
2. En déduire que le produit des carrés non nuls de $\mathbb{Z}/p\mathbb{Z}$ est égal à $(-1{)}^{(p+1)/2}(\mathrm{mod}p)$. (Indication : $k(p-k)\equiv -k^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 $modp$ si (et seulement si) $a^m\equiv 1modp$.
2. Pour $n=2$ (donc $p\ne 2$), en déduire le « critère d'Euler » usuel : $a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)modp$.

Exercice 4-7

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

Exercice 4-8

Soient $p$ un nombre premier impair et $\epsilon :=\{\begin{array}{c}1\text{ si }p\equiv \pm 1mod8\\ -1\text{ si }p\equiv \pm 3mod8.\end{array}$

On se propose de redémontrer que $\left(\frac{2}{p}\right)=\epsilon$, 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 ${\mathrm{F}}_p[\zeta ]:={\mathrm{F}}_p[X]/(X^4+1)$ (non intègre car $X^4+1={\mathrm{\Phi }}_8(X)$, le [[w:Polynôme cyclotomique#Définition et exemples|8Modèle: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=\epsilon \tau$ (indication : remarquer que ${\tau }^p={\zeta }^p+{\zeta }^{-p}$).
5. Conclure.

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 0mod{p}^k$ et $P^{\prime }\left(r\right)\equiv ̸0modp$.
   Montrer qu'il existe un entier $s\equiv rmod{p}^k$ tel que $P\left(s\right)\equiv 0mod{p}^{2k}$.
2. En déduire que si $p$ est impair, tout entier non divisible par $p$ qui est un carré $modp$ est aussi un carré $mod{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é $mod2$ mais pas $mod4$, et un entier impair qui est un carré $mod4$ mais pas $mod8$.

Exercice 4-10

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

1. Quel est l'ordre du groupe multiplicatif ${(\mathbb{Z}/2^r\mathbb{Z})}^{\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 à $1mod8$.
4. En déduire quels sont les carrés dans ${(\mathbb{Z}/2^r\mathbb{Z})}^{\times }$.
5. Et dans $\mathbb{Z}/2^r\mathbb{Z}$ ?

Exercice 4-11

Soit un nombre premier $p\ge 5$.

1. Déduire de la loi de réciprocité quadratique (jointe à sa première loi complémentaire) que $p\equiv 1mod3\iff \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 1mod3$ si et seulement si le groupe ${(\mathbb{Z}/p\mathbb{Z})}^{*}$ contient un élément d'ordre $3$.
3. Montrer que les éventuels éléments d'ordre $3$ de ${(\mathbb{Z}/p\mathbb{Z})}^{*}$ sont exactement les racines dans $\mathbb{Z}/p\mathbb{Z}$ du polynôme $X^2+X+1$.
4. Conclure.

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 1mod5⟺\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é $modp$.
   On note ${\mathrm{F}}_{p^2}$ le [[w:Corps fini#Exemple : les corps à p2 éléments|corps fini à pModèle:Exp éléments]].
2. Montrer que $5\mid p^2-1$ si et seulement si le groupe ${\left({\mathrm{F}}_{p^2}\right)}^{*}$ contient un élément d'ordre $5$.
3. Montrer que les éventuels éléments d'ordre $5$ de ${\left({\mathrm{F}}_{p^2}\right)}^{*}$ sont exactement les racines dans ${\mathrm{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\ne 0$ et l'élément $t:=x+\frac{1}{x}$ est racine de $T^2+T-1$.
5. Montrer que si $p\equiv \pm 1mod5$ et si $x$ est un élément d'ordre $5$ de ${\left({\mathrm{F}}_{p^2}\right)}^{*}$ alors l'élément $t:=x+\frac{1}{x}$ appartient non seulement au corps ${\mathrm{F}}_{p^2}$ mais au sous-corps ${\mathrm{F}}_p:=\mathbb{Z}/p\mathbb{Z}$. (Indication : développer ${(x+\frac{1}{x})}^p$.)
6. En déduire que $5\mid p^2-1$ si et seulement s'il existe $t\in {\mathrm{F}}_p$ tel que $t^2+t-1=0$.
7. Conclure.

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{(p-1)(q-1)}{4}}$.

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

Exercice 4-14

Modèle:Wikipédia 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\le i\le 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é $modn$ ? A-t-on $\left(\frac{a}{n}\right)=1\Rightarrow a$ est un carré $modn$ ?
3. Calculer $\left(\frac{123}{917}\right)$.
4. Montrer que (pour $p_i$ impairs) $\prod p_i=\prod (1+p_i-1)\equiv 1+\sum (p_i-1)mod4$, 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{(m-1)(n-1)}{4}}$.
6. Montrer que $\left(\frac{2}{n}\right)=(-1{)}^{\frac{n^2-1}{8}}$ (indication : $\prod p_i^2=\prod (1+p_i^2-1)\equiv \dots mod\dots$).

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 [[../../Nombres premiers et fonctions arithmétiques#Énoncés de quelques conjectures et théorèmes célèbres sur les nombres premiers|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 « [[../../Devoir/Principe local-global pour les carrés|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é $mod{p}_2$ et congru à à $1mod8p_3\dots p_m$.
   2. Montrer qu'il existe alors une infinité de nombres premiers $p$ congrus à $xmod8p_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 à $-3mod8$ 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 à $-1mod4$ et que pour une infinité d'entre eux, $\left(\frac{a}{p}\right)=-1$.

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 $\epsilon$ une application de $Q$ dans $\{-1,1\}$. Montrer que pour une infinité de nombres premiers $p$, on a : $\mathrm{\forall }q\in Q\left(\frac{q}{p}\right)=\epsilon (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 ${(\mathbb{Z}/2\mathbb{Z})}^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 ${(\mathbb{Z}/2\mathbb{Z})}^Q$ telle que $\mathrm{\forall }a\in Af\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 $\mathrm{\forall }a\in A\left(\frac{a}{p}\right)=(-1{)}^{g(a)}$.
   3. En utilisant la [[../../Nombres premiers et fonctions arithmétiques#Énoncés de quelques conjectures et théorèmes célèbres sur les nombres premiers|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$.

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é $mod4p$ ;
2. parmi les nombres premiers $p>3$, ceux tels que $-24$ est un carré $mod4p$.