2014 dxdy logo

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

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




 
 Помогите разобраться с нелинейным сравнением по модулю
Сообщение18.12.2013, 23:33 
Задача:
Решить сравнение $x^7 \equiv 10 \pmod {49}$

Я недавно занялся модулярной арифметикой, столкнулся с такой задачкой. Я знаю, что это сравнение не имеет решений. Мое доказательство использует дискретное логарифмирование (т. к. модуль - квадрат простого, существует первообразный корень, следовательно задачу можно записать в виде $(g^y)^7 \equiv 10 \pmod {49}$, что равносильно $ (g^7)^y \equiv 10 \pmod {49}$. Теперь можно решать сравнение относительно $y$, а $x \equiv g^y \pmod{49}$).
Вопрос в существовании более простого решения с использованием того, что модуль 49, а показатель 7. В частности, решения с применением малой теоремы Ферма.

 
 
 
 Re: Помогите разобраться с нелинейным сравнением по модулю
Сообщение19.12.2013, 06:56 
helgui в сообщении #803317 писал(а):
Задача:
Решить сравнение $x^7 \equiv 10 \pmod {49}$
Вопрос в существовании более простого решения с использованием того, что модуль 49, а показатель 7. В частности, решения с применением малой теоремы Ферма.
Тогда уж теоремы Эйлера.
На ее основании достаточно проверить, что $10^6$ не сравнимо с $1$ по модулю $49$.

 
 
 
 Re: Помогите разобраться с нелинейным сравнением по модулю
Сообщение19.12.2013, 09:59 
Можно также воспользоваться стандартной техникой, основанной на лемме Гензеля о подъёме (как решить сравнение $f(x) \equiv 0 \pmod{p^k}$, зная все решения сравнения $f(x) \pmod{p}$). Если $x^7 \equiv 10 \pmod{7^2}$, то $x \equiv 10 \pmod{7}$, т.е. $x=3+7y$. Но тогда $x^7=(3+7y)^7 \equiv 3^7 \pmod{7^2}$. Осталось вычислить $3^7 \bmod{7^2}$ и убедиться, что результат отличен от $10 \bmod{7^2}$.

 
 
 
 Re: Помогите разобраться с нелинейным сравнением по модулю
Сообщение20.12.2013, 01:10 
VAL в сообщении #803368 писал(а):
helgui в сообщении #803317 писал(а):
Задача:
Решить сравнение $x^7 \equiv 10 \pmod {49}$
Вопрос в существовании более простого решения с использованием того, что модуль 49, а показатель 7. В частности, решения с применением малой теоремы Ферма.
Тогда уж теоремы Эйлера.
На ее основании достаточно проверить, что $10^6$ не сравнимо с $1$ по модулю $49$.

Блин, все действительно просто. Спасибо всем, кто отозвался.

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


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