Обратимость в кольцах вычетов

[oleg.k]

Теорема $[k]$ обратим в $\mathbb{Z}/n$ $\Leftrightarrow$ $k$ и $n$ взаимно простые.
Слева направо я доказал. А вот в обратную сторону не могу. Доказываю методом от противного.

Рассмотрим случай $n = 1$.
($\forall k \in \mathbb{Z}$) $k$ и $1$ взаимно простые, т.к. единица имеет только 2 делителя: 1 и -1.
Также ($\forall k \in \mathbb{Z}$) $[k]$ обратим в $\mathbb{Z}/n$. Это тоже очевидно, т.к. $\mathbb{Z}/1$ - поле, состоящее из 1 элемента, для которого этот же самый элемент и является обратным (вообще, некоторые авторы этот объект полем не считают, но имхо это вполне нормальное поле, а нежелание считать такое поле полем наверное исходит из желания иметь в поле как минимум 2 разных элемента: ноль и единицу). Таким образом, утверждение теоремы справедливо для $n = 1$.

Рассмотрим случай $n \geqslant 2$. Предположим, что нашлись $n \in \mathbb{N} ( n \geqslant 2)$, кольцо $\mathbb{Z}/n$, $k \in \mathbb{Z}, $ $[k] \in \mathbb{Z}/n$ такие, что $k$ и $n$ взаимно простые и вместе с этим $k$ не обратим в $\mathbb{Z}/n$. Выпишем последовательность произведений $[k][0], [k][1], ... , [k][n-1]$. В ней $n$ элементов. Т.к. $[k]$ не обратим в $\mathbb{Z}/n$, то в этой последовательности нету $[1]$, но т.к. в $\mathbb{Z}/n$ всего $n$ элементов, то $\exists 1\leqslant i < j \leqslant (n-1)$ такие, что $[k][i] = [k][j] \Rightarrow [k(j - i)] = [0] \Rightarrow k(j-i) \vdots n$.

И вот дальше я не знаю как получить противоречие.

Первоначально попытка была следующая. Разложим $n$ на простые множители: $n = n_1\cdot ... \cdot n_s, (s \geqslant 1, n_i \geqslant 2)$. Далее легко показать, что $k(j-i) \vdots n \Rightarrow (\forall 1\leqslant i \leqslant s) k(j-i) \vdots n_i$. Т.к. $(\forall 1\leqslant i \leqslant s)$ $k$ не кратно $n_i$ (т.к. $k$ и $n$ взаимно простые), то по лемме Евклида получаем, что $(\forall 1\leqslant i \leqslant s) (j-i)\vdots n_i$. Но как дальше получить противоречие я не знаю.

[Someone]

oleg.k в сообщении #1469741 писал(а):

$\mathbb{Z}/1$ - поле, состоящее из 1 элемента

В определение поля (и тела) входит требование, чтобы оно содержало больше одного элемента. То, что у Вас получилось, называется нулевым кольцом. Это единственное кольцо, в котором единица совпадает с нулём, и единственное кольцо характеристики $1$. Оно, конечно, во всех отношениях замечательное, но называть его полем не следует. Это породит достаточно много неудобств. Например, придётся постоянно говорить "ненулевое поле" или что-нибудь эквивалентное этому.

oleg.k в сообщении #1469741 писал(а):

некоторые авторы этот объект полем не считают

Я не встречал авторов, которые его считают полем. Впрочем, я не алгебраист.

[york]

Пусть $k$ и $n$ - взаимнопростые
Рассмотрим ряд
$k\cdot 1, k\cdot 2,..., k\cdot (n-1) mod(n)$
Докажем, что в нём все элементы различны.
Пусть $kx=ky mod(n)$
$k(x-y)=0 mod(n)$
Множители $k$ никак не могут внести вклад в равенство нулю по модулю $n$.
Остаётся $x-y=0 mod(n)$, или $x=y mod(n)$
Поэтому в рассмотренном ряду найдётся обратный элемент

[oleg.k]

Someone в сообщении #1469746 писал(а):

В определение поля (и тела) входит требование, чтобы оно содержало больше одного элемента.

Ну я пользуюсь таким определением поля. Поле - коммутативное ассоциативное кольцо с единицей, где всякий ненулевой элемент обратим. Поле, содержащее только ноль, с т.з. этого определения полем является. Тут чисто терминологический момент.

Someone в сообщении #1469746 писал(а):

Я не встречал авторов, которые его считают полем. Впрочем, я не алгебраист.

Да, Вы правы.

Кудрявцев, 1 том, стр. 39 писал(а):

Следует только исключить тривиальный случай: легко проверить, что для множества, состоящего только из одного нуля, выполняются все свойства I - V (в таком множестве 0 = 1). Множество, в котором имеется хоть один элемент, отличный от нуля, будем для краткости называть нетривиальным.

Свойства I - V - это аксиомы непрерывного упорядоченного поля.

Я как-то для себя отметил, что этот объект называется тривиальным полем. Но далее Кудрявцев в определении поля пишет, что там должно быть минимум 2 элемента.

york в сообщении #1469751 писал(а):

Множители $k$ никак не могут внести вклад в равенство нулю по модулю $n$.

Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

[york]

oleg.k в сообщении #1469754 писал(а):

Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

$k(x-y)$ делится на $n$
У $k$ и $n$ нет общих множителей
Значит $x-y$ делится на $n$

[oleg.k]

york в сообщении #1469757 писал(а):

oleg.k в сообщении #1469754 писал(а):

Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

$k(x-y)$ делится на $n$
У $k$ и $n$ нет общих множителей
Значит $x-y$ делится на $n$

Так и я могу Вот только это надо доказать.

[york]

oleg.k в сообщении #1469762 писал(а):

Так и я могу Вот только это надо доказать.

Если от печки, то смотрите теорему о единственности разложения на простые. Какие кольца с полями?? Это доказывают задолго до них.

[oleg.k]

york в сообщении #1469771 писал(а):

Если от печки, то смотрите теорему о единственности разложения на простые.

Основная теорема арифметики формулируется для натуральных чисел, больших единицы. $k$ - целое. $k(x-y)$ - тоже, вообще говоря, целое. Целое число можно по разному разложить на множители. А простых в его разложении может и не быть.

[iifat]

Чего-то не понимаю, или зачем это всё? Возьмите расширенный алгоритм Еквлида...

[oleg.k]

iifat в сообщении #1469780 писал(а):

Чего-то не понимаю, или зачем это всё? Возьмите расширенный алгоритм Еквлида...

А можно поподробнее? Алгоритм Евклида нужен для того, чтобы находить НОД двух целых чисел. Я как то не очень понимаю, к чему он здесь относится..

[nnosipov]

oleg.k в сообщении #1469844 писал(а):

Алгоритм Евклида нужен для того, чтобы находить НОД двух целых чисел.

Да, он такой. Но лучше прочитать все слова.

[oleg.k]

nnosipov в сообщении #1469883 писал(а):

Но лучше прочитать все слова.

Выразили мы остатки линейно через $a$ и $b$ вот и весь обобщенный алгоритм Евклида. Простейшее следствие обычного алгоритма Евклида. В них нету никакой принципиальной разницы. Я бы был признателен, если бы Вы намекнули для чего он в моей задаче нужен.

-- 21.06.2020, 00:15 --

не обобщенный, а расширенный точнее

[Someone]

oleg.k в сообщении #1469899 писал(а):

если бы Вы намекнули для чего он в моей задаче нужен.

Дык, он сразу же даёт обратный элемент в вашей задаче.

[oleg.k]

Someone в сообщении #1469902 писал(а):

Дык, он сразу же даёт обратный элемент в вашей задаче.

Расширенный алгоритм Евклида дает разложение НОД($k,n$) в линейную комбинацию $ak + bn$, где $a, b \in \mathbb{Z}$. Но НОД($k,n$) = 1 (т.к. они взаимно простые). Где тут обратный элемент?

-- 21.06.2020, 00:36 --

аааа

$[ak + bn]$ вот же он

-- 21.06.2020, 00:38 --

а метод от противного можно как-нибудь до ума довести?

-- 21.06.2020, 00:42 --

точнее не так. $[ak + bn] = [1]$

[Someone]

oleg.k в сообщении #1469903 писал(а):

$[ak + bn]$ вот же он

Нет. У Вас $ak+bn$ равно чему? И какой будет обратный элемент?