Теорема. Если n натуральное число равное сумме двух квадратов, то существует алгоритм, который определяет это.

Действительно, алгоритм состоит в использовании обычного калькулятора. для этого мы из заданного числа n вычитаем последовательные квадраты 1, 4, 9, и так далее до тех пор, пока не получим полный квадрат. Таким образом, наш алгоритм предполагает после вычитания очередного квадрата проверку является ли полученный результат квадратом. Если результат является квадратом, то наше заданное число n является суммой двух квадратов.