2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 3^n == 7 (mod n) и делитель 127
Сообщение29.08.2016, 16:27 
Модератор
Аватара пользователя


11/01/06
5660
Модификация одной моей старой задачи. Опубликована под номером 4101 в Crux Mathematicorum 42:1 (2016).

Пусть натуральное число $n$ удовлетворяет сравнению:
$$3^n\equiv 7\pmod{n}.$$
Докажите, что $n$ не делится на 127.

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение04.09.2016, 19:13 


16/08/05
1146
Попробую только начать.

Если $n=127m$, то $m$ должно удовлетворять сравнению $m\equiv 115\pmod{126}$. Далее рассуждения должны быть аналогичны теме, с анализом делителей 126 и привлечением квадратичного закона взаимности. Так?

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение04.09.2016, 20:39 
Модератор
Аватара пользователя


11/01/06
5660
dmd, да.

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение07.09.2016, 18:37 


16/08/05
1146
$n$ должно быть нечётно, значит $21$ должно быть квадратичным вычетом по модулю $m$, и значит символ Якоби $\left(\frac{21}m\right)=1$. Периодичность $\left(\frac{21}m\right)$ - тоже $21$, значит $m$ надо рассмотреть по модулю $21$. Из $m\equiv 115\pmod{126}$ видно, что $m\equiv 10\pmod{21}$. Но $\left(\frac{21}{10}\right)=-1$ - значит $127\nmid n$.

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение09.09.2016, 00:33 


16/08/05
1146

(кстати)

$26782373099$ - решение исходного сравнения

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение12.10.2016, 20:59 
Модератор
Аватара пользователя


11/01/06
5660
dmd в сообщении #1150203 писал(а):
$26782373099$ - решение исходного сравнения

Да, вот тут ещё: A277126

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение24.10.2016, 21:59 


16/08/05
1146
Решение 9135884036634915191945452485106476242 видимо было получено факторизацией 3^166-7. А как? Я пробовал factor и factorint в pari/gp - не вышло.

 Профиль  
                  
 
 Re: 3^n == 7 (mod n) и делитель 127
Сообщение25.10.2016, 07:14 
Модератор
Аватара пользователя


11/01/06
5660
dmd, мало пробовали, видимо. Факторизация, кстати, присутствует на factordb.com

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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