Un jeu

Hello Sneg,

Je répond sous forme de code aussi : $2,0,1; 1,*;3,0$ :-D

Oups j'ai mal lu le jeu :-D

$\def\F{\mathbb F}$Coucou Sneg,
Je réponds après Poirot sans te donner vraiment la solution. Une précision : pas de négation ni de raisonnement par l'absurde avec mézigue. Pourquoi ? Parce que je n'aime pas et que je suis capricieux.

$\bullet$ A. Si tu connais les nombres complexes. En présence de $x^2 + y^2 = 0$ dans $\C$ et de $x \ne 0$, que peux tu en déduire concernant $(x^{-1}y)^2$ ? Et comme je n'aime pas $x \ne 0$, je le remplace par la vraie vérité : $x$ est inversible.

Dans l'histoire $a = x^2 + y^2$ avec $\gcd(x,y) = 1$, en passant dans $\Z/a\Z$, on obtient $x^2 + y^2 = 0$. On va pouvoir appliquer le trick ci-dessus. A condition de prouver que $x, y$ sont inversibles modulo $a$. Note : ils le sont tous les deux.
Questions : pourrais tu montrer que $\gcd(a,x) = 1$ ET que $\gcd(a,y) = 1$ ? De la manière la plus directe. Et en déduire ce qu'il faut.

$\bullet$ B. Du coup, je vais continuer à jouer. D'abord, j'ai relu l'article de Stan Wagon, The Euclidean Algorithm Strikes Again, Amer. Math. Monthly vol. 97, numéro 2, 1990. J'y ai vu, lorsque $a$ est un premier $p \equiv 1 \bmod 4$, disons que $p = 4k + 1$, que Gauss disposait d'une formule pour écrire $p$ sous la forme $x^2 + y^2$.
$$
x = {1 \over 2} {2k \choose k} \bmod p, \qquad y = (2k! \times x) \bmod p
$$A CONDITION de prendre pour $\bmod$ l'opérateur de reste $r$ dans la division par $p$ vérifiant $|r| < p/2$. I.e. remplacer le reste habituel $r$ par $p-r$ si besoin. Cette formule de détermination de $(x,y)$ n'est pas efficace pour le calcul mais ce n'est pas son but.

[color=#000000]> k := 15 ;                                                             
> p := 4*k + 1 ;
> p ;
61
> Reste := func < m |  2*r lt p select r else p-r where r is m mod p > ;
> x := Reste(ExactQuotient(Binomial(2*k, k), 2)) ;
> y := Reste(Factorial(2*k) * x) ;
> x ;
5
> y ;
6
> p ;
61
> x^2 + y^2 ;
61
[/color]

$\bullet$ C. J'ai lu aussi le coup suivant, toujours dans le contexte $p \equiv 1 \bmod 4$. Soit $N_p$ le nombre de points de $y^2 = x^3 -x$ sur $\F_p = \Z/p\Z$. Alors :
$$
x = \left| {N_p - p \over 2} \right| \quad \text{ intervient dans} \quad p = x^2 + y^2
$$

[color=#000000]> EllipticCurve([-1, 0]) ;         
Elliptic Curve defined by y^2 = x^3 - x over Rational Field
> p := 61 ;
> Fp := GF(p) ;
> Ep := EllipticCurve([Fp| -1, 0]) ;
> Ep ;
Elliptic Curve defined by y^2 = x^3 + 60*x over GF(61)
> Np := #Ep - 1 ;
> Np ;
71
> (Np - p) / 2 ;
5
[/color]

$\bullet$ D. Pour épater ses ami(e)s. Les polynômes d'Euler. Tu connais ? Regarde bien la formation de
$$
f_4(q_1,q_2,q_3,q_4), \qquad \qquad f_5(q_1, q_2, q_3, q_4, q_5)
$$

[color=#000000]> f4 := func < q1,q2,q3,q4 | q1*q2*q3*q4 + q3*q4 + q1*q4 + q1*q2 + 1 > ;
> f5 := func < q1,q2,q3,q4,q5 | q1*q2*q3*q4*q5 + q3*q4*q5 + q1*q4*q5 + q1*q2*q5 + q1*q2*q3 + q5 + q3 + q1 > ;
[/color]

Par exemple, pour $f_5$, on met le produit $q_1q_2q_3q_4q_5$ et ensuite on supprime deux $q_i$ consécutifs pour obtenir $q_3q_4q_5 + q_1q_4q_5 + \cdots $. Et on recommence (suppression de deux consécutifs) pour obtenir $q_5 + q_3 + q_1$.

Je choisis maintenant 5 entiers $q_i \ge 1$ qui vont être les quotients dans l'algorithme d'Euclide de deux entiers définis plus loin. Attention : le dernier quotient doit être $\ge 2$. Dans une division euclidienne de longueur $\ge 2$, le dernier quotient n'est jamais 1.

[color=#000000]> q1 := 3 ;  q2 := 7 ;  q3 := 1 ; q4 := 5 ; q5 := 2 ;
[/color]

Les deux entiers $a,b$ avec lesquels on va réaliser l'algorithme d'Euclide :

[color=#000000]> a := f5(q1,q2,q3,q4,q5) ;
> a ;
319
> b := f4(q2,q3,q4,q5) ;
> b ;
102
[/color]

L'algorithme d'Euclide :

[color=#000000]> r0 := a ; r1 := b ;
> Q := [] ;
> while r1 ne 0 do
while> q, r := Quotrem(r0,r1) ;
while> Append(~Q, q) ;
while> r0 := r1 ; r1 := r ;
while> end while ;
> Q ;
[ 3, 7, 1, 5, 2 ]
[/color]

On retrouve bien nos $q_i$ de départ. Merci Euclide, Euler, Gauss et les autres.

Sneg,
Vraiment ? Peut-être que je n'aurais pas utiliser dû utiliser l'adjectif ``inversible'' ? Ci-dessous un petit quelque chose.

(1) Supposons $x^2 + y^2 = 0$ dans $\C$ avec $x \ne 0$. On divise par $x^2$ ce qui donne $1 + (x^{-1}y)^2 = 0$ d'où une égalité de type convoité $z^2 = -1$.

On peut zapper sur ce point (1) : c'était juste pour donner une idée.

(2) Soit $a = x^2 + y^2$ avec $\gcd(x,y) = 1$. Montrons que $x,a$ sont premiers entre eux. Soit $d$ un diviseur commun à $x$ et $a$. A fortiori $d \mid x^2$ donc $d \mid a - x^2 = y^2$. Mais $x,y$ étant premiers entre eux, il en est de même de $x,y^2$. Puisque $d$ divise $x$ et $y^2$, on a $d = \pm 1$, ce qu'il fallait montrer.

(3) Faisons comme dans le point (1) ou simulons le au sens du calcul modulo $a$. Comme $x,a$ sont premiers entre eux, il existe un entier $x'$ tel que $x' x \equiv 1 \bmod a$ (on dit que $x'$ est un inverse de $x$ modulo $a$). On a :
$$
x^2 + y^2 \equiv 0 \bmod a, \qquad x'x \equiv 1 \bmod a \qquad \text{d'où par multiplication par } x'^2 \qquad
1 + (x'y)^2 \equiv 0 \bmod a
$$On vient de trouver une racine carrée de $-1$ modulo $a$ : c'est $x'y$.

Pareil, pas pareil ?

D'une façon générale et pour $m$ un nombre impaire le nombre de solutions de l'équation $x^2\equiv a\pmod m$ est : $$
\prod_{p|m}\left(1+\left({\tfrac {a}{p}}\right)\right),
$$ avec $\left({\tfrac {a}{p}}\right)$ le symbole de Legendre : $$
\left(\frac ap\right)=\left\{\begin{array}{cl}1,&\mbox{si }
p\nmid a\mbox{ et } a \mbox{ résidu quadratique (mod }p);\\ -1,
&\mbox{si }p\nmid a \mbox{ et }a \mbox{ n'est pas un résidu quadratique (mod }
p);\\ 0,&\mbox{si }p\mid a.\end{array}\right.
$$ Donc pour que $x^2\equiv -1\pmod{m}$ ait une solution, il doit que $p\mid m \implies \left({\tfrac {a}{p}}\right) \neq -1$.
Dans $\mathbb{Z}/m\mathbb{Z}$ on a : $-1=m-1$, puisque $p|m$, on a $p \nmid m-1$. le seul cas qui reste pour que $\left({\tfrac {a}{p}}\right) \neq -1$ c'est pour $m-1$ un résidu quadratique $\pmod p$

Conclusion: Pour que $x^2\equiv -1\pmod{m}$ ait une solution il faut que $p|m \implies (\exists k \in \mathbb{N}), m-1=k^2 \pmod p$ et dans ce cas le nombre de solutions est $2^{\omega (m)}$, avec $\omega(m)$ est le nombre des diviseurs premiers distincts de $m$

@jandri, j'ai oublié de mentionner que $m$ est impaire.

Jean-éric,
Bonne année 2020.
J'attache l'exercice corrigé en question (laisse béton l'incohérence des dates due à des recompilations). L'article dont je me suis inspiré est en https://www.jstor.org/stable/2323912?seq=1 mais l'accès n'est pas gratuit.