Ceci est une équation de Pell de forme générale x² - Dy² = 1
Comme on ne voit pas de solution évidente, nous allons utiliser l'algorithme général
(algorithme PQa)
| U0 = 0 | V0 = 1 | a0 = 3 | P0 = 3 | Q0 = 1 | ||||
| U1 = 3 | V1 = (13 - 9)/1 = 4 | a1 = E[(3 + 3)/4] = 1 | P1 = 4 | Q1 = 1 | ||||
| U2 = 4 - 3 = 1 | V2 = (13 - 1)/4 = 3 | a2 = E[(3 + 1)/3] = 1 | P2 = 7 | Q2 = 2 | ||||
| U3 = 3 - 1 = 2 | V3 = (13 - 4)/3 = 3 | a3 = E[(3 + 2)/3] = 1 | P3 = 11 | Q3 = 3 | ||||
| U4 = 3 - 2 = 1 | V4 = (13 - 1)/1 = 4 | a4 = E[(3 + 1)/4] = 1 | P4 = 18 | Q4 = 5 | ||||
| U5 = 4 - 1 = 3 | V5 = (13 - 9)/4 = 1 | V5= 1 => stop | ||||||
L'indice 5 étant impair, (18,5) est solution de x² - 13y² = -1.
La solution fondamentale de x² - 13y² = 1 est x = 18² + 13×5² = 649, y = 2×18×5 = 180
et l'armée de Harold est de 13y² = 421200 hommes.
Les solutions plus grandes n'étant pas raisonnables, inutile de les calculer....
Une autre façon de voir cet algorithme est une succession de changement de variables connue sous le nom de "méthode anglaise"
x² - 13y² = 1, x/y = t à peu près solution de t² - 13 = 0 soit t ≈ 3,
posons x = 3y + z
-4y² + 6yz + z² = 1, y/z à peu près solution de -4t² + 6t + 1 = 0, t ≈ 1,
posons y = z + a
3z² - 2az - 4a² = 1, t ≈ 1, posons z = a + b
-3a² + 4ab + 3b² = 1, t ≈ 1, posons a = b + c
4b² - 2bc - 3c² = 1, t ≈ 1, b = c + d
-c² + 6cd + 4d² = 1, t ≈ 6, c = 6d + e [*]
4d² - 6de - e² = 1, t ≈ 1, d = e + f
-3e² + 2ef + 4f² = 1, t ≈ 1, e = f + g
3f² - 4fg - 3g² = 1, t ≈ 1, f = g + h
-4g² + 2gh + 3h² = 1, t ≈ 1, g = h + i
h² - 6hi - 4i² = 1 dont la plus petite solution (évidente) est h = 1, i = 0
donc g = 1, f = 2, e = 3, d = 5, c = 33, b = 38, a = 71, z = 109, y = 180, x = 649.
Soit x² = 421201 hommes, y compris Harold.
En fait on peut s'arrêter à [*] -c² + 6cd + 4d² = -1, avec c = 1, d = 0 comme solution évidente,
et en remontant :
b = 1, a = 2, z = 3, y = 5, x = 18 comme solution de x² - 13y² = -1,
puis en déduire comme ci-dessus la solution de x² - 13y² = +1 avec l'identité
(x² - Ay²)² = (x² + Ay²)² - 4Ax²y² :
Si (X, Y) est solution de x² - 13y² = -1, alors (X² + 13Y², 2XY) est solution de x² - 13y² = (-1)² = +1