L'énoncé était, rappelons le:

7901 est premier et est égal à 85²+26².
Trouver le plus petit entier x tel que:
7901*x=1+4n², n étant entier naturel. A la main bien entendu.
Pour les plus courageux: prouver que x existe pour tout nombre premier impair somme de 2 carrés.

Solution rapide:
p=a²+b² dont on cherche un multiplicateur
q=c²+d² ce multiplicateur ! car
pq= (ac+bd)²+(ad-cb)² ou (ac-bd)²+(ad+cb)²=1²+(2n)²
Comme on cherche un pq=1+4n², et qu'on sait qu'il existe le couple (c,d) tel que ac-bd=1 mais aussi ac-bd=-1, car a et b sont premiers entre eux, il n'y a plus qu'à trouver (c,d).

Quand on a un couple a,b premiers entre eux, on sait que tous les restes de n*a modulo b, n<a, donneront b-1 restes différents, dont bien entendu 1 et -1 ( ou b-1). L'égalité n'intervient que pour a*b=b*a. (c,d) seront donc plus petits que (a,b), et par conséquent q aussi.

Cherchons (c,d)
85c-26d=1
26(3c-d)+7c=1
26e+7c=1
7(3e+c)+5e=1
7f+5e=1
Une solution est e=3 et f=-2
3e+c=f
c=f-3e=-11 ou 15 modulo 26
e=3c-d
d=3c-e=-36 ou 49 modulo 85

Comme il faut q impair, on prend le couple (-11,-36) car la somme des carrés est impaire.
x=q=11²+36²=1417 et n=1673.

1+4n²=0 modulo 7901 pour n=1417 et aussi pour tout n=7901k + ou-1417.

Etant donné qu'on a cherché le seul couple (c,d) <(a,b) tel que ac-bd=1 et avec c²+d² impair, c'est le plus petit.

Cette méthode généralise de facto l'existence de x( ou q) pour tout p somme de 2 carrés.

Cette question a été inspirée par l'étude des nombres de la forme 1+4n². On sait maintenant que tous les nombres premiers de la forme 4n+1 divisent les nombres 1+4n².  Ce sont d'ailleurs les seuls.

Bravo à Promath et Papiauche qui ont su résoudre en totalité ou en partie cet épineux problème d'arithmétique, avec tous les deux une démarche presque identique et plutôt sophistiquée. Merci aux autres intervenants qui ont vite trouvé la solution particulière et aussi aux autres qui ont cherché.

Très bien, très bien, très bien

Pas mécontent d'avoir vu pas mal de choses:
- la question de la parité,
- l'utilisation de l'identité de Bezout, nettement plus performante avec a et b qu'avec a (ou b) et p.
- le choix du multiplicateur avec ma deuxième solution.

Sur la démo prouvant qu'on a bien obtenu le plus petit, je comprends le principe général, mais il faut que je métabolise.

Une question me vient:

nodgim a écrit:

Cette méthode généralise de facto l'existence de x( ou q) pour tout p somme de 2 carrés.

Si un nombre premier est somme de deux carrés, les nombres sont nécessairement premiers entre eux.

La formulation de la généralisation porte-t-elle sur:

un nombre premier somme de deux carrés,
ou celle (apparemment moins restrictive) d'un nombre somme de deux carrés de nombres premiers entre eux.

De mon point de vue, c'est la seconde:
7801 n'est pas premier = 13*269

7801= =85^2+24^2

Avec la méthode de résolution:

q = 2285
n = 2111

P.S. Je ne voyais pas comment utiliser le fait que p était premier dans ma seconde approche.