|
Даны натуральные числа $%x$% и $%y$% из отрезка $%[2; 100]$%. Докажите, что хотя бы для одного натурального числа $%n$% число $%{x}^{2^n} + {y}^{2^n}$% - составное. задан 14 Май '13 15:29 
IvanLife
показано 5 из 9
показать еще 4
|
|
отвечен 15 Май '13 13:36 
рупан Да, теперь стала понятна роль ограничения. Это связано с простотой третьего числа Ферма $%2^{2^3}+1$%. Ограничение можно тем самым несколько ослабить, основываясь на том же соображении, применённом к четвёртому числу Ферма (а пятое уже не будет простым). Интересно, что я вчера когда пытался решать, но в одном из подходов пробовал реализовать похожую идею, но дальше у меня что-то не "склеилось", и создалось ошибочное впечатление, что задача рассчитана на компьютерный перебор.
(15 Май '13 16:14)
falcao
|
|
Я составил простенькую программу для 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 
falcao |
Мне сначала показалось, что это задача олимпиадного типа, но тогда она должна решаться для чисел без ограничений. Поскольку задан диапазон до 100, есть подозрение, что это задача на составление компьютерной программы. Так ли это?
Похоже на это.
нет, не на составление компьютерной программы
@Falcao, задачи-то разные.
@Urt: о каких задачах имеется в виду, что они разные?
Falcao, запись условия задачи, на которую Вы дали ссылку, несколько не соответствует условию задачи в данной теме.
@Urt: но я не давал здесь никаких ссылок! Единственную ссылку давал @рупан, и там изложено решение как раз той задачи, о которой говорится в вопросе.
@Falcao, спасибо за пояснение. Ваш комментарий к задаче я ошибочно воспринял как продолжение ответа @Pупан"а. В условии задачи, на которую дал ссылку @Pупан, многоэтажные степени (если они там есть) у меня всюду выглядят как произведения. Сейчас попробую разобраться.
@Urt: Там просто не пропечатались двойные верхние индексы, но по смыслу понятно, что имеются в виду именно они. Если бы речь шла о произведении на $%2^n$%, то доказывать было бы нечего.