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$
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
Solutions :
Compléments
Réciprocité quadratique Symboles de Legendre et de Jacobi