Леммы


Задача: арифметическая прогрессия задаётся целыми числами a0 — первый член и d — шаг. Требуется найти количество чисел прогрессии, являющихся полными квадратами других целых чисел.

Рассмотрим 3 случая:

  1. d > 0
  2. d = 0
  3. d < 0

1. d > 0.

Покажем, в каком случае в прогрессии содержится хотя бы одно число, являющееся квадратом некоторого целого числа.

a0 + n⋅d = r2
n = (r2 − a0) ∕ d, при этом все числа целые

Перепишем в следующем виде:

n = (r2) ∕ d − a0 ∕ d

и вычтем целые части из левой и правой сторон:

0 = r2 mod d − a0 mod d

Ввиду свободы выбора 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, не могут являться квадратами каких бы то ни было целых чисел.

Реклама

Метки: , ,

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s


%d такие блоггеры, как: