C'est ça Ebichu, bravo !
Comment l'as tu trouvé ? Perso, après une série d'essais....

Bien sûr, l'informatique est bien utile dans ce cas.

Justement, j'étais en train de me pencher sur le critère des autres solutions. En gros, peut-on savoir à l'avance s'il y aura plusieurs solutions possibles pour un entier donné ?

Pas si simple...

@ Klimrod : c'est bien ça, bravo !

Pour les autres solutions, je viens de trouver l'explication d'une bonne partie d'entre elles.

Voici celles que j'ai trouvées inférieures à 1000 :

5,[7]*
13,[29]*
25,[79]*
31,[49]
41,[169]*
61,[311]*
71,[169]
85,[517]*
113,[799]*
145,[1169]*
181,[1639]*
209,[337]
221,[2221]*
265,[2927]*
313,[3769]*
365,[4759]*
409,[985]
421,[5909]*
461,[1519]
481,[7231]*
545,[8737]*
613,[10439]*
685,[12349]*
761,[14479]*
841,[16841]*
925,[19447]*

À gauche, la valeur de n, et à droite entre crochets, celle de m (strictement inférieure à (n²+1)/2) .

Les solutions marquées d'une étoile sont de la forme n = (k²+1)/2 et m = (k³-k²+3k+1)/4 pour k un nombre impair >=3 : j'ai trouvé cette formule en cherchant quel polynôme pouvait bien donner ces valeurs. Et après, quand on fait les calculs, on se rend compte que oui, ça marche : (m-1)(n-1)=(n-1)²(n+1)(n²+3)/8 et (m²-n²)=(n-1)³(n+1)(n²+3)/16.

Il reste encore quelques solutions pour les courageux

Je vais arrêter là, voilà où j'en suis. Jusqu'à 2000, j'ai trouvé les solutions sporadiques suivantes (en me restreignant à m<(n²+1)/2) :
n=31 ; m=49
n=71 ; m=169
n=209 ; m=337
n=409 ; m=985
n=461 ; m=1519
n=1429 ; m=2311
n=1871 ; m=7921

Quelques questions ouvertes :
* existe-t-il un couple solution (n;m) avec m>(n²+1)/2 ?
* une valeur n peut-elle correspondre à >=3 valeurs de m ?
* peut-on faire émerger une autre famille de solutions de ces valeurs sporadiques ?

OK. J'examine une voie assez différente, je t'en parlerai quand ce sera plus mûr. En tout cas, chapeau pour ces nouveaux constats ! Je crois que toute solution particulière primitive doit pouvoir en créer une infinité d'autres.

Effectivement, je suis d'accord avec ton intuition, on peut probablement trouver une infinité de familles de solutions sporadiques. La k-ième famille correspond aux solutions entière de l'équation :
(m-1)*(n-1)*k=m²-n².

Quand je lance mon programme sur une petite valeur de k, je trouve systématiquement des solutions. Par exemple, je prends k=13, et j'obtiens
n=25 ; m=313 (solution du type (n²+1)/2)
n=365 ; m=4759 (solution liée au polynôme)
n=698021 ; m=9127639 (nouvelle solution sporadique, début de la famille)

Les familles semblent devenir de plus en plus compliquées. Par exemple, le début de la 3e famille est :
n=5 ; m=13
n=25    ; m=79
n=461 ; m=1519
n=2839 ; m=9373
n=54719 ; m=180721
n=337681 ; m=1115281
n=6510965 ; m=21504253

Les valeurs de n obéissent à la relation de récurrence u(n+2)=119*u(n)-u(n-2)-135 et celles de m à la relation v(n+2)=119*v(n)-v(n-2)-27.
J'ai l'impression que le rapport m/n converge vers (3+racine(13))/2, un petit coup de Wolframalpha devrait permettre de confirmer.

Je ne sais pas si ça vaut le coup de continuer à analyser les familles individuellement plus loin. Maintenant, il faudrait chercher une théorie générale ; mais ça devient ardu. Je peux rajouter une question supplémentaire, dont on peut conjecturer que la réponse est négative :
* existe-t-il une solution qui n'appartienne pas à une certaine k-ième famille ?

@ Ebichu : je n'ai pas pu travailler là dessus, ni hier, ni aujourd'hui, mais je ne n'abandonne pas ma propre piste, qui se résume en une seule équation relativement simple à étudier. Et qui justifie facilement la liste "deuxième niveau". 

@ Gwen: rapprochement intéressant, en effet.

Petit progrès : je conjecture que pour la k-ième famille de solutions, le quotient m/n tend vers [latex]\frac{k+\sqrt{k^2+4}}{2}[/latex]. Je l'ai vérifié pour k de 1 jusqu'à 5.

@ Ebichu :
Je dois pouvoir justifier cette relation entre k et le rapport m/n. Je vais rédiger mon idée et la transmettre, ça devrait t'éclairer.

La démarche qui m'avait mené aux solutions :

On pose m² - n² = k (m-1) ( n-1)
qui est une équation du second degré dont m est l"inconnue : m² - k ( n-1) m - n² + k (n-1) = 0

Delta1 = k² (n-1)² - 4 (n-1) k + 4 n² doit être un carré parfait A², qu'on résout à son tour par un Delta (inconnue k).

Delta' 2 = (n-1)² (4 + A² - 4 n² )

k = ( 2 (n-1) + V ( D' 2 )) / (n-1)² = ( 2 + V ( A² - 4 ( n²-1 ) ) / ( n-1)   

4 ( n² - 1 )  doit être une différence entre 2 carrés pour avoir un k rationnel.

Une différence entre 2 carrés voisins est impaire. 4 ( n² - 1 )  est une somme de différences entre carrés voisins successifs.

Exemple  n = 7 et donc  4 (n²-1) = 4 * 48 
Pour 2 * 96 : la suite des différences successives  est 95 97 et les carrés encadrants sont 47² et 49²
Pour 4 * 48 : la suite des différences successives  est 45 47 49 51 et les carrés encadrants sont 22² et 26².
Pour 8 * 24 : la suite des différences successives  est 17 19 21 23 25 27 29 31 et les carrés encadrants sont 8² et 16²
etc...

Mais ce ne sont pas que des solutions puisque 2 + V ( A² - 4 ( n²-1 )  doit être aussi divisible par n-1 pour avoir un k entier.

On peut déja simplifier en posant n ' = (n-1) /2

La formule pour k devient k = ( 1 + V ( A' ² - 4 n' (n' + 1 ) ) / n' avec A' = A / 2.

On doit donc trouver a * b = n '  ( n' +1 ) tel que a < b et  b - a + 1 (le petit carré encadrant) est divisible par n'; Dans ce cas, m aura pour valeur 2 b + 1.

Exemple
n = 71
n' = 35 (7 * 5)  et n' + 1 = 36 ( 2 * 2 * 3 * 3 )
Il faut chercher a et b en échangeant les facteurs premiers tel que b = a - 1 modulo 35.
Par tâtonnement, on trouve que a = 15 et b = 84 convient. Et m = 169. 

Par cette méthode, on voit apparaitre immédiatement une solution évidente pour tout n :
a = 1 et b = n' (n' +1 ). Modulo n', ça donne bien (1,0). Dans ce cas, m = 2 n' ( n' + 1 ) + 1.

On a aussi une autre série de solutions immédiates quand n' = a' ( a' + 1).
a = a' + 1 et b = a'  * ( n' + 1) car dans ce cas on a bien b - a + 1 = 0 modulo n'.

On trouve aussi, par une série de déductions simples, les nombres n pour lesquels une seule solution est possible :
- Lorsque n' possède un seul facteur premier (élevé ou non à une puissance donnée) dans sa décomposition.
- Lorsque n' + 1 est premier dans sa décomposition et n' n'est pas de la forme a' ( a' + 1).
- Lorsque n' ne possède que 2 et un seul autre facteur premier ( élevé ou non à une puissance donnée ) sauf si n' est 6.
- Il n'y a pas de couple (a, b) tel qu'un facteur premier de n' , présent à une puissance > 1, est distribué à la fois dans a et b.

Je crois que tu as raison, et pourtant ça marche bien ce que j'ai fait. ça doit se compenser ailleurs, mais c'est tellement embrouillé que je ne vois pas où pour l'instant. Je vais regarder tranquillement et corriger.

Sinon, l'utilisation du célèbre  " Delta " comme critère de résolution d'une équation du second degré est ici poussée au max.