2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 общий простой делитель 2^n-3 и 3^n-2
Сообщение03.01.2018, 20:56 
Модератор
Аватара пользователя


11/01/06
5660
Известно, что для $n=59868530942221$ числа $2^n-3$ и $3^n-2$ имеют общий простой делитель. Найдите его.

 Профиль  
                  
 
 Re: общий простой делитель 2^n-3 и 3^n-2
Сообщение04.01.2018, 00:33 
Заслуженный участник


12/08/10
1608
$p-1|n^2-1$?

 Профиль  
                  
 
 Re: общий простой делитель 2^n-3 и 3^n-2
Сообщение04.01.2018, 00:42 
Модератор
Аватара пользователя


11/01/06
5660
Null, и чему же равно $p$?

 Профиль  
                  
 
 Re: общий простой делитель 2^n-3 и 3^n-2
Сообщение04.01.2018, 11:02 


16/08/05
1146
Решение Null: 92009554676141

 Профиль  
                  
 
 Re: общий простой делитель 2^n-3 и 3^n-2
Сообщение04.01.2018, 13:45 
Заслуженный участник
Аватара пользователя


13/08/08
14430
А я вчера принял последнюю цифру $n$ за семёрку. И так обрадовался, что накатал ответ — $5$. А потом призадумался, а чего это maxal такую задачку дал. И увидел, что там не так всё просто :-( А жаль.

 Профиль  
                  
 
 Re: общий простой делитель 2^n-3 и 3^n-2
Сообщение05.01.2018, 00:09 
Модератор
Аватара пользователя


11/01/06
5660
dmd в сообщении #1281173 писал(а):
Решение Null: 92009554676141
Оно. Кстати, такие простые довольно редки - см. A196627 и A196628.

Null в сообщении #1281083 писал(а):
$p-1|n^2-1$?
Вообще говоря, это делимость не обязана выполнятся, но в этой задаче нам "повезло". Однако, даже найдя единственное $p$ таким образом, мы не можем утверждать, что $\gcd(2^n-3,3^n-2)=p$.

Степень везения предлагаю оценить следующей задачкой:
Пусть $a$ и $b$ случайные ненулевые вычеты по модулю простого $p$. Понятно, что мультипликативные порядки $\mathrm{ord}_p(a)$ и $\mathrm{ord}_p(b)$ являются делителями $p-1$, а вот какова вероятность того, что $\mathrm{lcm}(\mathrm{ord}_p(a),\mathrm{ord}_p(b))=p-1$ ?

(Если это равенство выполняется для искомого $p$ и $(a,b)=(2,3)$ в исходной задаче, то в виду делимости $\mathrm{lcm}(\mathrm{ord}_p(a),\mathrm{ord}_p(b)) \mid (n^2-1)$, мы как раз и получим $(p-1)\mid (n^2-1)$.)

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

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



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

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


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

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