Пары чисел

[Руст]

1. Найти все пары натуральных чисел а и b, для которых условие
(1)$n^2|(a^n+b^n)$
не выполняется при n>1.
2. Докажите, что если при некотором а и b условие (1) выполняется для некоторого n>1, то оно выполняется для бесконечного числа значений n.

[juna]

Что-то никто не берется. С наскока получилось следующее.
По п.1 $a,b$ - взаимнопростые. Можно показать, что в разложении суммы $(a+b)$ на простые множители не может присутствовать нечетных простых, т.е. $(a+b)=2^d$, значит $a=4k+1$, $b=4m+3$, $k+m+1=2^l$, хотя и в этом множестве могут быть ограничения.

[Руст]

Артамонов Ю.Н. писал(а):

Что-то никто не берется. С наскока получилось следующее.
По п.1 $a,b$ - взаимнопростые. Можно показать, что в разложении суммы $(a+b)$ на простые множители не может присутствовать нечетных простых, т.е. $(a+b)=2^d$, значит $a=4k+1$, $b=4m+3$, $k+m+1=2^l$, хотя и в этом множестве могут быть ограничения.

Да. Только упустили случай a+b=3.

[worm2]

Кстати, для случая a+b=3 имеем: $3^2|2^3+1$, но найти n>3 такое, что $n^2|2^n+1$ мне никак не удаётся. По крайней мере, если такое n и существует, то оно больше 40000 (если я не напортачил что-то с проверочной программой).

[Руст]

worm2 писал(а):

Кстати, для случая a+b=3 имеем: $3^2|2^3+1$, но найти n>3 такое, что $n^2|2^n+1$ мне никак не удаётся. По крайней мере, если такое n и существует, то оно больше 40000 (если я не напортачил что-то с проверочной программой).

Несложно доказать, что других не существует. Рассмотрите минимальный простой делитель числа n.

[worm2]

Руст писал(а):

Несложно доказать, что других не существует. Рассмотрите минимальный простой делитель числа n.

Но тогда получается, что утверждение

Цитата:

2. ...если при некотором а и b условие (1) выполняется для некоторого n>1, то оно выполняется для бесконечного числа значений n.

неверно. Ведь при a=2, b=1, условие (1) выполняется для n=3. Требуется доказать, что это условие выполняется (при тех же a и b) для бесконечного числа других значений n. Или я что-то неправильно понял.

[Руст]

Да, вы правы. Для этого случая надо было писать, если при n>3...

[RIP]

Попробую второй пункт.
Во-первых, очевидно, можно считать (a,b)=1.
Пусть $k=\frac{a^n+b^n}{n^2}$. Ниже будет доказано, что k имеет простой делитель p>2 (за исключением упомянутого случая {a,b}={1,2}, n=3). Тогда легко убедиться, что $n'=pn$ также обладает нужным свойством, и т.д.
Допустим, что

$$\begin{equation} k=2^{\alpha}. \end{equation}$$

Для удобства рассмотрим 2 случая.
1) $\alpha=0$, т.е. $a^n+b^n=n^2.$ Учитывая, что $3^n\geqslant n^2$ и $2^{n+1}>n^2$ при n>1, получаем, что {a,b}={1,2}, откуда легко получить n=3. Этот случай мы исключили.
2) $\alpha\geqslant1$, следовательно, a и b нечетны.
Во-первых, n нечетно, иначе $a^n+b^n\equiv2\pmod4$ и не делится на $n^2$.
$m:=\frac{a^n+b^n}{a+b}=a^{n-1}-a^{n-2}b+\ldots+b^{n-1}.$ m нечетно и делит $a^n+b^n=n^22^{\alpha}$, следовательно, $m|n^2$, в частности, $m\leqslant n^2$. Пусть для определенности b>a, тогда $b\geqslant a+2$ и $m\geqslant\frac{a^n+(a+2)^n}{2(a+1)}\geqslant\frac{3^n+1}4>n^2$ при $n\geqslant5$. Противоречие в этом случае. Для n=3 легко перебрать все решения неравенства $a^2-ab+b^2\leqslant9$ и убедиться, что для них (1) также не выполняется. Если нигде не наврал, вроде решено.

Для полноты изложения привожу доказательство того, что {a,b}={1,2} действительно исключение (док-во довольно длинное, но это первое, что пришло на ум).
Пусть n>1 и $2^n+1\equiv0\pmod{n^2}$. Тогда n нечетно. Пусть p-наименьший простой делитель n, $n=p^{\alpha}m,\ (p,m)=1.$ Тогда $2^m+1\equiv2^n+1\equiv0\pmod p$, следовательно, $2^{2m}\equiv1\pmod p$. С другой стороны, малая теорема Ферма нам говорит, что $2^{p-1}\equiv1\pmod p$, а поскольку (p-1,2m)=2 (т.к. все простые делители m больше p), то $2^2\equiv1\pmod p$,т.е. p=3. Легко доказать индукцией по $\alpha$, что $3^{\alpha+1}||2^{3^{\alpha}}+1$. Пусть $A=2^{3^{\alpha}}$, тогда $2^n+1=(A+1)(A^{m-1}-\ldots+1)$, причем второй сомножитель $\equiv m\pmod3$, след-но, $3^{\alpha+1}||2^n+1$, откуда $\alpha=1.$ Получаем $8^m+1\equiv0\pmod{m^2}.$ Повторяя рассуждения выше, получаем, что наименьший простой делитель m(если m>1) делит $8^2-1$, т.е. равен 7. Получаем $8^m\equiv-1\pmod{7}$, что нереально.

[worm2]

Вдохновлённый подсказкой Руста и идеями Артамонова Ю.Н. и RIPа, попробую добить 1-й пункт. Я буду рассуждать подробно, извините за большой объём. Основная часть решения содержится в следующей лемме:

Лемма. Пусть p>2 --- простое число, a и b --- натуральные, взаимно простые с p, n --- натуральное и $p|a^n+b^n$. Тогда существует такое натуральное r < p-1, что $p|a^r+b^r$, и r|n.
Доказательство.
(1) Пусть M --- множество всех целых $m \ge 0$, для которых $p|a^m+b^m$, r --- минимальный элемент M. Мы будем доказывать, что $M = \{r(2k-1), k \in \mathbb N\}$.
(2) r > 0, иначе было бы $p|2=a^0+b^0$, что противоречит условию p>2. Итак, r --- натуральное.
(3) По малой теореме Ферма $a^{p-1} \equiv b^{p-1} \equiv 1 (\mathrm{mod}\ p)$. Это значит, что $a^n \equiv a^q$, $b^n \equiv b^q (\mathrm{mod}\ p)$, где q --- остаток от деления n на p-1, а значит, $r \le q < p-1$.
(4) Положим $d = \min\limits_{i,j \in M;\ i \neq j}|i-j|$.
(5) Пусть $i,j \in M$ таковы, что i-j=d. Тогда $a^{i+d}+b^{i+d}$=$(a^i+b^i)(a^d+b^d)-a^d b^d (a^j+b^j)$ --- делится на p, поэтому $i+d \in M$ (см. определение M в (1)). Далее, если $j \ge d$, то $a^i+b^i$=$(a^j+b^j)(a^d+b^d)-a^d b^d (a^{j-d}+b^{j-d})$, откуда $p|a^d b^d (a^{j-d}+b^{j-d})$. Поскольку a и b взаимно просты с p, то $p|a^{j-d}+b^{j-d}$, т.е. $j-d \in M$. Если j<d, то $a^i+b^i$=$(a^j+b^j)(a^d+b^d)-a^j b^j (a^{d-j}+b^{d-j})$, откуда аналогично получаем $d-j \in M$. Итак, из $i,j \in M$, i-j=d>0 следует, что $i+d \in M$ и $|j-d| \in M$.
(6) Распространяя утверждение (5) от i и j в обе стороны числовой оси, получаем, что вся арифметическая прогрессия $\{q+d(k-1), k \in \mathbb N\}$, где q - остаток от деления i на d, входит в M.
(7) Но эта прогрессия и исчерпывает всё M, так как если бы в M был элемент не входящий в неё, то его расстояние до ближайшего члена этой прогрессии (входящего по (6) в M) было бы меньше d, что противоречит определению d (4). Итак, $M=\{r+d(k-1), k \in \mathbb N\}$.
(8) Поскольку r-d < 0, то $|r-d| = d-r \in M$ (по (5)), значит, d-r=r+d(k-1), k --- натуральное, откуда 2r=(2-k)d. По (2) r > 0, а значит, остаётся единственный вариант k=1, d=2r>0 и $M = \{r(2k-1), k \in \mathbb N\}$.

Итак, по (2) r натуральное, по (3) r<p-1, по (8) любой элемент M (в том числе и n) делится на r. Лемма доказана.

Теперь перейдём собственно к решению.

Теорема 1. Если $a+b=2^k$, $k \in \mathbb N$ и a взаимно просто с b (что здесь равносильно нечётности a), то $n^2|a^n+b^n$ не выполняется ни при каком натуральном n>1.
Доказательство.
(9) Пусть $n^2|a^n+b^n$. Для чётного n=2k это невозможно, т.к. $a^k$ и $b^k$ нечётны, $(a^k)^2+(b^k)^2$ = $(2A+1)^2+(2B+1)^2$ = $4(A^2+A+B^2+B)+2$ --- не делится на 4, а тем более на $n^2=4k^2$.
(10) Рассмотрим случай нечётного n. Пусть p --- минимальный простой делитель n, p>2.
(11) $p|a^n+b^n$. Так как a и b взаимно просты, только одно из них может делиться на p, но если ровно одно делится, то условие $p|a^n+b^n$ невыполнимо. Значит, и a и b взаимно просты с p.
(12) Из (10) и (11) видим, что выполнены все условия леммы. Значит, существует $r \in \mathbb N$: $p|a^r+b^r$, r<p-1<p и r|n. Но по (10) все простые делители n не меньше p, а делитель r<p. Значит, r=1 и p|a+b, что невозможно, т.к. a+b --- степень двойки и не делится на простое p>2. Теорема 1 доказана.

Теорема 2 (уж для полноты приведу). Для всех остальных (не удовлетворяющих условию теоремы 1) натуральных пар (a,b) существует такое натуральное n>1, что $n^2|a^n+b^n$.
Доказательство.
(13) Пусть a взаимно просто с b, $a+b \neq 2^k$. Пусть p --- простой делитель (a+b), больший двух. Из p|a+b следует: $(-b) \equiv a(\mathrm{mod}\ p)$.
(14) $a^p+b^p$ = (a+b)K, где $K=\sum\limits_{i=0}^{p-1}a^i (-b)^{p-1-i}$ $\equiv$ $\sum\limits_{i=0}^{p-1}a^i a^{p-1-i}$ $\equiv$ $\sum\limits_{i=0}^{p-1}a^{p-1}$ = $p a^{p-1} \equiv 0 (\mathrm{mod}\ p)$. Итак, $p|a+b$ и $p|K$, откуда $p^2|a^p+b^p$. Случай взаимно простых (a,b) доказан.
(15) Если (a,b) не являются взаимно простыми, то, очевидно, в качестве n можно взять их наибольший общий делитель (он больше 1). Теорема 2 доказана.

Итак, ответ по 1-му пункту задачи следующий: a нечётно и $a+b=2^k$, $k \in \mathbb N$.

[Sonic86]

Руст писал(а):

1. Найти все пары натуральных чисел а и b, для которых условие
(1)$n^2|(a^n+b^n)$
не выполняется при n>1.

BanmaN нашел на AoPS такое:
http://www.artofproblemsolving.com/Foru ... p?t=401494
С помощью этой леммы тоже можно решать эту задачу Во всяком случае случай $n^2|2^n+1$ есть даже в самой pdf-ке.

(Оффтоп)

это просто информационное сообщение для полноты поста