Решения (лин. диофант.) уравнения с помощью теоремы Эйлера

[GalkaVV]

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

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


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

[RIP]

Подразумевается следующая теорема Эйлера:
Если $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

[GalkaVV]

Спасибо. Просто огромное.

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

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