Доказать существование обратных элементов

[gogoshik]

Помогите, плиз, разобраться с такой задачей.

Требуется показать, что для каждого элемента множества $\{1, 2, 3, ..., p-1\}$ c бинарной операцией умножения по $\bmod (p)$, где $p$ -- простое, существует обратный элемент.

Я составил таблицу умножения. В ней видно, что для элементов $1$ и $(p-1)$ обратными являются они же сами. Т.е. $1 \otimes 1 \equiv 1 (\bmod p)$ и $(p-1) \otimes (p-1) \equiv 1 (\bmod p)$.

Пусть у нас есть произвольный элемент $(p - k)$ и обратный к нему $(p - m)$, где $k, m = 1, 2, ..., p - 1$. Тогда $(p - k) \otimes (p-m) = p^2 - pk - pm + km$ и должно быть сравнимо с единицей по $\bmod (p)$. Очевидно, что всегда возможно будет подобрать такую пару $(k, m)$ для которой остаток $k \otimes m \equiv 1 (\bmod p)$.

По крайней мере всегда можно будет найти обратные элементы. Пример. Множество $\{1, 2, 3, ..., 6\}$ c бинарной операцией умножения по $\bmod (7)$. Тогда обратные элементы:
$x = 1, x^{-1} = 1;$
$x = (p - k) = 7 - 5 = 2, x^{-1} = (p - m) = 7 - 3 = 4$, где $k \otimes m = 5 \otimes 3 \equiv 1 (\bmod 7)$ и т.д.


Может я ошибаюсь где-то и такое рассуждение нельзя считать решением, посмотрите, плиз.

[iifat]

gogoshik в сообщении #1324266 писал(а):

Очевидно, что всегда возможно будет подобрать такую пару

Теперь сравните вот это с исходной задачей.

[Munin]

gogoshik в сообщении #1324266 писал(а):

Может я ошибаюсь где-то и такое рассуждение нельзя считать решением, посмотрите, плиз.

Ничего даже близкого к решению. Вы пока доказали, что если у $k$ есть обратный, то и у $(p-k)$ есть обратный. Но откуда взялось, что у $k$ есть обратный? Ниоткуда.

(Сам обнаруженный вами факт - из-за того, что элементы $k$ и $(p-k)$ "противоположны" в смысле кольца, аналогично противоположным целым числам:

$p-k\equiv -k\equiv(-1)\otimes k\equiv(p-1)\otimes k\pmod{p}.$)

[ewert]

На самом деле проблема в другом. Известно, что для "непростых" чисел утверждение неверно. Но простота-то нигде даже и не пыталась использоваться.

[VAL]

Ключевой шаг - 1-е (и главное) свойство взаимно простых чисел.
$a$ и $b$ взаимно просты тогда и только тогда, когда 1 можно представить в виде их линейной комбинации.

[SomePupil]

Пусть $m, n -$ натуральные числа, $d = km + ln -$ их линейная комбинация с целыми $k$ и $l$. Если вдруг оказалось, что $d$ делит и $m,$ и $n,$ то $d -$ НОД. И обратно, НОД можно выразить в виде линейной комбинации. Из этого в случае взаимно-простых чисел получаем утверждение, от которого до вашей цели $-$ один шаг.

[gogoshik]

Пользуясь всеми подсказками ( ну и соотношением Безу), получается, что в случае взаимно простых $km + ln = 1$. В данном случае, при $l = p$, где $p$ -- простое, напишем $km + pn = \gcd(k, p) = 1$. Тогда $1 \equiv km + pn \equiv km (\bmod p)$, т.е. $km \equiv 1 (\bmod p)$. Так?

[kotenok gav]

gogoshik в сообщении #1324416 писал(а):

при $l = p$,

Надеюсь, подразумевалось $n=p$?

[gogoshik]

SomePupil в сообщении #1324339 писал(а):

Если вдруг оказалось, что $d$ делит и $m,$ и $n,$ то $d -$ НОД.

Ну, если $1$ является единственным делителем $m$ и $n$, то в контексте данной задачи и этой подсказки $n = p$. Спасибо.