Даны натуральные числа $%x$% и $%y$% из отрезка $%[2; 100]$%. Докажите, что хотя бы для одного натурального числа $%n$% число $%{x}^{2^n} + {y}^{2^n}$% - составное.

задан 14 Май '13 15:29

изменен 14 Май '13 18:28

Deleted's gravatar image


126

Мне сначала показалось, что это задача олимпиадного типа, но тогда она должна решаться для чисел без ограничений. Поскольку задан диапазон до 100, есть подозрение, что это задача на составление компьютерной программы. Так ли это?

(14 Май '13 19:46) falcao

Похоже на это.

(14 Май '13 19:54) Anatoliy

нет, не на составление компьютерной программы

(15 Май '13 11:31) IvanLife

@Falcao, задачи-то разные.

(15 Май '13 16:27) Urt

@Urt: о каких задачах имеется в виду, что они разные?

(15 Май '13 16:39) falcao

Falcao, запись условия задачи, на которую Вы дали ссылку, несколько не соответствует условию задачи в данной теме.

(15 Май '13 16:47) Urt

@Urt: но я не давал здесь никаких ссылок! Единственную ссылку давал @рупан, и там изложено решение как раз той задачи, о которой говорится в вопросе.

(15 Май '13 16:54) falcao

@Falcao, спасибо за пояснение. Ваш комментарий к задаче я ошибочно воспринял как продолжение ответа @Pупан"а. В условии задачи, на которую дал ссылку @Pупан, многоэтажные степени (если они там есть) у меня всюду выглядят как произведения. Сейчас попробую разобраться.

(15 Май '13 17:06) Urt

@Urt: Там просто не пропечатались двойные верхние индексы, но по смыслу понятно, что имеются в виду именно они. Если бы речь шла о произведении на $%2^n$%, то доказывать было бы нечего.

(15 Май '13 17:14) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
2
ссылка

отвечен 15 Май '13 13:36

Да, теперь стала понятна роль ограничения. Это связано с простотой третьего числа Ферма $%2^{2^3}+1$%. Ограничение можно тем самым несколько ослабить, основываясь на том же соображении, применённом к четвёртому числу Ферма (а пятое уже не будет простым). Интересно, что я вчера когда пытался решать, но в одном из подходов пробовал реализовать похожую идею, но дальше у меня что-то не "склеилось", и создалось ошибочное впечатление, что задача рассчитана на компьютерный перебор.

(15 Май '13 16:14) falcao
10|600 символов нужно символов осталось
4

Я составил простенькую программу для Maple, которая перебирает все пары чисел $%(x,y)$% разной чётности в пределах от 1 до 100. Программа за несколько секунд проверила, что для каждой такой пары существует натуральное $%n\le5$%, для которого число $%x^{2^n}+y^{2^n}$% является составным. "Рекордное" значение $%n=5$% наблюдалось для двух пар. Одна из них -- это пара $%(2,1)$%, соответствующая числу Ферма $%2^{2^5}+1$%, которое, как известно, делится на 641. Другая пара -- это $%(26,59)$%. Число $%26^{2^5}+59^{2^5}$% делится на 193. Для всех остальных пар подошло число $%n$% от 1 до 4.

Понятно, что пары чисел одинаковой чётности не имеет смысла рассматривать, так как получится чётное число. За вычетом случая $%x=y=1$%, оно всегда будет составным. Для полноты картины я проверял и такие пары, в которых одно число равно 1, а другое чётно.

Представленная информация не является математически прозрачным доказательством, хотя программа для каждой пары может указать конкретный простой делитель найденного составного числа. Надо заметить, что такая программа работает медленнее, так как алгоритмы проверки числа на простоту без указания разложения на множители (или даже нахождения простых делителей) работают существенно быстрее. Из других "рекордсменов" можно отметить пару $%(26,25)$%. Для неё $%n=3$%, а число $%26^8+25^8$% имеет наименьший простой делитель, равный 106321.

Мне кажется, какого-то красивого олимпиадного решения в данном случае быть не должно: вся эта тематика, связанная с обобщёнными числами Ферма, изучена достаточно мало -- на уровне отдельных чисел, про которые известно, простые они или составные.

Вот ещё пример интересной пары: $%(42,17)$%. Для неё $%n=3$%, и число $%42^8+17^8$% равно 9689627753857 и имеет такое разложение на простые множители: $%656993\cdot14748449$%. Ясно, что такая проверка не может быть осуществлена вручную, хотя при изменении $%n$% у соответствующего числа появляются небольшие простые делители, где факт делимости может быть установлен совсем просто. Скажем, если положить $%n=6$%, то число $%42^{64}+17^{64}$% будет иметь простой делитель $%257$%.

ссылка

отвечен 15 Май '13 2:24

изменен 15 Май '13 12:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,819

задан
14 Май '13 15:29

показан
665 раз

обновлен
15 Май '13 17:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru