2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Обратимость в кольцах вычетов
Сообщение20.06.2020, 13:32 


17/08/19
246
Теорема $[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$. Но как дальше получить противоречие я не знаю.

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 14:30 
Заслуженный участник
Аватара пользователя


23/07/05
17976
Москва
oleg.k в сообщении #1469741 писал(а):
$\mathbb{Z}/1$ - поле, состоящее из 1 элемента
В определение поля (и тела) входит требование, чтобы оно содержало больше одного элемента. То, что у Вас получилось, называется нулевым кольцом. Это единственное кольцо, в котором единица совпадает с нулём, и единственное кольцо характеристики $1$. Оно, конечно, во всех отношениях замечательное, но называть его полем не следует. Это породит достаточно много неудобств. Например, придётся постоянно говорить "ненулевое поле" или что-нибудь эквивалентное этому.

oleg.k в сообщении #1469741 писал(а):
некоторые авторы этот объект полем не считают
Я не встречал авторов, которые его считают полем. Впрочем, я не алгебраист.

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 14:49 


14/06/20

45
Пусть $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)$
Поэтому в рассмотренном ряду найдётся обратный элемент

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 15:02 


17/08/19
246
Someone в сообщении #1469746 писал(а):
В определение поля (и тела) входит требование, чтобы оно содержало больше одного элемента.
Ну я пользуюсь таким определением поля. Поле - коммутативное ассоциативное кольцо с единицей, где всякий ненулевой элемент обратим. Поле, содержащее только ноль, с т.з. этого определения полем является. Тут чисто терминологический момент.

Someone в сообщении #1469746 писал(а):
Я не встречал авторов, которые его считают полем. Впрочем, я не алгебраист.
Да, Вы правы.

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

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

york в сообщении #1469751 писал(а):
Множители $k$ никак не могут внести вклад в равенство нулю по модулю $n$.
Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 15:12 


14/06/20

45
oleg.k в сообщении #1469754 писал(а):
Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 15:17 


17/08/19
246
york в сообщении #1469757 писал(а):
oleg.k в сообщении #1469754 писал(а):
Что означает "внести вклад в равенство нулю.."? Не могли бы Вы поточнее написать это место?

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


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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 15:55 


14/06/20

45
oleg.k в сообщении #1469762 писал(а):
Так и я могу :D Вот только это надо доказать.

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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 16:01 


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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 16:32 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 21:26 


17/08/19
246
iifat в сообщении #1469780 писал(а):
Чего-то не понимаю, или зачем это всё? Возьмите расширенный алгоритм Еквлида...
А можно поподробнее? Алгоритм Евклида нужен для того, чтобы находить НОД двух целых чисел. Я как то не очень понимаю, к чему он здесь относится..

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение20.06.2020, 22:59 
Заслуженный участник


20/12/10
9062
oleg.k в сообщении #1469844 писал(а):
Алгоритм Евклида нужен для того, чтобы находить НОД двух целых чисел.
Да, он такой. Но лучше прочитать все слова.

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение21.06.2020, 00:09 


17/08/19
246
nnosipov в сообщении #1469883 писал(а):
Но лучше прочитать все слова.
Выразили мы остатки линейно через $a$ и $b$ вот и весь обобщенный алгоритм Евклида. Простейшее следствие обычного алгоритма Евклида. В них нету никакой принципиальной разницы. Я бы был признателен, если бы Вы намекнули для чего он в моей задаче нужен.

-- 21.06.2020, 00:15 --

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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение21.06.2020, 00:28 
Заслуженный участник
Аватара пользователя


23/07/05
17976
Москва
oleg.k в сообщении #1469899 писал(а):
если бы Вы намекнули для чего он в моей задаче нужен.
Дык, он сразу же даёт обратный элемент в вашей задаче.

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение21.06.2020, 00:35 


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

-- 21.06.2020, 00:36 --

аааа :-)

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

-- 21.06.2020, 00:38 --

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

-- 21.06.2020, 00:42 --

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

 Профиль  
                  
 
 Re: Обратимость в кольцах вычетов
Сообщение21.06.2020, 00:43 
Заслуженный участник
Аватара пользователя


23/07/05
17976
Москва
oleg.k в сообщении #1469903 писал(а):
$[ak + bn]$ вот же он
Нет. У Вас $ak+bn$ равно чему? И какой будет обратный элемент?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group