2014 dxdy logo

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

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




 
 Решить сравнение
Сообщение29.12.2013, 14:22 
Добрый день.

Помогите , пожалуйста, разобраться с небольшой задачей.
Нужно найти все натуральные x, удовлетворяющие сравнению $ 4^{x}\equiv 1(\mod 77)$

По теореме Эйлера $ 4^{ \varphi (77) }\equiv 1 ( \mod 77) $

$ \varphi (77)= \varphi (7) \varphi (11)=(7-1)(11-1)=60 $

Не знаю, что дальше надо делать.

 
 
 
 Re: Решить сравнение
Сообщение29.12.2013, 14:37 
Ну хорошо.
Там точнее было бы через $L$-функцию Кармайкла, ну да ладно.
Я Вам советую разложить модуль на множители и перейти от одного сравнения к системе. Множители будут достаточно маленькими, чтобы вычисления было удобно делать даже в голове. После решения каждого сравнения просто найдете общее решение и все.
Далее, вот пусть у нас есть сравнение $a^x\equiv 1\pmod m$. По т. Эйлера мы знаем, что $a^{\varphi (m)}\equiv 1\pmod {m}$. Поскольку все решения образуют арифметическую прогрессию с нулевым начальным членом, т.е. все $x$ описываются сравнением $x\equiv 0\pmod{d}$, то $d$ делит $\varphi(m)$. Если $d$ делит $\varphi(m)$, то у нас есть лишь конечное число вариантов - их можно перебрать. Вот теперь перебирайте делители, как найдете самый малый делитель, удовлетворяющий сравнению, так он и будет его решением.

 
 
 
 Re: Решить сравнение
Сообщение29.12.2013, 15:23 
$\begin{cases}
 & { 4^{x}\equiv 1 ( \mod 7)}  \\ 
 & { 4^{x}\equiv 1 ( \mod 11) } 
\end{cases}$

$\varphi (7)=6=2\cdot 3 $

$4^{2}\equiv 2 (\mod 7)$
$4^{3}\equiv 1 (\mod 7)$

$\varphi (11)=10=2\cdot 5 $

$4^{2}\equiv 5 (\mod 11)$
$4^{5}\equiv 1 (\mod 11)$

Первый член арифметической прогрессии равен $3\cdot5=15 , d=15$.

 
 
 
 Re: Решить сравнение
Сообщение29.12.2013, 15:29 
Прекрасно :-)
Только советую все же написать не $3\cdot 5$, а $\text{НОК}(3,5)$. Ну как хотите, главное, чтобы Вы это понимали.
Ну и слов можно добавить - тут сами смотрите. Если для себя решаете, то слов не нужно, для препода - смотря какой препод...

 
 
 
 Re: Решить сравнение
Сообщение29.12.2013, 15:58 
Точно, нужно НОК написать. Спасибо Вам большое!

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group