Bonjour,

PS
il y a une et une seule solution dans ² avec 0 < x < y
cela donne 8 solutions dans ²

oui, jai vu sur un forum que cest la fonction d'un cercle ou quelque chose de ce genre.
en fait je ne cherche pas la force brute, bien que le résultat soit important et tes techniques supers intéressantes. mais cest que je résoud un exo d IMO et cest la dernière étape qu il me reste à franchir (chuis en seconde donc je connais pas grand chose) cest pour ça que je doit trouver la meilleur technique possible, pour , si jamais je suis choisi, avoir le maximum de notes ^^

en fait ce sera plus la fonction d un demi-cercle que celle d un cercle

Si je comprends bien tu cherches sur ce cercle (demi cercle / quart de cercle) juste les points à coordonnées entière en fait

à moins d'utiliser l'algo que je t'ai donné (Legendre, l'autre est trop lent) et alors tu auras du mal à le justifier, la méthode la plus simple pour toi c'est "la force brute" :

tu essayes systématiquement
x = 1, y = racine de (1009 - x²) = racine (1008) pas entier
x = 2, y = racine de (1009 - x²) = racine (1005) pas entier
x = 3, idem
... etc
jusqu'à
x = racine carrée de (1009/2) = 22 (en nombres entiers)

au bout d'une quinzaine d'essais tu tomberas sur la solution unique pour x > 0
prouver qu'elle est unique va te faire continuer jusqu'à x = 22.

il n'y a pas d'autre méthode que les algorithmes ou la force brute.
(justifier qu'il suffit de s'arrêter à x = 22 par l'échange de x et y, donc on se contente de chercher x < y)

en fait je crois plutot qu on peut continuer jusqu a 31, parceque 31²=961 et 32²=1024 donc trop grand. pour x=31 on a y=48, pas un carré parfait, mais ça n empeche pas qu il yait des carrés parfaits pour x entre 22 et 31
pour la force brute, on peut aussi nous limiter au nombres paires ou aux nombres impaires, ce qui divise par 2 le nombre de calculs à faire, parce que c et y sont de paritée différente.
qu en penses tu?

par exemple le couple (28;15) est une réponse, mais 28>25.
comme on a les nombres au carré, ça change un peu, je crois.

ok merci pour l'aide, ceci m'aide beaucoup ^^

en fait un ami m a parlé d une façon de la résoudre avec les modulos. je sais que c est possible pour celles du 1er de gré, mais pour cela est ce possible?
et remerci

demandes lui sa méthode

je citais vaguement l'algorithme de Cornacchia (après vérif de l'orthographe)
C'est effectivement "the" algorithme efficace pour ça (dès que le nombre à décomposer devient grand)
il utilise effectivement des congruences et on commence par chercher en tirant au sort !! on a à chaque essai aléatoire 1/2 de tomber juste donc 1/2 de rater au premier coup, 1/4 au 2ème, 1/8 au 3ème etc 1/2ⁿ au nième essai, de sorte que dans la pratique un nombre d'essais "assez faible" permet de tomber pile (s'ils sont vraiment aléatoires)
Ce qu'on cherche avec ça ?

un nombre r₀ tel que r₀² -1 modulo N
ensuite on trafique l'algorithme d'Euclide, en cascade, pour trouver une suite de r_i avec
r₁ N mod r₀
r₂ N mod r₁
etc ...
en s'arrêtant quand r_k < N
x = r_k et y = (N - x²) si y entier
(sinon il n'y a pas de solution)

bref la complication de cet algorithme ne vaut le coup (coût) que vraiment pour de grands nombres (tels que M soit de plusieurs milliers)
sinon la force brute sera plus efficace !

de la doc utile sur ces sommes de carrés là : (c'est en anglais) où on trouve un script pour obtenir la décomposition d'un nombre quelconque en somme de carrés (liens au même endroit)

Merci pour ton aide, tout cela mais été vraiment utile ^^ je noterais toute ces techniques, on ne sait jamais quand on en aura besoin :p

amicalement: Anas