2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 1489 как делитель решения 2^n = 3 (mod n)
Сообщение05.02.2007, 14:49 
Модератор
Аватара пользователя


11/01/06
5702
Докажите, что 1489 не может быть делителем натурального числа $n,$ удовлетворяющего сравнению $2^n \equiv 3\pmod{n}.$

 Профиль  
                  
 
 
Сообщение05.02.2007, 16:40 
Заслуженный участник


09/02/06
4397
Москва
Проверил, что $p=1489$ простое число. По всей видимости $3$ не принадлежит мультипликативной группе остатков по модулю $p$, образованной $2$. Это можно проверить вычислив точные порядки чисел $T(2)$ и $T(3)$. Необходимо, чтобы $T(3)$ делил $T(2)$. Сразу по символам Лежандра не удалось проверить $2$ и $3$ оба квадратичные вычеты. Поэтому вычисления длинны $p-1=1488=16\cdot 3\cdot 31.$

 Профиль  
                  
 
 
Сообщение05.02.2007, 17:20 
Заслуженный участник
Аватара пользователя


01/08/06
3117
Уфа
$2^{637} \equiv 3\pmod{1489}$, так что не получается.

 Профиль  
                  
 
 
Сообщение05.02.2007, 18:12 
Заслуженный участник


09/02/06
4397
Москва
Тогда сложно. Знаем только, что надо показать, что при $n=1489m$ нет решения сравнений $2^{1489m}=3\pmod m \ \ m=637\pmod{744}$.
Для этого можно рассмотреть малые простые числа вида $p=2k\cdot 1489+1$ и рассмотреть остатки при делении $m$ на такие простые числа.

 Профиль  
                  
 
 
Сообщение05.02.2007, 21:42 
Модератор
Аватара пользователя


11/01/06
5702
Задача простая. Первый шаг сделан.
Осталось сделать второй. :D

 Профиль  
                  
 
 
Сообщение06.02.2007, 07:29 


23/01/07
3497
Новосибирск
Не уверен, что все учел правильно, но мне видится так:
Период повторения остатков по степеням двойки по основанию $1489$, в том числе и $3 \mod (1489)$$744$.
Первое появление остатка $3$, как здесь справедливо заметили, – $637$-я степень числа $2$.
Таким образом, можно составить равенство:
$637 + L\cdot 744 = 1489\cdot M$, где $L$ и $M$ – целые числа
Или $2\cdot 637 + L\cdot (1489-1) = 2M\cdot 1489.$
$2\cdot 637 + L\cdot 1489 - L = 2M\cdot 1489$
$2\cdot 637 - L = 1489\cdot (2M - L)$
Т.к. левая часть не делится на $1489$, то равенство в целых числах не возможно, следовательно, числу $1489$ - не судьба, участвовать в указанных сравнениях.

 Профиль  
                  
 
 
Сообщение06.02.2007, 07:35 
Модератор
Аватара пользователя


11/01/06
5702
Батороев писал(а):
$2\cdot 637 - L = 1489\cdot (2M - L)$
Т.к. левая часть не делится на $1489$,

Почему это она не делится? Возьмите, например, $L=2\cdot 637$ или $L=2\cdot 637+1489$ и т.д. и будем вам делимость.

 Профиль  
                  
 
 
Сообщение06.02.2007, 08:36 


23/01/07
3497
Новосибирск
"Ляпу" свою принимаю, но тогда, что мы имеем при $n=2056309$ и Вашем "т.д"?

 Профиль  
                  
 
 
Сообщение06.02.2007, 08:44 
Модератор
Аватара пользователя


11/01/06
5702
Батороев писал(а):
"Ляпу" свою принимаю, но тогда, что мы имеем при $n=2056309$ и Вашем "т.д"?

Для $n=2056309$ число $1489$ является делителем, но данное $n$ не удовлетворяет сравнению $2^n \equiv 3\pmod{n}.$ Поэтому никаких выводов здесь сделать нельзя.

 Профиль  
                  
 
 
Сообщение06.02.2007, 08:48 
Заслуженный участник


09/02/06
4397
Москва
Будем считать, что worm нашёл минимальное решение сравнения. Тогда $T(2)>637$ и $T(2)\leq 744$ вследствие того, что $2$ квадратичный вычет, т.е. $m=637+744k$ даёт все возможные решения. Число $744$ делится на $24$, соответственно $m=13\pmod{24}$. Если бы символ Якоби $\left(\frac{2}{m}\right)=1$ а $\left(\frac{3}{m}\right)=-1$ то получилось бы доказательство не возможности деления $n$ на $1489$. Однако, дело обстоит наоборот $\left(\frac{2}{m}\right)=-1$, $\left(\frac{3}{m}\right)=1$. Поэтому, или задача решается привлечением законов взаимности более высшей степени (например кубической или биквадичной) или до чего то мы не можем додуматься или ошибся maxal.

 Профиль  
                  
 
 
Сообщение06.02.2007, 08:59 
Модератор
Аватара пользователя


11/01/06
5702
Или ошибся Руст. :)
Ты на верном пути, но в твоих рассуждениях ошибка.

 Профиль  
                  
 
 
Сообщение06.02.2007, 09:11 
Заслуженный участник


09/02/06
4397
Москва
Да. Из $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$ следует, что тройка должна быть чётной степенью $2$, а у нас $m=637\pmod {744}$ нечётная степень.

 Профиль  
                  
 
 
Сообщение06.02.2007, 09:15 
Модератор
Аватара пользователя


11/01/06
5702
Рустем вплотную подошел к решению, поэтому можно выкладывать карты на стол ;)

Итак, пусть $n=1489\cdot m$ удовлетворяет сравнению $2^n \equiv 3\pmod{n}.$
Тогда:

во-первых, (как справедливо заметили Руст и worm2), m должно удовлетворять сравнению $m\equiv 637\pmod{744}$, которое в свою очередь влечет $m\equiv 13\pmod{24}$;

во-вторых, $n$ обязано быть нечетным, а поэтому $\left(2^{(n+1)/2}\right)^2 \equiv 6\pmod{m}$ и, значит, символ Якоби $\left(\frac6m\right)=1.$

Осталось только проверить, что требования $m\equiv 13\pmod{24}$ и $\left(\frac6m\right)=1$ несовместны.

 Профиль  
                  
 
 
Сообщение06.02.2007, 09:22 
Заслуженный участник


09/02/06
4397
Москва
maxal писал(а):
Рустем вплотную подошел к решению, поэтому можно выкладывать карты на стол ;)

А разве, то что я писал, не решение. Правда раньше меня смущало, что $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$. Но это противоречит нечётности n, о чём написал при последнем посте.

 Профиль  
                  
 
 
Сообщение06.02.2007, 09:31 
Модератор
Аватара пользователя


11/01/06
5702
Руст писал(а):
А разве, то что я писал, не решение. Правда раньше меня смущало, что $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$. Но это противоречит нечётности n, о чём написал при последнем посте.

Да, решение, просто "последнего поста" не было, когда я писал свое решение. Я и сказал, что ты вплотную подошел к решению, потому как осталось исправить всего лишь одну маленькую ошибочку, что собственно и было сделано в "последнем посте".

Добавлено спустя 2 минуты 19 секунд:

Кстати, красивая задачка получилась? Я вообще совершенно случайно наткнулся на этот факт, вот и решил предложить в качестве задачки :lol:

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group