ПОНЯТТЯ КОНГРУЕНЦІЇ для учнів-олімпіадників

КОНГРУЕНЦІЇ

Важливе місце в курсі теорії чисел посідають конгруенції та, зокрема, конгруенції вищих степенів. Але до того як вони почали розглядатися, математики різних країн, протягом століть розглядали невизначені рівняння 1-го степеня.


Задачі, що зводяться до розгляду системи порівнянь 1-го степеня, розглядалися в арифметиці китайського математика Сун Тзу, що жив приблизно на початку нашої ери. У нього як у цілого ряду китайських, індуських, арабських і європейських учених, що вирішували такі задачі після нього, питання ставився в наступній формі: знайти число, що дає задані остачі від ділення на задані числа.

Робота Сун Тзу стала відомою в Європі в 1852 р. Незалежно від китайських математиків спосіб рішення задач такого роду був даний індуським математиком Брамегупта (588-660).

Система n порівнянь із n невідомими вивчалася Гауcсом. Повне дослідження систем лінійних конгруенцій було подано в роботах Фробеніуса й Стейніца наприкінці XIX століття.

І так конгруенції вищих степенів були покладені в основу модулярного представлення числа, яке широко використовується в сучасній криптографії, що досить актуальна в наш час високих технологій. Велику увагу цьому питанню приділили такі вчені-дослідники як Ріверс, Адельман та Ширман.

КОНГРУЕНЦІЇ І КЛАСИ

Ряд чисел при діленні на одне і те саме число дають одну і ту ж саму остачу. Постає питання про те, як можна використати цю особливість і які властивості вона має. Відповідь на нього – конгруенції.

Приклад: Дію ділення 7:2=3(ост. 1) можна записати у такому вигляді:

7 = 2•3 + 1,

де число 7 називають ділене, число 2 називають дільником числа 7, число 3 – неповною часткою(результат дії ділення), число 1 називають остачею від ділення 7: 2.

При діленні цілого числа на 7 можна отримати 7 різних остач, тобто, 0, 1, 2, 3, 4, 5, 6.

Взагалі, якщо довільне ціле число поділити на натуральне m, то можна отримати m-1 остачу, тобто 0, 1, 2, 3, 4, 5, 6, …, m-1. На основі цього можна множину Z цілих чисел можна розбити на m підмножин, які будемо позначати Zm (де m – ціле число, що змінюється від 0 до m-1). Розглянемо склад кожної такої підмножини:

Підмножина Z0 складається з безлічі цілих чисел вигляду:

…, -3m, -2m, -m, 0, m, 2m, 3m, …,

– це числа, які діляться націло на m. Цю підмножину називають класом нульових лишків за модулем m. Усі числа класу Z0 задовольняють рівняння в цілих числах:

x=0(mod m), цей вираз читають так: «ікс дорівнює нулю за модулем m», а такий вираз прийнято називати конгруенцією за модулем m. Тобто,

-3m=0(mod m),

-2m =0(mod m),

-m=0(mod m),

m=0(mod m),

2m=0(mod m),

і так далі.

Підмножина Z1 складається з безлічі цілих чисел вигляду:

…, -3m+1, -2m+1, -m+1, 1, m+1, 2m+1, 3m+1, …,

– це числа, які при діленні на m мають остачу(лишок) 1. Цю підмножину називають

класом одиничних лишків за модулем m. Усі числа класу Z1 задовольняють рівняння в цілих

числах:

x=1(mod m),

яке прийнято називати конгруенцією за модулем m. Тобто,

-3m+1=1(mod m),

-2m+1=1(mod m),

-m+1=1(mod m),

m+1=1(mod m),

2m+1=1(mod m),

і так далі.

Підмножина Z2 складається з безлічі цілих чисел вигляду:

…, -3m+2, -2m+2, -m+2, 2, m+2, 2m+2, 3m+2, …

– це числа, які при діленні на m мають остачу(лишок) 2. Цю підмножину називають класом двійкових лишків за модулем m.

Усі числа класу Z2 задовольняють рівняння в цілих числах:

x=2(mod m),

яке прийнято називати конгруенцією за модулем m. Тобто,

-3m+2=2(mod m),

-2m+2=2(mod m),

-m+2=2(mod m),

m+2=2(mod m),

2m+2=2(mod m) ,

і так далі.

Підмножина Z3 складається з безлічі цілих чисел вигляду:

…, -3m+3, -2m+3, -m+3, 3, m+3, 2m+3, 3m+3, …,

– це числа, які при діленні на m мають остачу(лишок) 3. Цю підмножину називають класом трійкових лишків за модулем m.

Усі числа класу Z3 задовольняють рівняння в цілих числах:

x=3(mod m),

яке прийнято називати конгруенцією за модулем m. Тобто,

-3m+3=3(mod m),

-2m+3=3(mod m),

-m+3=3(mod m),

m+3=3(mod m),

2m+3=3(mod m),

і так далі.

Підмножина Z4 складається з безлічі цілих чисел вигляду:

…, -3m+4, -2m+4, -m+4, 4, m+4, 2m+4, 3m+4, …

– це числа, які при діленні на m мають остачу(лишок) 4. Цю підмножину називають класом четвіркових лишків за модулем m.

Усі числа класу Z4 задовольняють рівняння в цілих числах:

x=4(mod m),

яке прийнято називати конгруенцією за модулем m. Тобто,

-3m+4=4(mod m),

-2m+4=4(mod m),

-m+4=4(mod m),

m+4=4(mod m),

2m+4=4(mod m),

і так далі.

Зрозуміло, продовжуючи так далі, ми згодом отримаємо останню підмножину.

Підмножина Zm-1 складається з безлічі цілих чисел вигляду:

…, -2m-1, -m-1, -1, m-1, 2m-1, 3m-1, 4m-1, …

– це числа, які при діленні на m мають остачу(лишок) m-1. Цю підмножину називають класом m-1-oкових лишків за модулем m.

Усі числа класу Zm-1 задовольняють рівняння в цілих числах:

x= m-1(mod m),


яке прийнято називати конгруенцією за модулем m. Тобто,

-3m-1=m-1(mod m),

-2m-1=m-1(mod m),

-m-1=m-1(mod m),

-1= m-1(mod m),

m-1=m-1(mod m),

і так далі.

Досить часто в математичній літературі зустрічається термін «множина цілих чисел розбита на класи еквівалентності за модулем m», цей термін відповідає такому змісту, «множина цілих чисел розбита на класи лишків за модулем m».

Наведіть самостійно приклади у вигляді таблиці з шістьма стовбчиками: класи лишків за модулем 6.

Зверніть увагу на те, що в кожному стовпчику наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 6.

Зауваження.

У двох класах лишків Z1(сюди входять числа вигляду 6n+1), Z5(сюди входять числа вигляду 6n+5) за модулем 6 знаходяться прості числа, окрім двох простих чисел 2 та 3. Але в усіх класах лишків за модулем 6 можна знайти складені числа.

2)Наведіть самостійно приклади у вигляді таблиці з пятьма стовбчиками:класи лишків за модулем 5.

Зверніть увагу на те, що в кожному стовпчику наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 5.

Зауваження. В усіх класах лишків за модулем 5 можна знайти складені та прості числа.



КОНГРУЕНТНІ ЧИСЛА ЗА МОДУЛЕМ m ТА ЇХНІ ВЛАСТИВОСТІ

Означення. Два цілих числа а і b називаються конгруентними за модулем m, якщо числа а і b при діленні на m дають однакові остачі.

Конгруентні числа за модулем m можна записати у вигляді:

a = mg+r,

b = mk+r,



Модуль m є натуральним числом.

Конгруентність за модулем m чисел a та b записуємо так:

а = b(mod m).

Конгруентність чисел а і b за модулем m рівнозначна:

а) рівності а = b+mk, де k=0, ± 1, ± 2, ... ;

б) подільності а-b на m; тобто, а-b ділиться націло на m.

Приклади конгруентних чисел за модулем 5

-7 = -2(mod 5).

3 = 8(mod 5).

13 = -12(mod 5).

5 = 0(mod 5).

Перевірити конгруентність за модулем 5 можна таким чином, відняти від лівої частини

конгруенції -7 праву частину конгруенції -2, тобто -7-(-2)=-5, це число ділиться

націло на 5. Отже числа -7 та -2 є представниками одного класу лишків, а конкретно Z3.

Приклади конгруентних чисел за модулем 7

6 = -1(mod 7).

-4 = 3(mod 7).

13=6(mod 7).

7=0(mod 7).

Властивості конгруентних чисел

1. Два цілих числа, які конгруентні третьому за модулем m, конгруентні між собою за цим самим модулем.

Якщо

а=b(mod m),

с=b(mod m)

то

а=с(mod m).

Зауваження. У конгруенції будь-яке число можна замінити конгруентним йому.

Наприклад,

5=2(mod 3),

5=8(mod 3).

Отже,

8=2(mod 3).

2. Числа, конгруентні за модулем m, належать до одного й того самого класу чисел.

Отже, множину чисел розбиваємо на класи Zr за модулем m.

Всіх класів буде m
Z0, Z1, Z2, , …, Zm-1.

3. Конгруенції за одним і тим самим модулем можна почленно додавати або віднімати.

Наприклад,

а=b(mod m).

c=d(mod m).

а+c=b+d(mod m).

4. Конгруенції за одним і тим самим модулем можна почленно множити. Наприклад,

а=b(mod m).

c=d(mod m).

а•c=b•d(mod m).

5. Члени конгруенції можна переносити з однієї частини в другу, змінюючи їх знак на протилежний.

Якщо

а = b + с(mod m),

то також вірно

а - с = b(mod m),

або
а-b=с (mod m),

або

а - b- c = 0 (mod m).

6. До кожної з частин конгруенції можна додати (або відняти) число, кратне модулю.

Якщо

а=b(mod m),

то

а + km = b(mod m)

а = b + km(mod m),

або

а - km = b(mod m)

а=b - km(mod m).

7. Обидві частини конгруенції можна помножити на одне й те саме ціле число.

Якщо

а=b(mod m),

то

аk=bk(mod m),

де k – ціле число.

8.Обидві частини конгруенції можна піднести до одного й того самого степеня,

показник якого є ціле невід'ємне число.

Якщо

а=b(mod m),

то

а^k=b^k(mod m).

9. Обидві частини конгруенції можна поділити на їх спільний дільник, якщо він

взаємно простий з модулем m.

Якщо

а=b(mod m),

НСД(k, m)=1, то

a:k=b:k(mod m).

10.Обидві частини конгруенції і модуль можна помножити на одне й те саме

натуральне число.

Якщо

а=b(mod m),

то

аk=bk(mod km),

11. Обидві частини конгруенції і модуль можна поділити на будь-

який їх спільний дільник.

Якщо

а=b(mod m),

то

а:k = b:k(mod m:k),

12. Якщо конгруенція має місце за модулем m, то вона матиме місце за будь-яким

дільником k не рівне 1 цього модуля.

а=b(mod m),

то

а=b(mod k),

13. Якщо конгруенція має місце за кількома модулями, то вона матиме місце і за модулем, що дорівнює їх найменшому спільному кратному: НСК (m;n) = k

Якщо

a=b(mod m),

а=b(mod n),

то

а=b(mod k).

14. Якщо одна частина конгруенції і модуль діляться на яке-небудь ціле число, то й друга частина конгруенції повинна ділитись на це число.

15. Якщо в многочлені
f(х₁, х₂,..., х_n) від n цілих величин
х₁ х₂,..., х_n з цілими коефіцієнтами ці величини і коефіцієнти замінити конгруентними з ними величинами і числами за модулем m, то в результаті дістанемо новий многочлен, конгруентний з попереднім за тим самим модулем m.

16. Китайська теорема про остачі. Якщо цілі числа
m₁, m₂, m₃, m₄ , … , m_k , то для довільних цілих чисел
а₁, а₂, а₃, а₄ , … , а_k існує ціле число х, яке задовольняє умови
х = а_і(mod m_і), де i=1,k, При цьому число х можна вважати числом, яке належить довільному наперед заданому півінтервалу довжиною, дорівнює добутку
m₁•m₂•m₃•m₄• … •m_k.

17. Теорема. Будь-яке натуральне число когруентне сумі своїх цифр у десятковій системі числення за модулем 9.

18. Теорема Ейлера. Функція кількості взаємно простих чисел для натурального числа n називається функцією Ейлера f(n), для неї виконується конгруенція
a^f(n)=1(mod n).

20. Теорема Ферма. Для простого числа р виконується конгруенція

а^р-1=1(mod р) або

а^р=а(mod р).

Вправи для самостійного осмислення



1. Утворити класи лишків за модулем 2:

• Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z1 та Z0;

• Виконати додавання та множення над представниками класу Z1 та Z0 і з’ясувати в якому класі знаходяться отримані сума та добуток.

2. Утворити класи лишків за модулем 3. Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z1 та Z2;

• Виконати додавання та множення над представниками класу Z1 та Z2 і з’ясувати в якому класі знаходяться отримані сума та добуток.

3. Утворити класи лишків за модулем 4.

• Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z1 та Z3;

• Виконати додавання та множення над представниками класу Z2 та Z3 і з’ясувати в якому класі знаходяться отримані сума та добуток.

4. Утворити класи лишків за модулем 7.

• Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z3 та Z6;

• Виконати додавання та множення над представниками класу Z4 та Z1 і з’ясувати в якому класі знаходяться отримані сума та добуток.

5. Утворити класи лишків за модулем 8.

• Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z1 та Z0;

• Виконати додавання та множення над представниками класу Z1 та Z0 і з’ясувати в якому класі знаходиться отримані сума та добуток.

6. Утворити класи лишків за модулем 9. Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

• Знайти представника класів Z1 та Z7;

• Виконати додавання та множення над представниками класу Z6 та Z3 і з’ясувати в якому класі знаходиться отримані сума та добуток.




БЛОК 2

Завдання на дослідження


Розподілити усі твердження на три групи:
• перша група тверджень, які завжди правильні на множині натуральних чисел;
• друга група тверджень, які завжди неправильні на множині натуральних чисел;
• третя група тверджень, які не входять до першої та до другої групи.

1. Якщо шестицифрове число не містить рівних цифр, тоді добуток цифр є число парне.

2. В таблиці 3х3 у верхніх кутових клітинках зліва напрво поставили цифри 1 та 2. Розмістити в порожніх клітинках таблиці числа від 3 до 9 так, щоб виконувались дві такі умови: 1) сума чотирьох чисел в будь-якому квадраті 2х2 була однакова; 2) число записане в центрі таблиці було - найбільш можливим. В середній клітинці не може стояти цифра 9.

3. Михайло записує число. Він використовує лише цифри 1,2,3,4,5 і слідує таким правилам: 1) будь-які дві сусідні цифри даного числа відрізняються між собою; 2)всі двоцифрові числа , що складаються з любих двох сусідніх цифр даного числа записаних у порядку зліва - направо, відрізняються між собою. Наприклад, число 123134252 задовольняє умовам , а число 12315412 - ні, гак як число 12 присутнє два рази в записі числа. 25 цифр ? це максимальна кількість цифр, з якого може складатися запис числа Михайло.

4. На дошці написано число 1. Кожну секунду до числа на дошці додають суму його цифр. Через деякий час на дошці з’явитися число 126.

5. Якщо а:b , де a та b натуральні числа, то найбільший спільний дільник а і b(скорочено записують НСД(а, b)) не дорівнює b, тобто НСД(а, b)?b.

6. НСД(х, у)=НСД(х+у, у)=НСД(х+у, х).

7. НСД (х, у)=НСД(х-у, у)=НСД(х-у, х).

8. НСД (х, у)=НСД(7х+3у, 8у)=НСД(7х+3у, 5х).

9. Якщо а:b(ост. к), тобто а=b?m+k, де a , b, m, к натуральні числа, то НСД(а, b)= НСД(а, к)

10. Якщо а, с, к довільні натуральні числа, то НСД(а, с)=НСД(а?к, с?к)

11. Якщо m:n, k:n і mx+ky = n, де x, y, n, m, k – натуральні числа, то найбільший спільний дільник чисел m, k дорівнює n, тобто НСД(m, k) = n.

12. Частки від ділення натуральних чисел m і n на їх найбільший дільник k( тобто діляться на їх НСД(m, n)=k), є два взаємно прості числа, тобто НСД(m:k, n:k) = 1.

13. Якщо n, m, k – натуральні числа, то найбільший спільний дільник чисел m?n та k?n дорівнює НСД(m, k)?n, тобто завжди виконується рівність НСД(m?n, k?n) = НСД(m, k) ? n.

14. Якщо НСД(m, n)=1, тоді НСД(mс, n) ? НСД(n, с), де с, m, k – натуральні числа.

15. Якщо НСД(m, n)=1 і mс:n, тоді с:n, де c, m, k – натуральні числа.

16. Якщо НСД(m, n)=1 і с:m, с:n, тоді с: (n? m), де c, m, k – натуральні числа.