2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Пары чисел
Сообщение27.09.2006, 22:53 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение04.10.2006, 14:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение04.10.2006, 16:27 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение04.10.2006, 18:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение04.10.2006, 18:56 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение05.10.2006, 10:31 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
Руст писал(а):
Несложно доказать, что других не существует. Рассмотрите минимальный простой делитель числа n.

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

 Профиль  
                  
 
 
Сообщение05.10.2006, 11:34 
Заслуженный участник


09/02/06
4382
Москва
Да, вы правы. Для этого случая надо было писать, если при n>3...

 Профиль  
                  
 
 
Сообщение07.10.2006, 04:13 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Попробую второй пункт.
Во-первых, очевидно, можно считать (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}$, что нереально.

 Профиль  
                  
 
 
Сообщение12.10.2006, 14:25 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
Вдохновлённый подсказкой Руста и идеями Артамонова Ю.Н. и 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$.

 Профиль  
                  
 
 Re: Пары чисел
Сообщение18.07.2011, 15:04 
Заслуженный участник


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

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

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group