НГУ

Форумы НГУ
Текущее время: Вт дек 10, 2019 7:12 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: легкая задачка по т.ч.
СообщениеДобавлено: Сб сен 15, 2007 9:52 pm 
Не в сети
Начинающий автор

Зарегистрирован: Вс июн 18, 2006 4:39 pm
Сообщения: 285
Подскажите как решать следующие задачки:
1/ @ 1+2^{n}+4^{n} - простое => n=3^{k} @
2/ @Доказать бесконечность множества простых чисел вида {4k+1}@


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 12:00 am 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
По второй задаче задаче смотрите Виноградов "Основы теории чисел" в вопросах к главе 1 ( у меня это страница 23) задача №5, а в конце смотрите решение.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 12:13 am 
Не в сети
Начинающий автор

Зарегистрирован: Вс июн 18, 2006 4:39 pm
Сообщения: 285
MaxVT писал(а):
По второй задаче задаче смотрите Виноградов "Основы теории чисел" в вопросах к главе 1 ( у меня это страница 23) задача №5, а в конце смотрите решение.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 1:03 am 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Решение второй задачи без теоремы Дирихле:
Предположим, что существунт только конечное число простых чисел вида 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. Противоречие.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 2:34 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 10:25 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
В связи с первой задачей стало любопытно, верна ли обратная импликация. То есть верно ли, что если 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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 5:13 pm 
Не в сети
Начинающий автор

Зарегистрирован: Вс июн 18, 2006 4:39 pm
Сообщения: 285
Доказательства конечно красивые, но с использованием еще не известных результатов для студентов первого курса. Задачи то из первого параграфа сборника Блощицына. Если кто предложит вариант решения без сравнений и символов, то вопрос еще актуален.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 7:41 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
sxe писал(а):
Если кто предложит вариант решения без сравнений и символов, то вопрос еще актуален.


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

Пусть 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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс сен 16, 2007 9:30 pm 
Не в сети
Начинающий автор

Зарегистрирован: Вс июн 18, 2006 4:39 pm
Сообщения: 285
Коба писал(а):
Ну и какие проблемы? Перепишите всё без сравнений. Я покажу на примере первой задачи, как это делается, ну а уж вторую давайте сами. Справитесь? :)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 17, 2007 3:37 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
У меня вот что получилось.
Пусть 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),
а должно ведь делиться.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 17, 2007 4:52 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Гост_Я писал(а):
У меня вот что получилось.
Пусть 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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 17, 2007 5:14 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Коба писал(а):
Честно говоря, плохо понял. При чём здесь простота числа p? И чему x равен?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 17, 2007 9:39 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Гост_Я писал(а):
Это решает исходную задачу.


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

Гост_Я писал(а):
Показано, что при любом натуральном x


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

Гост_Я писал(а):
...и простом p...


Простота 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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 27, 2007 3:45 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Коба писал(а):
В связи с первой задачей стало любопытно, верна ли обратная импликация. То есть верно ли, что если n = 3^k для некоторого натурального k, то число 1 + 2^n + 4^n --- простое.

При n = 1,3 это так. Для n=9 уже так просто не проверишь, надо прогу писать.

Для n=9 число также является простым. А дальше идут составные:
1 + 2^27 + 4^27 = 2593 * 71119 * 97685839
1 + 2^81 + 4^81 = 487 * 16753783618801 * 192971705688577 * 3712990163251158343
Дальше идут еще как минимум 4 составных числа, но вот разложения их на простые так просто получить не удастся.
Коба писал(а):
Но если и тут окажется, что верно, то для n = 27 компик ещё что-то посчитает, а для n = 81 уже всё... По крайней мере я не вижу алгоритма, который бы проверил простоту чиста 1 + 2^{81} + 4^{81} за обозримое время.

У вас превратное представление о существующих тестах простоты. Например, непростота для n=3^8=6561 на современном компе устанавливается за доли секунд.
Коба писал(а):
Так что программировать ничего не хочется.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: легкая задачка по т.ч.
СообщениеДобавлено: Чт сен 27, 2007 3:59 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
sxe писал(а):
1/ @ 1+2^{n}+4^{n} - простое => n=3^{k} @

Пусть 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, что и требовалось доказать.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB