Задача: арифметическая прогрессия задаётся целыми числами a0 — первый член и d — шаг. Требуется найти количество чисел прогрессии, являющихся полными квадратами других целых чисел.
Рассмотрим 3 случая:
- d > 0
- d = 0
- d < 0
1. d > 0.
Покажем, в каком случае в прогрессии содержится хотя бы одно число, являющееся квадратом некоторого целого числа.
Перепишем в следующем виде:
и вычтем целые части из левой и правой сторон:
Ввиду свободы выбора r, величина r mod d может принимать значения 1..d-1. r2 mod d = (r mod d)2 mod d. Таким образом, если существует такое r, что (r2 mod d − a0 mod d) = 0, (или, что то же самое, r2 mod d = a0 mod d), то в последовательности существует бесконечно много чисел, являющихся квадратами целых чисел (пояснение см. далее), в противном случае, таких чисел в последовательности нет.
Итак, если существует такое целое число r, что r2 mod d = a0 mod d, то (r+d)2 так же является членом этой арифметической прогрессии, и следовательно число полных квадратов в прогрессии бесконечно.
Например, рассмотрите две следующие последовательности:
- a0 = 3, d = 5
- a0 = 2, d = 3
Продемонстрирую на первой. Остатки от деления любого числа r на 5 могут принимать значения 0, 1, 2, 3, 4. Остатки от деления числа r2 на 5 соответственно: 0, 1, 4, 4, 1. Если выбрать a0 таким образом, чтобы a0 mod d − {0,1,4} не делилось на d нацело (то есть a0 mod d должно равняться 2 или 3), то в последовательности не будет ни одного числа, являющегося полным квадратом.
2. d = 0
В этом случае всё просто — последовательность состоит из одного и того же числа. Если оно является квадратом какого-то целого числа, то таких чисел в последовательности бесконечно много, в противном случае, ни одного.
3. d < 0
Аналогично случаю 1 лишь с той разницей, что чисел не может быть бесконечно много, так как величины, меньшие 0, не могут являться квадратами каких бы то ни было целых чисел.
Метки: лемма, математика, олимпиады
