1.Конгруенції та класи лишків за модулем

В цьому параграфі застосуємо результати попереднього параграфу до кільця цілих чисел.

Насамперед зауважимо, що, як це показано в §2, кільце цілих чисел є кільцем головних ідеалів - всякий ненульовий ідеал вє сукупністю чисел, кратних деякому натуральному числу, його можна записувати у вигляд. Тому конгруенції в цьому кільці є конгруенціями за модулем, Нагадаємо, що за означенням числаконгруентні за модулем, якщо їх різницяділиться націло на. За теоремою 3 §5 числаконгруентні затоді і тільки тоді, коли існуєтаке, що. Для цілих чисел справедливий ще один критерій конгруентності.

Теорема 1. Цілі числа a і b конгруентні за модулем тоді і тільки тоді, коли вони мають однакові остачі при діленні на.

Доведення. За теоремою про ділення з остачею

Звідки . Оскільки перший доданок даної суми ділиться на, то вся сума ділиться натоді і тільки тоді,коли наділиться другий доданок. Ос­таннє, внаслідок того,можливе тоді і тільки тоді, коли, тобто.

З теореми 2 §5 випливає, що сукупність чисел, конгруентних між собою за , співпадає з деяким суміжним класом кільцяза ідеалом. Через це сукупність чисел, конгруентних між собою за, називається класом чисел,конгруентних за, а будь-яке число із цього класу його представником або лишком. Тому клас чисел,конгруентних за модулемще назива­ють класом лишків кільця цілих чисел за модулем.

Як відомо, сукупність суміжних класів кільця K за ідеалом утворює розбиття цього кільця, яке само є кільцем відносно операцій додавання та множення класів - фактор-кільцем K/, Тому сукупність класів лишків кільця цілих чисел за модулемутворює фактор-кільце. З теореми І виходить, що фактор-кільцеє скінченим і міститьрізних класів.

Справді, кожен клас лишків є сукупність всіх цілих чисел, що при діленні надають одну і ту ж остачу. Оскільки всіх остач є- 0,1,2,...,— кожна з них міститься в одному і тільки в одному класі лишків та, навпаки, кожен клас містить одну з цих остач, то всіх різних класів лишків є.

Класи лишків за модулемпозначають часто через, де— остача чисел даного класу при діленні на . Випишемо їх:

Якщо з кожного класу чисел за модулем взяти по одному і тільки, по одному лишку, то одержана система чисел називається повною системою лишків модулем. Найчастіше за повну систему лишків за модулемвибирають найменші невід’ємні лишки 0,1,2,...,або абсолютно найменші лишки, тобто лишки, які в своїх класах є найменшими за абсолютною величиною. За модулем 10, наприклад, повною системою найменших невід'ємних лишків є:

0,1,2,3,4,5,6,7,8,9,

а повною системою абсолютно найменших лишків є

0,1,2,3,4,5,-4,-3,-2,-1

Або

0,1,2,3,4,-5,-4,-3,-2,-1. Крім повних систем лишків, в теорії чисел важливу роль відіграють так звані зведені системи лишків. Щоб підійти до цього поняття, зауважимо, що числа одного і того ж класу в силу відомого співвідношення

Мають модулем один і той же найбільший спільний дільник. Зокрема, всі числа одного і того ж класу є одночасно взаємно простими забо взаємно не простими з, тобто можна говорити про класи чисел, взаємно простих а модулем. При цьому класє взаємно простим за модулемтоді і тільки тоді, Коли. Це означає, що класів чисел, взаємно простих з модулем, є стільки, скільки є чисел, меиших віді взаємно простих, тобто,. Явдо з кожного класу лишків, взаємно простих за модулем, взяти по одному і тільки по одному лишку, то одержана сукупність чисел називається зведеною системою лишків за модулем. Щоб зведену систему, треба з повної системи ликів за модулемвибрити числа, взаємно прості з.