НГУ

Подскажите как решать следующие задачки:
1/ @ 1+2^{n}+4^{n} - простое => n=3^{k} @
2/ @Доказать бесконечность множества простых чисел вида {4k+1}@

По второй задаче задаче смотрите Виноградов "Основы теории чисел" в вопросах к главе 1 ( у меня это страница 23) задача №5, а в конце смотрите решение.

Да-да, я в курсе, что ее можно решать используя теорему Дирихле ( Если в арифмет. последовательности a, a+d,a+2d,... (a,d)=1 то в ней найдется бесконечно много простых чисел), но доказательства еще не нашел теоремы этой.

Первая задача значительно интересней, причем довольно легко доказать, что n - нечетное.

Решение второй задачи без теоремы Дирихле:
Предположим, что существунт только конечное число простых чисел вида 4t+1. Тогда можно взять N равным произведению этих чисел. Возьмем любой простой делитель p числа 4N^{2}+1. Из того, что p|4N^{2}+1 следует $(2N)^{2}\equiv -1\pmod{p}$, то есть $\left(\frac{-1}{p}\right)=1$, где левая и правая скобки обозначают символ Лежандра. А это значит, что p имеет вид 4t+1.
Поскольку N --- произведение всех простых чисел вида 4t+1, то p|N. В то же время p|4N^{2}+1. Получаем, что p|1, хотя p>1. Противоречие.

1) При n = 0 1 + 2^n + 4^n = 3 --- простое число и n не равно 3^k.

Если же мы исключаем ноль из рассмотрения, то вроде так у меня получилось:

Пусть n = v*r, где v --- степень тройки, а r не делится на 3. Необходимо доказать, что если число 1 + 2^n + 4^n --- простое, то r = 1.

Допустим, что r не равно 1. Пусть u = 2^v и m = 1+u+u^2. Так как u^3-1 = (u-1)(1+u+u^2), то u^3-1 делится на m и u^3 сравнимо с 1 по модулю m. Значит, и u^{3s} сравнимо с 1 для любого целого неотрицательного s.

Имеем 1 + 2^n + 4^n = 1 + u^r + u^{2r}. Так как r не делится на 3, то либо r = 3s+1, либо r=3s+2 для некоторого неотрицательного s. В первом случае 1 + u^r + u^{2r} сравнимо с 1 + u^{3s}u + u^{6s}u^2 сравнимо с 1 + u + u^2 сравнимо с нулём по модулю m. Во втором случае 1 + u^r + u^{2r} сравнимо с 1 + u^{3s}u^2 + u^{3(2s+1)}u сравнимо с 1 + u^2 + u и опять сравнимо с нулём по модулю m. В обоих случаях 1 + u^r + u^{2r} делится на m.

Так как v > 0, то u > 1. Так как r > 1, то 1 + 2^n + 4^n = 1 + u^r + u^{2r} > 1 + u + u^2 = m. А раз число 1 + 2^n + 4^n делится на число m, меньшее его и не равное 1, то оно составное.

Может, можно найти что-нибудь короче, хотя не уверен. И так всё достаточно просто.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

В связи с первой задачей стало любопытно, верна ли обратная импликация. То есть верно ли, что если n = 3^k для некоторого натурального k, то число 1 + 2^n + 4^n --- простое.

При n = 1,3 это так. Для n=9 уже так просто не проверишь, надо прогу писать. Но если и тут окажется, что верно, то для n = 27 компик ещё что-то посчитает, а для n = 81 уже всё... По крайней мере я не вижу алгоритма, который бы проверил простоту чиста 1 + 2^{81} + 4^{81} за обозримое время.

Так что программировать ничего не хочется.

Пытался рассуждать, но доказать так ничего и не получилось. Всё, что получилось --- это доказать один простой фактик о взаимной простоте некоторых пар чисел. Поначалу мне казалось, что это может быть полезным, но в конце концов никакой пользу я оттуда извлечь так и не сумел. На всякий случай привожу этот факт с доказательством --- вдруг кому-то станет интересно? Хотя путь, похоже, тупиковый.

---------------------

Пусть для произвольного натурального k u_k = 2^{3^k} и v_k = 1 + u_k + u_k^2. Необходимо доказать или опровергнуть, что v_k --- простое число для любого k.

Лемма: Для любого k числа u_k - 1 и v_k взаимно просты.

Доказательство. Предположим, что простое число p делит u_k - 1. Так как u_k --- степень двойки, то p не равно 2. Так как u_k --- нечётная степень двойки, то u_k сравнимо с -1 по модулю 3 и p не равно 3. Далее, имеем 3u_k(u_k-1) + (u_k-1)^3 = u_k^3 - 1 = v_k(u_k-1). Пусть s --- максимальное число, такое что p^s делит u_k-1. Так как p^{s+1} не делит 3u_k(u_k-1) и p^{s+1} делит (u_k-1)^3, то p^{s+1} не делит v_k(u_k-1). Отсюда следует, что p не делит v_k.

Следствие: Для v_k = 1 + 2^{3^k} + 4^{3^k} различные v_k-ые взаимно просты друг с другом.

Доказательство. Сразу следует из леммы, поскольку u_{k+1}-1 делится на u_k - 1 и на v_k.

----------------------

Но взаимной простоты, увы, мало. Если у кого-то есть идеи или решение --- пишите. Мне будет интересно.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Доказательства конечно красивые, но с использованием еще не известных результатов для студентов первого курса. Задачи то из первого параграфа сборника Блощицына. Если кто предложит вариант решения без сравнений и символов, то вопрос еще актуален.

Ну и какие проблемы? Перепишите всё без сравнений. Я покажу на примере первой задачи, как это делается, ну а уж вторую давайте сами. Справитесь?

Пусть n = v*r, где v --- степень тройки, а r не делится на 3. Необходимо доказать, что если число 1 + 2^n + 4^n --- простое, то r = 1.

Допустим, что r не равно 1. Пусть u = 2^v и m = 1+u+u^2. Так как u^3-1 = (u-1)m, то для любого целого положительного s справедливо u^{3s} = (u^3-1)(1+u^3+...+u^{3(s-1)})+1 = m(u-1)(1+u^3+...+u^{3(s-1)})+1.

Имеем 1 + 2^n + 4^n = 1 + u^r + u^{2r}. Так как r не делится на 3, то либо r = 3s+1, либо r=3s+2 для некоторого неотрицательного s. В первом случае 1 + u^r + u^{2r} = 1 + u^{3s}u + u^{6s}u^2 = 1 + (m(u-1)(1+u^3+...+u^{3(s-1)})+1)u + (m(u-1)(1+u^3+...+u^{3(2s-1)})+1)u^2 = 1 + u + u^2 + m(u-1)(1+u^3+...+u^{3(s-1)} + 1+u^3+...+u^{3(2s-1)}) = m(1 + (u-1)(1+u^3+...+u^{3(s-1)} + 1+u^3+...+u^{3(2s-1)})). Во втором случае 1 + u^r + u^{2r} = 1 + u^{3s}u^2 + u^{3(2s+1)}u = 1 + (m(u-1)(1+u^3+...+u^{3(s-1)})+1)u^2 + (m(u-1)(1+u^3+...+u^{6s})+1)u = 1 + u^2 + u + m(u-1)(1+u^3+...+u^{3(s-1)} + 1+u^3+...+u^{6s}) = m(1 + (u-1)(1+u^3+...+u^{3(s-1)} + 1+u^3+...+u^{6s})). Как видим, в обоих случаях 1 + u^r + u^{2r} делится на m.

Так как v > 0, то u > 1. Так как r > 1, то 1 + 2^n + 4^n = 1 + u^r + u^{2r} > 1 + u + u^2 = m. А раз число 1 + 2^n + 4^n делится на число m, меньшее его и не равное 1, то оно составное.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

да справимся, но все равно хочется по оригинальней решение

У меня вот что получилось.
Пусть p и P=1+x^p+x^{2p} простые.
Тогда P*(x^p-1)=x^{3p}-1=(x^3-1)*M
Сокращая на (x-1), получаем
P*(x^{p-1}+ x^{p-2}+ … +1)=(x^2+x+1)*M
Теперь видно, что если p не делится на 3,
то (x^{p-1}+ x^{p-2}+ … +1) не делится на (x^2+x+1) (остаток равен x+1 или 1),
а должно ведь делиться.

Честно говоря, плохо понял. При чём здесь простота числа p? И чему x равен?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Показано, что при любом натуральном x и простом p число 1+x^p+x^{2p} может быть простым, только если p=3.
Это решает исходную задачу.

Ну да. В принципе, так тоже можно. Хотя если расписать это решение с той же степенью подробности, как я своё выше, то у меня будет короче.



При любом натуральном x > 1. При x = 1 доказательство не проходит.



Простота p используется в этом доказательстве только для того, чтобы получить из неё неравенство p > 1 (и из него далее вывести, что P не равно x^2 + x + 1). Глядя на такое использование свойства простоты я вначале подумал, что в текст Гост_Я вкралась опечатка.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Для n=9 число также является простым. А дальше идут составные:
1 + 2^27 + 4^27 = 2593 * 71119 * 97685839
1 + 2^81 + 4^81 = 487 * 16753783618801 * 192971705688577 * 3712990163251158343
Дальше идут еще как минимум 4 составных числа, но вот разложения их на простые так просто получить не удастся.

У вас превратное представление о существующих тестах простоты. Например, непростота для n=3^8=6561 на современном компе устанавливается за доли секунд.

Почему бы не воспользоваться мат.пакетами, в которых все уже давно запрограммировано. Например, PARI/GP - и бесплатный, и быстрый пакет для теоретико-числовых вычислений.

Пусть n=m*3^k, где m не делится на 3.
Из равенства
2^{3n} - 1 = (2^n - 1) (1 + 2^n + 4^n)
следует, что обе части делятся на 2^{3^{k+1}} - 1, причем 2^n - 1 делиться на 2^{3^{k+1}} - 1 не может. Поэтому НОД(2^{3^{k+1}} - 1,1 + 2^n + 4^n)>1 и, в виду простоты 1 + 2^n + 4^n, число 2^{3^{k+1}} - 1 обязано делиться на 1 + 2^n + 4^n. В частности, имеем
2^{3^{k+1}} - 1 >= 1 + 2^n + 4^n > 2^{2*m*3^k}
Это неравенство не может выполняться, если m>1 (в этом случае правая часть будет больше левой). Поэтому m=1, что и требовалось доказать.