Je n'ai pas la solution mais voici mon petit grain de sable :

Si n²+1 est multiple de p alors n est une racine carré de -1 modulo p.
Il faut prouver que si p est un nombre premier congru à 1 modulo 4 alors -1 a une racine carrée modulo p.

Soit m tel que m*m = -1 modulo p alors nécessairement (-m)*(-m) = m*m = -1 modulo p et (-m)  = p-m modulo p est aussi une racine carrée.

Les deux racines sont de parités différentes parce que p est impair : m+(p-m) = p.

Il est a noter que si ceci marche  pour p premier, ce n'est pas vrai pour tous les nombres congru à 1 modulo 4 et donc le fait que p soit premier est important.

Bonjour,

 Cliquez pour afficher

je cite :
il y plusieurs façons de démontrer ce résultat. Une des plus rapides fait appel au théorème de Wilson
qui exprime que pour tout nombre premier p on a (p-1)! ≡ -1 mod p

 Cliquez pour afficher

si p impair = 2m+1 alors
(p-1)! = (1.2.3...m)(p-m),(p-m+1)...(p-1) ≡ (1.2.3...m)(-m)(-(m-1)) ... (-1) ≡ (-1)^m (m!)^2 mod p
si m est pair = 2k, c'est à dire p = 4k+1, cela donne (p-1)! ≡ (m!)^2 mod p
or (Wilson) (p-1)! ≡ -1 mod p
donc (m!)^2 ≡ -1 mod p
ceci exprime que p divise (m!)^2 + 1 = n^2 + 1

évidemment on n'utilisera pas cette méthode pour trouver le plus petit n tel que p divise n^2 + 1 !

mathafou

Pour "voir" un peu, j'avais cherché le plus petit n pour certaines valeurs de p : 5, 13, 17, ..., 61 et enfin 229 , 277 , 2017 .

 Cliquez pour afficher

Pour p =229 , n = 107 .
Pour p =277 , n = 60 .
Pour p =2017 , n = 229 .

une fois l'existence démontrée, il y a des algorithmes "efficaces" pour les trouver : l'algorithme de Tonelli et Shanks.
j'étais persuadé d'en avoir une copie dans mes documents mais je ne le retrouve pas
peut être disparu dans mon feu précédent PC.
il faudra chercher sur Internet...

à noter aussi un résultat important :
une fois qu'on a trouvé n tel que p divise n² + 1
on peut en déduire les nombres (entiers) a et b uniques tels que p = a² + b²
ceci est une autre histoire (une histoire de division Euclidienne dans les entiers de Gauss Z[i] par exemple)

Merci mathafou pour la référence vers l'algorithme, ça faisait un bout de temps que je cherchais quelque chose comme ça

L'algorithme peut être grandement simplifié puisqu'on ne cherche pas la racine de n'importe quel résidu  mais la racine de -1. Une fois qu'on a trouvé le 'z' on a fini...

def solve(p) :
   """ If p is a prime such that p = 1 (mod 4), find n in [1...(p-1)/2] such that n²+1 = 0 (mod p) """
   # There is (p-1)/2 z such that pow(z,(p-1)//2,p) == p-1 (roughly half), find one. Could be randomized.
   z = 1
   while pow(z,(p-1)//2,p) != p-1 :
      z += 1
   n = pow(z,(p-1)//4,p)
   return min(n,p-n)

Bonjour,
@LittleFox,
Ce serait sympa d'expliquer un peu ton programme pour les non initiés dont je fais partie

Petite explication

On sait que pour premier, . De plus la moitié des a entre 1 et p-1 donne -1, l'autre moitié donne 1.
En effet ce sont les racine de (fermat).
Pourquoi ils sont moitié/moitié? Je ne retrouve pas mes sources mais c'est le cas .

Donc il est facile de trouver un tel . Il suffit de tester, on a une chance sur deux. En cherchant au hasard il faut en moyenne en tester deux.

Comme par hypothèse , est entier et est une racine de -1 modulo p.
Il n'y a que deux racines et . On retourne la plus petite des deux.

Voilà, j'espère que c'est plus clair .

Merci pour cette réponse rapide !
Erreur 503 a encore sévi avant que je puisse répondre

Citation :
J’ai essayé en factorisant a^4q 1 [p] . Je n'ai rien trouvé.

Le passage ne marche que parce que p est premier.

Sinon il peut y avoir d'autres racines. 2 exposant le nombre de facteurs premiers?
Par exemple .

Oui, si p est premier, on a une structure de corps. La règle du produit nul peut s'utiliser.
Mais aucun moyen de prévoir si c'est un + ou un - dans a^2q 1 [p] .

Bonjour,

dans , l'équation possède exactement deux solutions (1 et ) quand ou avec nombre premier impair et .

Plus généralement si avec impair possédant diviseurs premiers, le nombre de solutions de l'équation est égal à si ou , à si et à si .

Bonsoir,
@LittleFox