Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2k+t– 2s' - s" < а = 2k.

Отсюда получаем:

s" > 2k+t– 2s' - 2k,

и, так как t >= 1:

s" > 2k– 1s' - 2k,

s = s's" > 2k– 1s'2– 2ks = 2k– 1s' (s' - 2).

Вследствие р = s2t < а = 2k выводим s < 2k– t <= 2k– 1.

Объединим два полученных неравенства:

2k– 1s' (s' - 2) < x < 2k– 1, поэтому s' (s' - 2) < 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2k+t– 2, v = s,

b = u– v = 2k+t– 2– s < а = 2k,

s > 2k+t– 2– 2k.

Так как s < 2k– t, то t должно быть таким, чтобы

2k– t > 2k+t– 2– 2k.

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2k– t– s = a/2 - p/2.

Следовательно, если 2b = а– p, то n — квадрат числа (а + p)/2 = а– b.

При t = 2 имеем

p = 4s, b = 2k– s = a– p/4.

Следовательно, если p = 4(a– b), то n — квадрат числа a + p/4 = 2а– b.

Этим исчерпываются случаи, когда n может быть полным квадратом.

Можно спросить себя, могут ли эти различные случаи действительно осуществляться. Заметим, что при вступлении в цикл у нас b = 1, a = 4. После этого b может быть изменено добавлением а, т. е. кратным числа 4. Следовательно, b остается сравнимым с 1 по модулю 4. В трех возможных случаях:

p = 0, r = b,

p = а– 2b, r = a– b,

p = 4 (a– b), r = 2a– b,

первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство

b = ар + b2

с учетом соотношений p < a, b < a дает n < 2a2 и, следовательно, при выходе из цикла a2 > n/2. Равенство