2014 dxdy logo

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

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




 
 Решения (лин. диофант.) уравнения с помощью теоремы Эйлера
Сообщение26.05.2007, 22:58 
Все банально и просто, нужно решить уравнения вида $ax+by=c$, в частности $69х-35у=37$ с помощью теоремы Эйлера.

Вопрос: где найти эту теорему и как ей воспользоваться?


P.S. Пожалуйста объясните ход решения.

 
 
 
 
Сообщение27.05.2007, 07:24 
Аватара пользователя
Подразумевается следующая теорема Эйлера:
Если $a$ и $m$ --- взаимно простые целые числа, $m>0$, то
$$a^{\varphi(m)}\equiv1\pmod m.$$

Здесь $\varphi(m)$ --- функция Эйлера. $\varphi(m)$ обозначает количество целых чисел $n$, $1\leqslant n\leqslant m$, которые взаимно просты с $m$. Вычисляется она так: Если $m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_s^{\alpha_s}$, где $p_1,p_2,\ldots, p_s$ --- попарно различные простые числа, $\alpha_1,\ldots,\alpha_s$ --- натуральные числа, то
$$\varphi(m)=\prod_{i=1}^sp_i^{\alpha_i-1}(p_i-1).$$

Применяется она следующим образом:
Чтобы решить уравнение $ax+by=c$, надо решить сравнение $ax\equiv c\pmod {|b|}$. Если предположить для простоты, что $(a,b)=1$ (т.е. $a$ и $b$ взаимно просты), то, по теореме Эйлера, это сравнение имеет решение $x\equiv x_0\pmod{|b|}$, где $x_0:= c\cdot a^{\varphi(|b|)-1}\pmod{|b|}$ (т.е. $x_0$ --- любое целое число, сравнимое с $c\cdot a^{\varphi(|b|)-1}$ по модулю $|b|$; конечно, можно взять $x_0=c\cdot a^{\varphi(|b|)-1}$, но желательно, чтобы $x_0$ было "поменьше", в частности, в Вашем примере $a=69$, $b=-35$, т.е. $a\equiv-1\pmod{|b|}$, поэтому такое $x_0$ легко найти. Да и вообще Ваш пример тривиально решается без теоремы Эйлера.)
А тогда решение уравнения $ax+by=c$ имеет вид $\left(x_0+bt;\frac{c-ax_0}b-at\right)$, $t\in\mathbb Z$. (Но это лишь в случае, когда $(a,b)=1$. Общий случай сводится к этому.)

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

Про это можно почитать, например, в книжке Бухштаба А.А. "Теория чисел" по адресу http://eqworld.ipmnet.ru/ru/library/mat ... theory.htm

 
 
 
 
Сообщение27.05.2007, 23:18 
Спасибо. Просто огромное. :roll:

А по поводу решения моего примера - вы правы, но задача поставлена именно решить это уравнение с помощью теоремы Эйлера.

С уважением, Галина.

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


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