Знаймо![]() приховати рекламу
| Цей текст може містити помилки. Порівняння за модулемПлан:
ВведенняПорівняння [1] за модулем натурального числа n - в теорії чисел відношення еквівалентності на кільці цілих чисел, пов'язане з подільністю на n. Факторкольцо по цьому відношенню називається кільцем відрахувань. Сукупність відповідних тотожностей і алгоритмів утворює модульну [2] (або модулярні) арифметику. 1. ВизначенняДва цілих числа a і b можна порівняти по модулю натурального числа n (або равноостаточни при діленні на n), якщо при діленні на n вони дають однакові залишки. Число n називається модулем порівняння. Еквівалентні формулювання: a і b можна порівняти за модулем n, якщо їх різниця a - b ділиться на n без залишку, або якщо a може бути представлено у вигляді a = b + k n , Де k - Деяке ціле число. Наприклад: 32 і -10 порівнянні за модулем 7, так як і Твердження "a і b можна порівняти за модулем n" записується у вигляді: 2. ВластивостіСтавлення порівнянності по модулю натурального числа n має такі властивості:
В силу того, що ставлення порівнянності по модулю володіє цими трьома властивостями, воно є ставленням еквівалентності на безлічі цілих чисел. Будь-які два цілих числа порівнянні за модулю 1. Якщо числа a і b можна порівняти за модулем n, і n ділиться на m, то a і b можна порівняти за модулем m. Для того, щоб числа a і b були порівнянні по модулю n, канонічне розкладання на прості співмножники якого: необхідно і достатньо, щоб Якщо 3. Операції з порівняннями Порівняння з одного й того ж модулю володіють багатьма властивостями звичайних рівностей. Наприклад, їх можна складати, вичитати і множити: якщо числа Порівняння, однак, не можна, взагалі кажучи, ділити один на одного або на інші числа. Приклад:
Не можна також виконувати операції з порівняннями, якщо їх модулі не збігаються. 4. Пов'язані визначення4.1. Класи вирахувань Безліч всіх чисел порівнянних з a за модулем n називається класом відрахувань a за модулем n, і звичайно позначається [A] n або Оскільки порівняння за модулем n є ставленням еквівалентності на безлічі цілих чисел Операції додавання і множення на
Щодо цих операцій безліч 4.2. Системи вирахуваньСистема вирахувань дозволяє здійснювати арифметичні операції над кінцевим набором чисел, не виходячи за його межі. Повна система відрахувань по модулю n - будь-який набір з n попарно непорівнянних за модулем n цілих чисел. Звичайно як повної системи відрахувань по модулю n беруться найменші невід'ємні відрахування
або абсолютно найменші відрахування, що складаються з чисел
у разі непарного n , І чисел у разі парного n . Максимальний набір попарно непорівнянних за модулем n чисел, взаємно простих з n, називається наведеної системою вирахувань по модулю n. Будь-яка наведена система відрахувань по модулю n містить φ (n) елементів, де 5. Рішення порівнянь5.1. Порівняння першого ступеняВ теорії чисел, криптографії та інших областях науки часто виникає завдання відшукання рішень порівняння першого ступеня види: Рішення такого порівняння починається з обчислення НОД (a, m) = d. При цьому можливі 2 випадки:
де a 1 = a / d , b 1 = b / d і m 1 = m / d є цілими числами, причому a 1 і m 1 взаємно прості. Тому число a 1 можна звернути по модулю m 1 , Тобто знайти таке число c, що Практичне обчислення значення c можна здійснити різними способами: за допомогою теореми Ейлера, алгоритму Евкліда, теорії ланцюгових дробів (див. алгоритм) та ін Зокрема, теорема Ейлера дозволяє записати значення c у вигляді: 5.1.1. Приклад Для порівняння Оскільки 2 взаємно просто з модулем 11, то його можна звернути по модулю 11 і знайти 5.2. Порівняння другого ступеняРішення порівнянь другого ступеня зводиться до з'ясування, чи є дане число квадратичним вирахуванням (за допомогою квадратичного закону взаємності) і подальшого обчислення квадратного кореня з даного модулю. 5.3. Системи порівнянь Найпростіша система порівнянь щодо попарно взаємно простих модулів завжди можна залагодити, і її рішення єдино по модулю 6. ІсторіяКитайська теорема про залишки, відома вже багато століть, стверджує (на сучасному математичному мовою), що кільце відрахувань по модулю твори кількох взаємно простих чисел є прямим твором відповідних множника кілець відрахувань. Значною мірою теорія подільності і вирахувань була створена Ейлером. Порівняння за модулем вперше використовувалися Гауссом в його книзі "Арифметичні дослідження", 1801. Він же запропонував утвердилася в математиці символіку для порівнянь. Джерела
Цей текст може містити помилки. Схожі роботи | скачати Схожі роботи: Порівняння Порівняння браузерів Порівняння (програмування) Порівняння IDE Порівняння (риторика) Ознака порівняння Ступені порівняння Порівняння месенджерів |