Немного о делителях нуля и о делении на ноль.
Друзья! Совсем недавно я прочёл в одном из комментариев о невозможности деления на ноль. Так ли это?
Для начала зададимся неким множеством M. В множестве может содержаться некоторое число объектов, конечное или бесконечное, или вообще не содержаться объектов. Нас будут интересовать только те множества, которые объекты содержат. В целом не важно, какие объекты содержатся в множестве — стая птиц, косяк рыб, или просто некий набор чисел.
Допустим, у нас есть спецмашинка, в которую мы можем загружать объекты из нашего множества. К примеру, кастрюля, в которую мы можем положить птицу. Пусть эта машинка забирает у нас два объекта, и выдаёт один. К примеру, человек съел два яблока, а на выходе... тоже органическая смесь. Так вот, если у нас есть множество объектов, и операция, которая любым двум объектам множества сопоставляет третий, также принадлежащий этому множеству, то это множество называется группой.
Если быть более точным, то для группы жёстко заданы три аксиомы:
1) Множество замкнуто относительно операции. Т.е. если мы запихнули в оператор два элемента множества, то на выходе обязательно получим некий элемент того же самого множества.
2) Операция ассоциативна. (ab)c=a(bc)
3) Для любого элемента a, принадлежащему M, существует хотя бы одна (левая) единица, такая что 1a=a
4) Для любого элемента a, принадлежащему M, существует хотя бы один (левый) обратный элемент b, такой что ba=1
Итак, это понятие группы. Вообще говоря, групповая операция не обязана быть коммутативной, т.е. ab!=ba в общем случае. Если операция коммутативна, то группа называется абелевой.
Сколько в нашем множестве элементов? Или бесконечно много, или некое конечное число.
Допустим, что мы взяли некий элемент, и начали применять к нему групповую операцию, беря в качестве второго элемента его же. Т.е. проще говоря, мы ищем значение выражения a*a. (Для определённости под a*b будем понимать применение групповой операции к элементам a и b, а не умножение числа a на b). Затем a*a*a. Затем a*a*a*a. Если повторить это (n-1) раз, то получим элемент a^n (не следует понимать под этим обычную степень! Если групповая операция есть сложение, то a^n=a*n).
Как следует из определения группы, a^n принадлежит множеству M. Если мы будем увеличивать n, и если в множестве M количество элементов не бесконечное, то рано или поздно мы найдём такие k и l, что a^k=a^l. Из чего следует, что a^(k-l)=1!
Т.е. взяв любой элемент множества и применяя к нему и ему групповую операцию, мы обязаны будем рано или поздно наткнуться на единицу! Заметьте, что в случае, если мы определяем групповую операцию как естественное сложение, то единицей такой операции будет естественный ноль! Т.е. умножив некий элемент на число мы получим ноль! Чувствуете, к чему всё идёт?
«Ну ладно, - скажет искушённый читатель, - это всё математическая ерунда. Вот попробуй найди такое конкретное множество, и определи на нём такую конкретную операцию, чтобы в нём возник делитель нуля, причём самым, что ни на есть естественным образом!» Друзья! Такое множество уже давно найдено, и успешно используется в криптографии (в частности, в кодировании и передаче данных в этих ваших интернетах). Итак, знакомьтесь: фактормножество остатков!
«Что такое фактормножество?», — наверняка возник у многих вопрос. Ну что же, вернёмся на исходные.
Пусть у нас по-прежнему есть некое конечное множество. Введём отношения между элементами этого множества. Какие отношения? Да какие хотите! Хоть любовные! Вот только у нас не будет аналогов жизненных ситуаций, типа любовного треугольника, ибо это, во-первых, геометрия, а во-вторых, мы рассмотрим особый класс отношений: отношения эквивалентности.
Итак, любые два элемента могут находиться в некоем отношении друг с другом. К примеру, жители одной деревни знакомы друг с другом, или не знакомы. Обозначается это как xRy, что значит "житель x знает жителя y". Если оно не так, то можно ввести отношение xGy, значащее что "x не знаком с y".
Отношение R называют отношением эквивалентности, если для любых трёх элементов множества M x, y и z выполняются три аксиомы:
1) xRx (рефлексивность)
Т.е. каждый элемент находится в отношении с самим собой.
2) xRy -> yRx (симметричность)
Т.е. если Паша безумно любит Машу, то Маша тоже его любит. Взаимность=)
3) aRb & bRc -> aRc (транзитивность)
Т.е. если Паша любит Машу, а Маша любит кота, то кот любит Пашу.
Если мы вводим на конечном множестве отношение эквивалентности, то согласно этому отношению всё множество можно разбить на конечное число подмножеств. В каждом подмножестве все элементы будут попарно находиться друг с с другом в этом отношении, а элементы разных подмножеств друг с другом — нет. В качестве примера представьте себе закрытые сообщества готов, клоунов, скинхедов, эмо и ботанов: каждый ботан есть друг самому себе и любому другому ботану, и аналогично для всех остальных. Нетрудно проверить, что отношение "дружба" является отношением эквивалентности на объединении множеств вышеупомянутых людей. Если же, допустим, некий ботан дружит с готом, то из вышеупомянутых трёх аксиом следует, что любой ботан дружит с любым готом, т.е. вместо пяти закрытых сообществ у нас четыре. Разбиение на сообщества по дружбе среди людей есть, в общем случае, разбиение на классы эквивалентности элементов множества.
Для выполнения некоторых задач может оказаться нужным не каждый элемент из подмножества, а лишь один, который ввиду отношения эквивалентности характеризует всё подмножество. К примеру, если мы хотим провести соцопрос о хобби и времяпровождении, то достаточно взять одного любого ботана, скинхеда, клоуна, гота и эмо, а результаты остальных будут одинаковые (условно). Т.е. вместо множества 100 или 1000 человек мы получили множество, состоящее из 5 его характерных представителей. Такое множество называется фактормножеством M/R, а отображение M->M/R есть отображение факторизации.
Зададимся теперь неким натуральным числом n, и разобьём множество всех целых чисел на фактормножества. Критерием отношения двух чисел выберем равенство остатков от деления числа на n. Чтобы не было путаницы, будем считать остатком от деления числа z на n число r такое, что z=q*n+r, причём n>r>0, а q есть некое целое число. Итак, если некие целые числа x и y находятся в нашем отношении R, (xRy), то x=q1*n+r и y=q2*n+r. Предлагаю читателям самим убедиться в том, что это действительно отношение эквивалентности.
Математики так часто использовали это отношение, что придумали для него особое обозначение. xRy (x=y)mod n
Сколько же будет элементов в нашем фактормножестве? Столько же, сколько может быть остатков от деления любого числа на n ! Их ровно n штук: 0, 1, 2, 3 ... (n-1). Т.е. любому целому числу мы можем, согласно нашему отображению факторизации, сопоставить одно из n чисел. Да будет так!
Чем дальше заходим, тем мы ближе к делителям нуля. Вернёмся к нашим множествам с одной операцией, и добавим ещё одну операцию. Назовём одну из них, для определённости, сложением, а вторую умножением. Множество с двумя операциями называется кольцом. Вообще говоря, для кольца тоже заданы некоторые аксиомы (кольцо есть аддитивная абелева группа с дистрибутивным сложением-умножением и ассоциативным умножением).
Как же нам определить сложение и умножение на нашем фактормножестве остатков? Предлагаю особо не париться. Раз у нас уже все числа заменены их остатками от деления, то и вместо суммы, разности и умножения будем брать остатки от деления этих результатов на n. Теперь, когда в множестве заданы 2 операции, мы называем его кольцом вычетов.
Чтобы было проще понять, я составил таблицы сложения и умножения для двух примеров колец вычетов.
При n=4:
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
* 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
При n=5:
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Ии... Бинго! Что мы видим в таблице умножения для n=4? 2*2mod4=0! Т.е. произведение двух ненулевых элементов дало 0! Как же такое возможно?
Вся суть, на самом деле, в том, что число 4 — составное. В самом деле, для любого n равенство x mod n=0 означает, что n есть делитель x. Для колец вычетов над простыми числами такое невозможно, ведь если n — простое, то числа 2 ... (n-1) не являются его делителями, а значит и их произведение тоже не будет делителем. Если же n=a*b (естественно a меньше n и b меньше n), то как раз произведение этих чисел (принадлежащих нашему кольцу) даёт n mod n=0.
«Но почему мне об этом не рассказывали в школе?!», — возмутится читатель. Потому что в школе мы изучали алгебраические операции над полями. И в курсе матанализа практически сразу вводится понятие поля действительных чисел (как дедекндовых сечений, к примеру). А в поле, согласно его аксиомам, делителей нуля нет! Более того, если у кольца нет делителей нуля (тогда его называют областью целостности), и если кольцо конечное, то оно тоже задаёт поле! Т.е. наше кольцо вычетов по модулю 5, 3, 2, 7, 13, и вообще любому простому числу есть поле. Собственно, эти поля и используются при кодировании данных.
Искушённый читатель наверняка уже заметил, что я немного отклонился от темы. В самом первом предложении было про деление на ноль, а теперь мы уже говорим о каких-то делителях нуля... Нехорошо.
Итак, что есть результат деления b/0=c ? Это есть решение уравнения b=0*c . Вообще говоря, в любом кольце результатом умножения на ноль некоего числа будет ноль. Но, вспомним что 0=a*b. b=a*b*c -> c=a^(-1) Казалось бы, вот оно, решение проблемы: найдено число, которое можно считать результатом деления на ноль! Но нет! Давайте обратимся к таблице умножения для n=4, и отыщем по ней элемент, обратный двойке. Его там нет! Несмотря на то, что мы нашли для наших полей положительные числа, дающие в произведении
Для начала зададимся неким множеством M. В множестве может содержаться некоторое число объектов, конечное или бесконечное, или вообще не содержаться объектов. Нас будут интересовать только те множества, которые объекты содержат. В целом не важно, какие объекты содержатся в множестве — стая птиц, косяк рыб, или просто некий набор чисел.
Допустим, у нас есть спецмашинка, в которую мы можем загружать объекты из нашего множества. К примеру, кастрюля, в которую мы можем положить птицу. Пусть эта машинка забирает у нас два объекта, и выдаёт один. К примеру, человек съел два яблока, а на выходе... тоже органическая смесь. Так вот, если у нас есть множество объектов, и операция, которая любым двум объектам множества сопоставляет третий, также принадлежащий этому множеству, то это множество называется группой.
Если быть более точным, то для группы жёстко заданы три аксиомы:
1) Множество замкнуто относительно операции. Т.е. если мы запихнули в оператор два элемента множества, то на выходе обязательно получим некий элемент того же самого множества.
2) Операция ассоциативна. (ab)c=a(bc)
3) Для любого элемента a, принадлежащему M, существует хотя бы одна (левая) единица, такая что 1a=a
4) Для любого элемента a, принадлежащему M, существует хотя бы один (левый) обратный элемент b, такой что ba=1
Итак, это понятие группы. Вообще говоря, групповая операция не обязана быть коммутативной, т.е. ab!=ba в общем случае. Если операция коммутативна, то группа называется абелевой.
Сколько в нашем множестве элементов? Или бесконечно много, или некое конечное число.
Допустим, что мы взяли некий элемент, и начали применять к нему групповую операцию, беря в качестве второго элемента его же. Т.е. проще говоря, мы ищем значение выражения a*a. (Для определённости под a*b будем понимать применение групповой операции к элементам a и b, а не умножение числа a на b). Затем a*a*a. Затем a*a*a*a. Если повторить это (n-1) раз, то получим элемент a^n (не следует понимать под этим обычную степень! Если групповая операция есть сложение, то a^n=a*n).
Как следует из определения группы, a^n принадлежит множеству M. Если мы будем увеличивать n, и если в множестве M количество элементов не бесконечное, то рано или поздно мы найдём такие k и l, что a^k=a^l. Из чего следует, что a^(k-l)=1!
Т.е. взяв любой элемент множества и применяя к нему и ему групповую операцию, мы обязаны будем рано или поздно наткнуться на единицу! Заметьте, что в случае, если мы определяем групповую операцию как естественное сложение, то единицей такой операции будет естественный ноль! Т.е. умножив некий элемент на число мы получим ноль! Чувствуете, к чему всё идёт?
«Ну ладно, - скажет искушённый читатель, - это всё математическая ерунда. Вот попробуй найди такое конкретное множество, и определи на нём такую конкретную операцию, чтобы в нём возник делитель нуля, причём самым, что ни на есть естественным образом!» Друзья! Такое множество уже давно найдено, и успешно используется в криптографии (в частности, в кодировании и передаче данных в этих ваших интернетах). Итак, знакомьтесь: фактормножество остатков!
«Что такое фактормножество?», — наверняка возник у многих вопрос. Ну что же, вернёмся на исходные.
Пусть у нас по-прежнему есть некое конечное множество. Введём отношения между элементами этого множества. Какие отношения? Да какие хотите! Хоть любовные! Вот только у нас не будет аналогов жизненных ситуаций, типа любовного треугольника, ибо это, во-первых, геометрия, а во-вторых, мы рассмотрим особый класс отношений: отношения эквивалентности.
Итак, любые два элемента могут находиться в некоем отношении друг с другом. К примеру, жители одной деревни знакомы друг с другом, или не знакомы. Обозначается это как xRy, что значит "житель x знает жителя y". Если оно не так, то можно ввести отношение xGy, значащее что "x не знаком с y".
Отношение R называют отношением эквивалентности, если для любых трёх элементов множества M x, y и z выполняются три аксиомы:
1) xRx (рефлексивность)
Т.е. каждый элемент находится в отношении с самим собой.
2) xRy -> yRx (симметричность)
Т.е. если Паша безумно любит Машу, то Маша тоже его любит. Взаимность=)
3) aRb & bRc -> aRc (транзитивность)
Т.е. если Паша любит Машу, а Маша любит кота, то кот любит Пашу.
Если мы вводим на конечном множестве отношение эквивалентности, то согласно этому отношению всё множество можно разбить на конечное число подмножеств. В каждом подмножестве все элементы будут попарно находиться друг с с другом в этом отношении, а элементы разных подмножеств друг с другом — нет. В качестве примера представьте себе закрытые сообщества готов, клоунов, скинхедов, эмо и ботанов: каждый ботан есть друг самому себе и любому другому ботану, и аналогично для всех остальных. Нетрудно проверить, что отношение "дружба" является отношением эквивалентности на объединении множеств вышеупомянутых людей. Если же, допустим, некий ботан дружит с готом, то из вышеупомянутых трёх аксиом следует, что любой ботан дружит с любым готом, т.е. вместо пяти закрытых сообществ у нас четыре. Разбиение на сообщества по дружбе среди людей есть, в общем случае, разбиение на классы эквивалентности элементов множества.
Для выполнения некоторых задач может оказаться нужным не каждый элемент из подмножества, а лишь один, который ввиду отношения эквивалентности характеризует всё подмножество. К примеру, если мы хотим провести соцопрос о хобби и времяпровождении, то достаточно взять одного любого ботана, скинхеда, клоуна, гота и эмо, а результаты остальных будут одинаковые (условно). Т.е. вместо множества 100 или 1000 человек мы получили множество, состоящее из 5 его характерных представителей. Такое множество называется фактормножеством M/R, а отображение M->M/R есть отображение факторизации.
Зададимся теперь неким натуральным числом n, и разобьём множество всех целых чисел на фактормножества. Критерием отношения двух чисел выберем равенство остатков от деления числа на n. Чтобы не было путаницы, будем считать остатком от деления числа z на n число r такое, что z=q*n+r, причём n>r>0, а q есть некое целое число. Итак, если некие целые числа x и y находятся в нашем отношении R, (xRy), то x=q1*n+r и y=q2*n+r. Предлагаю читателям самим убедиться в том, что это действительно отношение эквивалентности.
Математики так часто использовали это отношение, что придумали для него особое обозначение. xRy (x=y)mod n
Сколько же будет элементов в нашем фактормножестве? Столько же, сколько может быть остатков от деления любого числа на n ! Их ровно n штук: 0, 1, 2, 3 ... (n-1). Т.е. любому целому числу мы можем, согласно нашему отображению факторизации, сопоставить одно из n чисел. Да будет так!
Чем дальше заходим, тем мы ближе к делителям нуля. Вернёмся к нашим множествам с одной операцией, и добавим ещё одну операцию. Назовём одну из них, для определённости, сложением, а вторую умножением. Множество с двумя операциями называется кольцом. Вообще говоря, для кольца тоже заданы некоторые аксиомы (кольцо есть аддитивная абелева группа с дистрибутивным сложением-умножением и ассоциативным умножением).
Как же нам определить сложение и умножение на нашем фактормножестве остатков? Предлагаю особо не париться. Раз у нас уже все числа заменены их остатками от деления, то и вместо суммы, разности и умножения будем брать остатки от деления этих результатов на n. Теперь, когда в множестве заданы 2 операции, мы называем его кольцом вычетов.
Чтобы было проще понять, я составил таблицы сложения и умножения для двух примеров колец вычетов.
При n=4:
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
* 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
При n=5:
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Ии... Бинго! Что мы видим в таблице умножения для n=4? 2*2mod4=0! Т.е. произведение двух ненулевых элементов дало 0! Как же такое возможно?
Вся суть, на самом деле, в том, что число 4 — составное. В самом деле, для любого n равенство x mod n=0 означает, что n есть делитель x. Для колец вычетов над простыми числами такое невозможно, ведь если n — простое, то числа 2 ... (n-1) не являются его делителями, а значит и их произведение тоже не будет делителем. Если же n=a*b (естественно a меньше n и b меньше n), то как раз произведение этих чисел (принадлежащих нашему кольцу) даёт n mod n=0.
«Но почему мне об этом не рассказывали в школе?!», — возмутится читатель. Потому что в школе мы изучали алгебраические операции над полями. И в курсе матанализа практически сразу вводится понятие поля действительных чисел (как дедекндовых сечений, к примеру). А в поле, согласно его аксиомам, делителей нуля нет! Более того, если у кольца нет делителей нуля (тогда его называют областью целостности), и если кольцо конечное, то оно тоже задаёт поле! Т.е. наше кольцо вычетов по модулю 5, 3, 2, 7, 13, и вообще любому простому числу есть поле. Собственно, эти поля и используются при кодировании данных.
Искушённый читатель наверняка уже заметил, что я немного отклонился от темы. В самом первом предложении было про деление на ноль, а теперь мы уже говорим о каких-то делителях нуля... Нехорошо.
Итак, что есть результат деления b/0=c ? Это есть решение уравнения b=0*c . Вообще говоря, в любом кольце результатом умножения на ноль некоего числа будет ноль. Но, вспомним что 0=a*b. b=a*b*c -> c=a^(-1) Казалось бы, вот оно, решение проблемы: найдено число, которое можно считать результатом деления на ноль! Но нет! Давайте обратимся к таблице умножения для n=4, и отыщем по ней элемент, обратный двойке. Его там нет! Несмотря на то, что мы нашли для наших полей положительные числа, дающие в произведении