Calcul d'une congruence
dans Arithmétique
Bonjour,
On sait que si $p\equiv 1 \pmod 4$ alors $p$ est somme de deux carrés.
Dans 'Thèmes d'arithmétique' d'Olivier Bordellès, un exercice introduit l'algorithme de Serret pour déterminer $a$ et $b$ tels que $p=a^2+b^2$.
En gros, il faut effectuer l'algorithme d'Euclide avec $p$ et $x$, où $x$ est le représentant modulo $p$ de $\left(\dfrac{p-1}{2}\right)!$ compris entre 0 et $p-1$.
Ma question est donc : comment déterminer ce représentant ?
Merci et bonne année à tous.
On sait que si $p\equiv 1 \pmod 4$ alors $p$ est somme de deux carrés.
Dans 'Thèmes d'arithmétique' d'Olivier Bordellès, un exercice introduit l'algorithme de Serret pour déterminer $a$ et $b$ tels que $p=a^2+b^2$.
En gros, il faut effectuer l'algorithme d'Euclide avec $p$ et $x$, où $x$ est le représentant modulo $p$ de $\left(\dfrac{p-1}{2}\right)!$ compris entre 0 et $p-1$.
Ma question est donc : comment déterminer ce représentant ?
Merci et bonne année à tous.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
https://numerisation.irem.univ-mrs.fr/WR/IWR08017/IWR08017.pdf
(ce sont les annexes qui sont intéressantes concernant ta question, me semble-t-il)
Norbert Verdier, spécialiste d'histoire des mathématiques, revient parfois ici et écrit régulièrement dans Tangente et Quadrature (sauf erreur).
#Chaurien : avec $p=9733$ c'est un peu fastidieux...
Une indication supplémentaire $x^2\equiv -1 \pmod p$ où $x$ est celui défini précédemment.
Drôle d'objection. Bien sûr il ne s'agit pas de faire ça à la main avec un crayon. Avec n'importe quel langage de programmation on peut faire 4000 et quelques multiplications en une fraction de seconde. Moi j'utilisais le Turbo-Pascal mais malheureusement ça ne tourne plus sur mon ordinateur actuel. Le seul problème avec la factorielle c'est le dépassement de capacité car les entiers du langage ont une taille maximum au-delà de laquelle le calcul ne se fait plus exactement. Mais si l'on réduit modulo $p$ à chaque multiplication, ça va, notamment pour 9733 c'est trivial.
Bonne soirée.
Fr. Ch.
oui j'entends bien que cela se fait aisément par ordinateur, mais j'aurais voulu savoir s'il existait un raisonnement permettant de trouver $x$ "à la main" quelle que soit la taille de $p$.
$a=20465965227875381255062502347819060893534196379856534570181587967444063900712398554264818392926750859254\\0145778835184878966523745865787030965687335387$
$b=24106934008525343657235686663019339703125173036807293439785501900983305007359047195283735658068255462114\\7459119716927561540809178220753331351249088530$.
J'utilisais l'algorithme de Serret mais pour le calcul de $x$ je n'utilisais évidemment pas le calcul de $\Big(\dfrac{p-1}{2}\Big)\,! \mod p$.
Pour trouver $x$ tel que $x^{(p-1)/2}\equiv -1\pmod p$ on peut, en utilisant la loi de réciprocité quadratique, rechercher un nombre premier $x$ tel que $p^{(x-1)/2}\equiv -1\pmod x$, ce qui est très rapide. C'est ce que fait la fonction Maple "sum2sqr".
Il y a un article expliquant cela, paru dans la RMS en janvier 1999 : Divisibilité et somme de deux carrés.
beaucoup moins ambitieux, on obtient avec l'algorithme de Serret et en calculant $\left(\dfrac{p-1}{2}\right)!$ avec Python en réduisant chaque facteur modulo $p$ :
$$9733=18^2+97^2$$