Строим простое число

[nnosipov]

Пусть $q$ --- простое число, $R$ --- натуральное число, меньшее $q$, и $N=q^2R+1$. Если $2^R \not\equiv 1 \pmod{N}$ и $2^{N-1} \equiv 1 \pmod{N}$, то $N$ --- простое число. Докажите это.

[griboedovaa]

Пусть N не равно 2 и N сщставное число. F(n)-функция эйлера
Нод(F(N),N-1)=1. Пусть &-показатель(order) модулё N
тогда & делит F(n) и делит N-1, тогда &=1,что не возможно

[nnosipov]

griboedovaa в сообщении #549928 писал(а):

Пусть N не равно 2 и N сщставное число. F(n)-функция эйлера
Нод(F(N),N-1)=1. Пусть &-показатель(order) модулё N
тогда & делит F(n) и делит N-1, тогда &=1,что не возможно

Из трёх предложений понял только первое. Откуда следует равенство $\gcd{(\varphi(N),N-1)}=1$? О показателе какого числа по модулю $N$ идёт речь в третьем предложении?

[hippie]

nnosipov в сообщении #549956 писал(а):

Откуда следует равенство $\gcd{(\varphi(N),N-1)}=1$?

Это равенство, в общем случае, не выполняется.
Например, при нечётных $N$ и $\varphi(N)$ и $N-1$ — чётные числа.
Или, при $N=76\ (=5^2\cdot3+1).$ $\text{ НОД}(\varphi(N);\ N-1) = \text{НОД}(36;\ 75)=3.$

Правильное утверждение не $\text{ НОД}(\varphi(N);\ N-1) = 1,$ а $\text{ НОД}(\varphi(N);\ q) = 1.$

-- 19.03.2012, 14:19 --

Предположим, что $N$ составное и при этом $\varphi (N)$ кратно $q.$ Тогда один из простых множителей в разложении $N$ имеет вид $qx+1.$ Соответственно $\frac N{qx+1} = qy+1.$ Тогда $xy+\frac{x+y}q = R.$ Учитывая, что $\frac{x+y}q$ целое и $x\ge1,\ y\ge1,$ получаем $R\ge q,$ что противоречит условию.
Таким образом при составном $N$: $\text{ НОД}(\varphi(N);\ q^2) = 1.$
И, поскольку $\left(2^R\right)^{q^2}\equiv \left(2^R\right)^{\varphi(N)} \equiv 1 (\mod N),$ то и $\left(2^R\right)^{\text{ НОД}(\varphi(N);\ q^2)}\equiv 1 (\mod N),$ т.е. $2^R\right \equiv 1 (\mod N),$ а это противоречит условию.

[nnosipov]

hippie в сообщении #549982 писал(а):

Это равенство, в общем случае, не выполняется.

Ещё бы.

hippie в сообщении #549982 писал(а):

Тогда один из простых множителей в разложении $N$ имеет вид $qx+1.$

Вот это место поподробнее, пожалуйста. Не понимаю, почему это очевидно.

[Хорхе]

Из формулы для $\varphi(N)$ разве не очевидно?

[nnosipov]

Хорхе в сообщении #550012 писал(а):

Из формулы для $\varphi(N)$ разве не очевидно?

Да, теперь вижу . Как-то в голову не пришло взглянуть на это дело вот так, сам получил этот факт из других соображений.

[maxal]

см. также http://nature.web.ru/db/msg.html?mid=11 ... ode33.html

[nnosipov]

Вот, кстати, ссылка на оригинал задачи: http://www.artofproblemsolving.com/Foru ... 6&t=443903

maxal в сообщении #550458 писал(а):

см. также http://nature.web.ru/db/msg.html?mid=11 ... ode33.html

Впервые статья Нестеренко появилась в "Математическом просвещении" (1998, вып. 2). Пожалуй, самое популярное изложение вопроса.