В начале а = 4, p (целая часть дроби (n– 1)/4) четно, b = 1, так что ар + b2 = n.

Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a, b, p к a', b', p' либо

b' = b, а' = 2*а, так что если b < а, то и b' < а';

либо

b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.

Следовательно, вот ситуация, которую цикл оставляет инвариантной:

n = а*p + b2;

а — степень двойки,

p четно,

b нечетно, b < а.

Кроме того, мы знаем, что при выходе из цикла p < а.

Если p равно нулю, то n = b2. Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r2 (r нечетно). Соотношение

r2 = ар + b дает

r2– b2 = ар.

Положим r + b = 2u, r– b = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2t, где s нечетно, a t >= 1 (p четно).

Напомним, что а = 2k. В этих обозначениях 4uv = ар = s2k+t, uv = s2k+t– 2.

Возможные решения для пары u, v имеют вид пар

s'2k+t– 2, s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t >= 1 имеем k– t <= k + t– 2.

Вследствие p < а последовательно выводим

s2t < 2k,

s's"2t < 2k.

s's" < 2k– t <= 2k+t– 2 <= s'22k+t– 2

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2k+t– 2, v = s".