Résidus quadratiques

Par jp, le mercredi 22 décembre 2010 à 19:07 | Suites | Page principale Jeux et Mathématiques

Résoudre l'équation diophantienne

$a + bx = u^2$

dans laquelle  $a$ et $b$ sont donnés, $a>0$, $b>1$, on peut supposer $u \geq 0$ et accepter $x$ négatif pour faire plus simple.

On cherche les solutions $x$ ou $u$ ou $(x, u)$, (selon les préférences du moment).
 

Réponse

$a + bx = u^2$ équivaut à dire que $a$ est un carré modulo $b$

Il suffit donc de connaître l'ensemble des $t$ positifs inférieurs à$b$ tels que    $a = t^2 \mod b$ pour engendrer l'ensemble des solutions
(qui correspondent aux égalités $a + by = t^2$ avec $ 0\leq t<b$)

Pour chaque solution $(y,t)$ avec $0 \leq t <b $ on écrit
$a + bx = (kb+t)^2$, et
$a + by = t^2$ puis en soustrayant

$b(x-y) = k^2b^2 t^2 + 2kbt+t^2-t^2$
et enfin la formule paramétrée par $k$
$x = y + k^2bt^2+2kt $ où $y$ et $t$ sont fixés et $k$ positif est le paramètre variable

Suites OEIS

Il n'existe pas toujours des solutions, certains $a$ ne sont pas des carrés modulo b
Par exemple la suite  http://oeis.org/A057125 donne les valeurs des $b$ pour lesquelles $a=3$ est un carré modulo $b$
Il y a des suites OEIS pour d'autres valeurs de $a$

Entrez $a=$

 

1, 2, 3, 6, 11, 13, 22, 23, 26, 33, 37, 39, 46, 47, 59, 61, 66, 69, 71, 73, 74, 78, 83, 94, 97, 107, 109, 111, 118, 121, 122, 131, 138, 141, 142, 143, 146, 157, 166, 167, 169, 177, 179, 181, 183, 191, 193, 194, 213, 214, 218, 219, 222, 227, 229, 239, 241, 242, 249, 251, 253, 262, 263, 277, 282, 286, 291, 299, 311  

 

Calcul des solutions

Lorsque a est un carré modulo b, il peut aussi exister plusieurs solutions $a + by = t$ avec $t$ entre $0$ et $b$
par exemple les quatre familles ci-dessous pour $a=4$ et $b=42$
# a=4  b=42  x0=0   t=2
    0; 46; 176; 390; 688; 1070; 1536; 2086; 2720; 3438; 4240;
# a=4  b=42  x0=6   t=16
    6; 80; 238; 480; 806; 1216; 1710; 2288; 2950; 3696; 4526;
# a=4  b=42  x0=16   t=26
    16; 110; 288; 550; 896; 1326; 1840; 2438; 3120; 3886; 4736;
# a=4  b=42  x0=38   t=40
    38; 160; 366; 656; 1030; 1488; 2030; 2656; 3366; 4160; 5038;
(ces suites n'ont pas d'éléments communs)
on remarque 2+40 = 42 et 16+26=42 pour les valeurs de t et plus généralement
a + bx = u^2
a + by = t^2
donnent
b(x-y) = u^2 - t^2 ou si on préfère b(x-y) = (u-t)(u+t)

et donc en particulier u+t = b donne la solution u=b-t à partir de la solution t

 

Entrez $a=$ $b=$

Solutions :

 

 

Compléments

Réciprocité quadratique Symboles de Legendre et de Jacobi

Ecrire un commentaire




Quelle est la dernière lettre du mot qejzqe ? :