8. Конгруентність цілих чисел.

Теорема Ейлера і Ферма.

Т-ма. Нехай a і b цілі числа, mєN тоді еквівалентні між собою 3 умови

1 a і b дають однакові остачі при діленні на m: a=mq₁+r, b=mq₂+r, 0≤ r ≤m

2 (a-b)÷mєZ

3 Числа a і b відрізняються на ціле число, що є кратним m: a=b+mq, qєZ

Д-ня Доведемо еквівалентність умов за схемою 1→2→3→1

1) покажемо, що з 1→2. За умовою a=mq₁+r, b=mq₂+r, віднімемо рівності: a-b=m(q₁-q₂). Оскільки m(q₁-q₂)÷m то (a-b)÷m, тобто виконується 2

2) покажемо, що2→3. Нехай

(a-b)÷m, за означенням подільності націло a-b=mq, qєZ, звідки a=b+mq, тобто виконується умова 3.

3) 3→1. Нехай виконується a=b+mq, qєZ, або це можна переписати a-b=mq Розділимо a і b на m з остачею:

_ a=mq₁+r₁ 0≤ r₁ r₂ <m

b=mq₂+r₂

віднімемо почленно останні рівності

a-b = m(q₁-q₂)+(r₁-r₂) враховуючи рівність a-b=mq приходимо до висновку, що q₁-q₂ =0 , r₁-r₂ =0 і числа a і b дають однакові остачі при діленні на m. ▲

Таким чином, вказана теорема з різних сторін характеризує одну й ту ж саму властивість подільності чисел a і b на число m.

Означ. Нехай a і b єZ, mєN. Числа a і b називають конгруентними по модулю m, якщо виконується хоча б одна із умов 1-3 вказаної теореми. Позначення:

З означення маємо, що

1.a=mq₁+r або . b =mq₂+r,

↔2. (a-b)÷mєZ

3.a=b+mq, qєZ

Властивості конгруенції.

1(рефлексивність) aa(modm) дійсно (a–a )÷m для будь-якого m

2.(транзитивність) Для будь-яких a, b, c є Z, якщо ab(modm), bc(modm), то ac(mod m)

Дійсно, з означення конгруенції випливає a=b+mq, b= c+mt, q,tєZ, підставивши другу рівність в першу маємо a=c+mt+mq= c +m(t+q), а отже за означенням ac(mod m)

3. (симетричність) Для будь-яких a і b єZ з того що ab(modm), випливає, що ba(modm)

Дійсно, оскільки ab(modm), то (a-b)÷m, звідки -(b-a)÷m і (b-a)÷m → ba(modm).

Оскільки виконуються ці три властивості, то відношення конгруентності є відношенням еквівалентності.

4. Кожне число конгруентне зі своєю остачею при діленні на m, тобто якщо a=mq+r, 0≤ r ≤m то ar(modm).

Д-ня випливає з 3) означення конгруентності.

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

З умови маємо (a-b)÷m , нехай d- дільник m, тоді (a-b)÷ d, або ab(mod d).

6. Якщо конгруенція має місце по кількох модулях, то вона має місце і по їх НСК.

Нехай a конгруентне b по модулям m₁, m₂,…m_k, це означає, що різниця (a-b) ділиться на числа m₁, m₂,…m_k, але тоді, вона повинна ділитися і на їх НСК з чого слідує властивість.

7. Дві конгруенції за одним і тим же модулем можна почленно додавати та віднімати.

Нехай ab(modm), cd(modm), це означає, що (a-b)÷m, (c-d)÷m, тоді (a-b)+(c-d)÷m, з чого випливає a+cb+d(modm), аналогічно (a-b) - (c-d)÷m, звідки

a-cb-d(modm)

8. До будь-якої частини конгруенції можна додавати або віднімати число кратне модулю т.б. ab(modm)→ a +mtb(modm), ab+mt(modm).

З умови випливає, що a= b+mq, покладемо q=t+q₁ тоді a= b+m(t+q₁) або a=b+mt+mq₁ → ab+mt(modm).

9. До обох частин конгруенції можна додати (відняти) одне й те ж саме ціле число: ab(modm) → a+cb+c(modm)

На основі рефлективності конгруентності число с конгруентне само з собою за будь-яким модулем в тому числі і за m. Конгруенції за однаковим модулем можна почленно додавати з чого випливає властивість.

10 З однієї частини конгруенції в іншу можна перенести число взявши його з протилежним знаком. a+cb(modm)→ab-c(modm)

Використавши 1 і 7 маємо a+cb(modm) -b -b(modm) звідки ab-c(modm).

11. Дві конгруенції з одним і тим же модулем можна почленно перемножити

За умовою a=b+mq, c= d+mt, q,tєZ перемноживши рівності дістанемо

ac=bd+m(dq+bt+mqt), перепозначивши маємо ac=bd+mq' або acbd(modm).

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

Доведення випливає є попередньої властивості: беремо n штук рівних конгруенцій і перемножуємо.

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

Оскільки a=b+mq то aс=bс+mqс, взявши qс=q' одержимо acbс(modm).

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

Справді, acbс(modmс)→ ac=bс+(mс)t→ a=b+mt→ ab(modm).

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

З означення конгруенції випливає: a=b+mq, qєZ або a - mq =b, оскільки a÷k, m÷k → a - mq÷k →b÷k

Т-ма (Ейлера) Якщо (a,m)=1, то

Д-ня. Виберемо будь-яку ЗСЛm (зведену систему лишків) {x₁, x₂, … x_ψ(m)} За властивістю система {аx₁, аx₂, … аx_ψ(m)}, де (а,m)=1 також утворює ЗСЛm. Очевидно, що при відповідній пере нумерації ax₁~x_i1,, ax₂~x_i2, … аx_ψ(m)~ x_ψ(m). Одержимо, що відповідні елементи визначають один і той же клас лишків по модулюm тобто aх₁х_і1(modm),

ах₂х_і2(modm),

……………………….

aх_ψ(m)х_іψ(m)(modm).

Перемноживши вказані конгруенції маємо: a^ψ(m) х₁х₂…х_ψ(m)

х_і1х_і2…х_іψ(m)(modm). Оскільки х₁х₂…х_ψ(m)=х_і1х_і2…х_іψ(m) і кожне з чисел х_к взаємно просте з модулем, то скоротивши останню конгруенцію на вказаний добуток одержимо ▲

Як наслідок з теореми Ейлера одержимо малу теорему Ферма

Т-ма Якщо p- просте число, і (a,p)=1, то .

Д-ня. Покладемо в теоремі Ейлера m=p, тоді (a,p)=1 тоді і тільки тоді коли a÷p. Враховуючи, що φ(p)=p-1,та підставляючи цей вираз в теорему Ейлера будемо мати ▲

Наслідок Якщо аєZ, p – просте число, то (a^p - a)÷p.

Д-ня.1) Якщо (a,p)=1, то за малою теоремою Ферма помноживши обидві частини на а будемо мати:

звідки (a^p - a)÷p.

2)Нехай (a,p)≠1 →a÷p →(a^p - a)÷p.