Enigmette

2732

Et on a aussi $$62^2+65^2=8069$$

Si $a \in \mathbb Z/p \mathbb Z$ est tel que $(-a)a=-a^2=1$ alors $-1=a^2$ est un carré modulo $p$, et il est bien connu que c'est le cas si et seulement si $p=1 \pmod 4$. Réciproquement, si $p=1 \pmod 4$, et si $b^2=-1$ modulo $p$ alors $b$ est l'inverse de $-b$.

Pour calculer le produit $P$ des inversibles modulo $p$ premier, on regroupe pour commencer les paires d'inversibles, dont le produit est 1 .
Les non-appariables sont 1 et $-1$, donc $P=-1$ (th. de Wilson).

On peut aussi regrouper d'abord les paires d'opposés non nuls, qu'on écrit $\{ x,-x \}$ avec $x<p/2$.
Soit $Q$ le produit des non nuls $< p/2$ On a alors $-1=P=Q^2 (-1)^{(p-1)/2}$
Si $p$ est de la forme $4n+1$ le dernier facteur vaut 1 et $Q$ est une racine carrée de $-1$.

Exemple avec $p=13$ :
$$
6!=720\equiv 5\qquad,\qquad 5^2=25\equiv -1
$$

GaBuZoMeu a récemment montré une méthode pour $\Z[i\sqrt2]$ qu'on peut adapter ici à $\Z[ i]$ puisque $p\equiv1\ [4]$ :

• pour tous les entiers $a$ à partir de $2$, calculer $b=a^{(p-1)/4}$ dans $\Z/p\Z$ ; on s'arrête dès que $b\ne\pm1$, ce qui arrive lorsque $a$ est un générateur de $(\Z/p\Z)^*$ ; le $b$ trouvé est alors une racine quatrième de l'unité (d'où le nom) ; on relève $b$ en un entier noté encore $b$ ;
• calculer dans $\Z[ i]$ le PGCD de $b+i$ et de $8069$ : ça donne $u+iv$ tel que $u^2+v^2=8069$.

Un code possible :

p = 8069
K.<i> = NumberField(x^2+1)
R = K.maximal_order()
a, b = 1, 1
while b^2==1:
    a+= 1
    b = pow(a,(p-1)/4,p)
print 'a = %s, b = %s' % (a,b)
gcd(R(ZZ(b)+i),R(p))

et la sortie :

a = 2, b = 5337
-65*i + 62

Ce n'est manifestement pas ce qu'a fait flip flop qui semble procéder en sens inverse.

Cela dit, avec un nombre aussi petit que 8069, on peut aussi se permettre d'être naïf ou bourrin.

for k in range(floor(sqrt(8069))):
    for l in range(k):
        if k^2+l^2==8069:
            print k,l