модульная арифметика

[ShMaxG]

Помогите ответить на вопрос: верно ли что

$$ n_1 \left( {n_1^{ - 1} \bmod n_2 } \right) + n_2 \left( {n_2^{ - 1} \bmod n_1 } \right) = n_1 n_2 + 1 $$

, если

$$ \gcd \left( {n_1 ,n_2 } \right) = 1 $$

?

[Dandan]

Верно. Левая часть сравнима с 1 mod n_1 и с 1 mod n_2, значит она сравнима с 1 mod n_{1}n_{2}, т.к. n_1 и n_2 взаимо просты. Дальше сами.

[ShMaxG]

Большое спасибо!

[ShMaxG]

Еще такой вопрос: как найти $d$, если

$$ 10 = d^{ - 1} \bmod \left( {28 \cdot 30} \right) $$

Я прихожу к тому, что

$$ 10d \equiv 1\bmod \left( {28 \cdot 30} \right) $$

, что невозможно...

[maxal]

Естественно невозможно. 10 не взаимно просто с модулем, а потому необратимо. Такого $d$ не существует.

[ShMaxG]

Ну да, как я и думал. Спасибо.