17:10 

Делимость

wpoms.
Step by step ...


Существует ли бесконечно много пар натуральных чисел `(m,n)`, для которых `n^2 + 1` кратно `m`, а `m^2 + 1`кратно `n`?



@темы: Теория чисел

Комментарии
2015-10-03 в 04:50 

Ответ на вопрос задачи утвердительный.

С помощью несложной программы на Java были найдена некоторые пары натуральных чисел, не превышающие 100000, которые удовлетворяют условию задачи:

public class eek {
public static long MAX = 100000;
public static void main(String[] args) {
for (long i = 1; i <= MAX; i++)
for (long j = 1; j <= i; j++)
if ((i * i + 1) % j == 0 && (j * j + 1) % i == 0)
System.out.println("i="+i+" and j="+j);
}
}
По завершению, программа вывела:
i=1 and j=1
i=2 and j=1
i=5 and j=2
i=13 and j=5
i=34 and j=13
i=89 and j=34
i=233 and j=89
i=610 and j=233
i=1597 and j=610
i=4181 and j=1597
i=10946 and j=4181
i=28657 and j=10946
i=75025 and j=28657

Cоставим из них (конечную) последовательность a=(1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025)
Нетрудно видеть, что члены последовательности удовлетворяют рекуррентному соотношению:
a[0] = a[1] = 1 и
a[i+2] = 3*a[i+1]-a[i] для i=0..11.

Также заметим, что (a[i+1]^2+1)/a[i+2] = a[i] для тех же значений индекса i=0..11.

Покажем, что для всех целых неотрицательных значений i в бесконечной последовательности {a[i]}, заданной тем же рекуррентным соотношением, соседние члены также удовлетворяют условию задачи.

1. Докажем индукцией по i , что a[i] | a[i+1]^2+1 (символ вертикальная черта | означает отношение "делит нацело")
База индукции i=0 доказывается тривиально: a[0]=1 делит нацело a[0+1]^2 + 1 = 2.
Шаг индукции. Считаем предположение индукции доказанным для всех 0<=i<n: a[i] | a[i+1]^2 + 1.
Докажем утверждение для i=n: a[n] | a[n+1]^2+1
Действительно, a[n+1]^2 + 1 = (3*a[n]-a[n-1])^2 + 1 = 9*a[n]^2-2*3*a[n]*a[n-1]+(a[n-1]^2 + 1).
В силу того, что a[n] | 9*a[n]^2 и a[n] | 2*3*a[n]*a[n-1] и a[n] | a[n-1]^2 + 1 (по предположению индукции), то a[n] | a[n+1]^2 + 1. Что и требовалось доказать.

1. Для доказательства a[i+1] | a[i]^2+1 докажем индукцией по i равенство a[i+1]^2+1 = a[i]*a[i+2].
База индукции i=0 доказывается тривиально: a[0+1]^2+1 = a[0]*a[0+2] = 2.
Шаг индукции. Считаем предположение индукции доказанным для всех 0<=i<n: a[i+1]^2+1=a[i]*a[i+2].
Докажем утверждение для i=n: a[n+1]^2+1=a[n]*a[n+2].
Действительно, a[n]*a[n+2]=
=a[n]*(3*a[n+1]-a[n]) // т.к. a[n+2]=3*a[n+1]-a[n] по определению.
=3*a[n]*a[n+1]-a[n]^2 // просто выполнили умножением
=3*a[n]*a[n+1]-(a[n-1]*a[n+1]-1) // попользовались предположением индукции a[n]^2+1 = a[n-1]*a[n+1], откуда a[n]^2=a[n-1]*a[n+1]-1
=3*a[n]*a[n+1]-a[n-1]*a[n+1]+1 // просто раскрыли скобки
=a[n+1]*(3*a[n]-a[n-1])+1 // вынесли общий множитель a[n+1] за скобки
=a[n+1]*a[n+1]+1 // воспользовались рекуррентным определением последовательности a[n+1]=3*a[n]-a[n-1]
=a[n+1]^2+1.
Что и требовалось доказать.

Таким образом, для всех целых неотрицательных i справедливо: a[i]*a[i+2]=a[i+1]^2+1, откуда следует истинность второго условия задачи для последовательность {a[i]}:
a[i+1] | a[i]^2+1.

В итоге, бесконечное (счетное) множество пар соседних членов последовательности {(a[i], a[i+1])} - пример искомого множества.

2015-10-03 в 11:44 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
beubeff, Нетрудно видеть, что члены последовательности удовлетворяют рекуррентному соотношению: a[0] = a[1] = 1 и a[i+2] = 3*a[i+1] - a[i] для i=0..11.
:) ... круто...
...

2015-10-03 в 18:15 

All_ex,

1. Комментарий про фразу из решения:
"Нетрудно видеть, что члены последовательности удовлетворяют рекуррентному соотношению: a[0] = a[1] = 1 и a[i+2] = 3*a[i+1] - a[i] для i=0..11."

Действительно не трудно видеть, что найденная компьютером конечная последовательность a=(1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025) демонстрирует "приблизительно" линейный порядок роста соседних членов: z[i+1]=k*z[i]+b. Далее, попытаемся подобрать натуральный коэффициент k. Кандидаты k=1 или k=2 осмысленного результата не дают. Для k=3 видно, что на месте постоянной b возникают те же члены последовательности, но с противоположным знаком и "запаздыванием" индекса на 2. Таким образом, была найдена рекуррентная формула.

Кстате, то же "запаздывание" индексов открывается, если начать выписывать целочисленные частные (a[i+1]^2+1)/a[i+2] для указанного начального отрезка последовательности.

2. Совершенно справедливо замечание про представимость последовательности {a[i]}, удовлетворяющей линейному рекуррентному уравнению второго порядка, в виде суммы двух подходящих геометрических прогрессий (см. пример из статьи в Википедии про линейную рекуррентную последовательность). Однако, ее характеристическое уравнение q^2-3q+1=0 имеет иррациональные корни, что может привести к громоздким выкладкам при доказательстве, например, свойства a[i+1] | a[i]^2+1. Поэтому, я счел нецелесообразным пользоваться альтернативным представлением последовательности.

2015-10-03 в 18:22 

Trotil
All_ex, для это есть поисковик.

2015-10-03 в 19:09 

Trotil,
Спасибо за ссылку.
Там же в списке фактов про эту последовательность нашел такое упоминание:
"1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014"

Хотя я все искал и доказывал без помощи Google.

2015-10-03 в 20:35 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
beubeff, ... найденная компьютером ...
Trotil, для это есть поисковик.
Даже то, что это задача из олимпиады 2012-2013 года не даёт мне возможности надеяться, что было позволено пользоваться вычислительным экспериментом и поисковиками ... :upset:

beubeff, 2. Совершенно справедливо замечание ... - :shuffle2: ... ну, это было не замечание, а ... :upset: ... даже не знаю как обозвать эту спрятанную под кат фразу ...

Вот интересно, как выглядит авторское решение... :upset:
Ведь надо было сделать предположение, что это пары некоторой последовательности... придумать её способ описания... (хотя может есть какое-то "стандартное олимпиадное" рассуждение, которое мне не ведомо... ведь олимпиоником такого уровня я никогда не был ... ) ...
Там же в списке фактов про эту последовательность нашел такое упоминание: "1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014" - а ведь это уже после олимпиады... :upset:

2015-10-03 в 20:53 

Trotil
что было позволено пользоваться вычислительным экспериментом и поисковиками ...

для таких задач (исследовательского плана) - вполне нормальный подход, я считаю.

2015-10-03 в 21:07 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Trotil, вполне нормальный подход, я считаю. - дома - да... но это же была олимпиада по математике... :upset: ... так что слабо верится ... :nope:

2015-10-04 в 00:52 

Олимпиада-неолимпиада неважно. Задача сформулирована. Решение опубликовано. Решение корректно. Мог бы умолчать про джаву и написать что-то вроде:
"поробуем найти некоторые такие пары. Для начала поищем те из них, в которых первое число равно 1, получаем (1, 1) и (1, 2). Найдем пару в которой одно из чисел равно 2. Получаем (2, 5). Аналогично для 5 получаем (5, 13). И т.д. (13, 34). Раворачивается последовательность. Попробуем подобрать формулу. Дальше по тексту". beubeff

URL
2015-10-04 в 01:08 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
beubeff, спасибо за решение и его объяснение ...
...

2015-10-04 в 01:32 

На самом деле, рекуррентную формулу подобрал не удивление быстро (погуглить последовательность честно говоря не догадался).
Также почти очевидным было доказательство свойства a[i] | a[i+1]^2+1.
Затруднение вызвало доказательство второго свойства a[i+1] | a[i]^2+1 (потратил около часа на тщетные усилия выразить a[i] в виде функции только от i, пока не сообразил поинтересоваться, чему же равны целочисленные частные (a[i]^2+1)/a[i+1] хотя бы для стартовых значений i). Признаюсь, что без компьютера бы не решил.
beubeff

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная