Участник:LGB/Черновик: различия между версиями
Содержимое удалено Содержимое добавлено
LGB (обсуждение | вклад) ← Содержимое страницы заменено на «=== Определение, является ли заданное число многоугольным === '''З...» Метка: замена |
LGB (обсуждение | вклад) Нет описания правки |
||
Строка 1:
=== Определение, является ли заданное число многоугольным ===
'''Задача 1''' (задача Диофанта): дано натуральное число <math>N>2</math>. Определить, является ли оно многоугольным числом <math>P^{(k)}_n</math> и если да, то для каких <math>k</math> и <math>n</math>. Диофант сформулировал эту проблему так: «''выяснить, сколько раз данное число встречается среди всевозможных многоугольных чисел''»
Решение задачи Диофанта сводится к решению уравнения (см. {{Eqref|ОКФ|общую формулу}}):
: <math>N = P^{(k)}_n = \frac{(k-2)n^2 - (k-4)n}{2},</math> или: <math>2N - 2n = (k-2)(n^2 - n).</math>
Перепишем полученное уравнение в виде: <math>k-2 = \frac{2N-2}{n-1} - \frac{2N}{n}</math>
Знаменатели дробей справа [[Взаимно простые числа|взаимно просты]]; сумма или разность таких дробей может быть целым числом только если каждая дробь есть целое число<ref>В самом деле, пусть <math>\frac{a}{n_1} + \frac{b}{n_2}</math> (все числа целые) есть целое <math>K,</math> причём <math>n_1, n_2</math> взаимно просты. Умножая обе части на <math>n_1,</math> получим: <math>\frac{b n_1}{n_2} = Kn_1 - a.</math> Справа — целое число, поэтому <math>n_2</math> делит <math>b n_1,</math> и согласно [[Лемма Евклида|обобщённой лемме Евклида]], <math>n_2</math> делит <math>b.</math></ref>, поэтому <math>2N-2</math> кратно <math>n-1,</math> а <math>2N</math> кратно <math>n.</math>
В результате алгоритм решения приобретает следующую форму{{sfn |Деза Е., Деза М.|2016|с=37—38|name=DD37}}:
# Выписать все натуральные [[Делитель|делители]] числа <math>2N</math> (включая <math>1</math> и само <math>2N</math>).
# Выписать все натуральные делители числа <math>2N-2.</math>
Строка 6 ⟶ 14 :
# Для каждого отобранного <math>n</math> подсчитать <math display="inline">k=\frac{2N-2}{n-1} - \frac{2N}{n} + 2</math>.
# Вычеркнуть пары <math>(n,\;k)</math>, в которых <math>k<3</math>.
Тогда все соответствующие оставшимся парам числа <math>P^{(k)}_n</math> равны <math>N.</math>
'''Пример'''<ref name=DD37/>. Пусть <math>N=105</math>.
Строка 17 ⟶ 25 :
'''Задача 2''': дано натуральное число <math>N>2,</math> требуется определить, является ли оно ''<math>k</math>''-угольным числом <math>P^{(k)}_n</math>. В отличие от задачи 1, здесь <math>k</math> задано.
Для решения можно использовать ''тождество Диофанта''{{sfn |Деза Е., Деза М.|2016|с=
: <math>8(k-2)P^{(k)}_n + (k-4)^2 = (2n(k-2) - (k-4))^2</math>
Это тождество получается из приведенной выше {{Eqref|ОКФ|общей формулы для <math>P^{(k)}_n</math>}} и равносильно ей. Из тождества вытекает решение: если <math>N</math> есть <math>k</math>-угольное число, то есть <math>N=P^{(k)}_n</math> для некоторого <math>n,</math> то <math>8(k-2)N + (k-4)^2</math> есть некоторое квадратное число <math>R^2</math>, и обратно. При этом номер <math>n</math> находится по формуле<ref name=DD39/>:
| |||