Равенство по модулю

Тема в разделе "WASM.A&O", создана пользователем _DEN_, 14 апр 2005.

  1. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    У комрада Кнута есть такая строчка:



    x mod m = y mod m тогда и только тогда когда x = y по модулю m.



    Что означает "равенство чисел по модулю" ?
     
  2. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    это значит что остатки от деления этих чисел на модуль равны :)



    кроме того, (x-y) делится на m
     
  3. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    Тоесть, если:



    x mod m = y mod m && (x-y) mod m = 0



    то x = y по модулю?



    А может ли быть ситуация, что:



    x mod m = y mod m && (x-y) mod m != 0



    ?
     
  4. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    Это можно считать определением равенства целых чисел по модулю. ;)
     
  5. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    captain cobalt



    Так... Все же, возможно ли что



    x mod m = y mod m && (x-y) mod m != 0
     
  6. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
  7. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    captain cobalt



    Так какой смысл тогда во фразе



    x mod m = y mod m тогда и только тогда когда x = y по модулю m.



    ??? Те же яйца, вид с боку. Назвали одно и тоже по-разному.



    Например, можно сказать что "арксинус равен нулю тогда и только тогда когда аргумент равен нулю" - тут есть хоть какой-то смысл. Это разные вещи, свяанные неким свойством. А вот какой смысл во фразе Кнута тогда?
     
  8. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    Вот я и говорю, что это можно считать определением. ;)
     
  9. slow

    slow New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2004
    Сообщения:
    615
    _DEN_

    смотри:

    1) из равенства x mod m = y mod m следует равенство x = y по модулю m.

    2) из равенства x = y по модулю m следует x mod m = y mod m



    это полная расшифровка фразы Кнута



    смысл в том, что для некоторых x,y,m может случиться, что

    x != y, a x(mod m) = y(mod m)
     
  10. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    Тоесть "равенство по модулю" это просто понятие?
     
  11. slow

    slow New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2004
    Сообщения:
    615
    то есть, забыл вчера написать, равенство по модулю и обычное равенство - это две большие разницы.



    Тоесть "равенство по модулю" это просто понятие?


    а что еще ты ожидал? но это понятие крутое. модульная алгебра позволяет делать очень многое.



    для смеха: я однажды доказывал, что 21=3. Доказал! :)))

    hint: (3*7)(mod 3) = (3*1)(mod 3)
     
  12. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    slow



    Понятие всмысле...



    Например. Общая терия рядов Фурье. Возьмем ортонормированную последовательность. Есть два понятия - последовательность замкнута и последовательность полна. Это разные понятия, но одно следует из другого. А "равенство по подулю" это всего лишь название свойства "x mod m = y mod m" ?
     
  13. slow

    slow New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2004
    Сообщения:
    615
    Можно рассматривать "равенство по модулю" как отношение эквивалентности для чисел. Тогда это отношение разобьет

    множество (целых) чисел на классы, каждый из которых замкнут и обособлен от остальных.



    Тогда смысл фразы Кнута, повторюсь, в том, что равенство по модулю и обычное равенство - это две большие разницы.



    Но фишка заключается вот в чем. В некоторых случаях вычисления в поле R можно свести к вычислениям в суррогатных полях, например полях Галуа GF(p) (р-простое) и существенно их упростить. По этому поводу хочу написать масенькую статейку сюда, да все руки не доходят, а дело-то полезное и несложное.



    з.ы. Приятно, что иногда людям хочется докопаться до исконного смысла вещей :))

    з.з.ы. Ты не учишься на математическом факультете какого-нить вуза?
     
  14. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    slow







    Ну если "Ты" это я, то нет :derisive: По универской специальности я обычный САПРовец :) Математика больше для души.
     
  15. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    Модуль это штука хитрая. Как правило вместе с ним возникает понятия кольца. Понятия кольца я понял на примере часов: Мы не говорим что если сейчас 5 утра то через 24 часа будет 29 часов, а говорим будет теже самые 5 утра,т.к. ограничивающий фактор равен 24, то бишь модуль. Такой ясный пример приведен в книеге Романец, по криптографии.

    Также логично заметить что через 48 часов будет не 53 часа, а теже самые 5 утра, то есть как я понял возникают "новые" абстрактные числа, но вроде вполне осязаемые которые равны цифре 5, это 29,53, и 53+24*n.
     
  16. slow

    slow New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2004
    Сообщения:
    615
    EvilsInterrupt

    знаешь, модуль (как алгебраическая структура) и модуль в смысле число элементов в группе Z(p) - вещи сугубо разные, хоть и называются одинаково.

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

    Не понял, при чем в описываемом тобой примере кольцо? Ты имеешь в виду кольцо Z(p)? Так это всего лишь частный, хотя и важный, пример кольца.

    Плохо понятно, причем тут новые "абстрактные" числа? Никаких таких чисел нет и не может быть. В группе Z(p) операция сложения определяется так:

    a(mod p) + b (mod p)=(a + b)(mod p), то есть результатом операции будет число из Z(p).

    Конечно, можно устроить на множестве Z отношение эквивалентности, относя в одно подмножество те числа, остатки от деления на которые будут равными, факторизовать Z по этому отношению эквивалентности и получить Z(p).

    Никакой особой хитрости в понятии модуля нет, это всего лишь достаточно абстрактное математическое понятие.
     
  17. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    slow



    спасибо тебе. Я подумал и почитал книги многое понял, но такая математика через чур трудна для понимания.



    Для меня модуль видится в таком свете:

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



    Еще я не понял "алгебраическая структура", предпологаю это ряд элементарных операций, которые можно выполнить над рядом чисел. Тогда не совсем понятно "кольцо", если тебе не трудно напиши поподробней
     
  18. shefchick

    shefchick New Member

    Публикаций:
    0
    Регистрация:
    14 апр 2005
    Сообщения:
    22
  19. slow

    slow New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2004
    Сообщения:
    615
    о понятии модуля

    рассмотрим конкретный пример.

    пусть у нас есть множество - "суп", элементы его -

    картошка, огурцы, помидоры. назовем подмножество всех посоленных мамой огурцов в супе словом "огурцы", всех картофелин-"картошка",

    всех привозных азербайджанских помидоров в супе-"помидоры".

    теперь мы каждый элемент супа - можем отнести к конкретному классу - картоху к "картошке", и т.п.

    теперь мы не говорим, что в супе 12 картошин, мы говорим, что в супе есть картошка. это позволяет нам назвать супом не только тот, в котором 12 картошин, но и тот, в котором их, например, 15.

    о понятии кольца

    положим есть у нас множество М, состоящее из каких-нибудь элементов любой природы, условно назовем их "числами". определим на этом множестве операцию(любого смысла), обозначаемую условно знаком "+" и называемую условно "сложением". Эт операция может быть абсолютно любой, лишь бы

    она удовлетворяла некоторым условиям, интуитивно понятным:

    ассоциативность("число 1"+("число 2"+"число 3")=("число 1"+"число 2")+"число 3"), нейтральный элемент("ноль": "число"+"ноль"="число") и замкнутость("сумма" двух "чисел" тоже "число"). Если таковая операция на множестве М у нас введена, и удовлетворяет указанным условиям, то говорят, что на множестве М построена

    алгебраическая структура, называемая полугруппой. Это, наверное, простейшая из алгебраических структур, которые можно определить на множестве.

    Для того, чтобы получилась группа, необходимо, чтобы у каждого элемента был "обратный" ("число"+"обратное к нему"="ноль").

    Если операция в группе обладает коммутативностью(т.е "число 1"+"число 2"="число 2"+"число 1"), то группа называется абелевой.

    Простой пример абелевой группы - множество целых чисел по сложению.

    Кольцо - это алгебраическая структура на множестве, где определены 2 операции - "сложение" и "умножение", причем по сложению кольцо является абелевой группой, по умножению - полугруппой и выполнено некоторое свойство, связывающее операции - дистрибутивность("число 1"*("число 2"+"число 3")=(число1*число2)+("число 1" * "число 3")).



    Пример кольца построить чуток сложнее. писанины оч много. поэтому пока пример писать не буду, но если попросишь- напишу.



    з.ы. уважаемые, не открыть ли отдельную ветвь форума по математике?
     
  20. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    slow







    Я тоже за! Давай устроим голосование? :)