![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Властивості конгруенції
І. Загальні властивості конгруенцій. 1(рефлексивність) a 2.(транзитивність) Для будь-яких a, b, c є Z, якщо a Дійсно, з означення конгруенції випливає a=b+mq, b= c+mt, q,tєZ, підставивши другу рівність в першу маємо a=c+mt+mq= c +m(t+q), а отже за означенням a 3. (симетричність) Для будь-яких a і b єZ з того що a Дійсно, оскільки a Оскільки виконуються ці три властивості, то відношення конгруентності є відношенням еквівалентності. 4. Кожне число конгруентне зі своєю остачею при діленні на m, тобто якщо a=mq+r, 0≤ r ≤m то a Д-ня випливає з 3) означення конгруентності. 5. Якщо конгруенція має місце по модулю m, то вона має місце і по будь-якому модулю, що є дільником числа m. З умови маємо (a-b)÷m, нехай d-дільник m, тоді (a-b)÷ d, або a 6. Якщо конгруенція має місце по кількох модулях, то вона має місце і по їх НСК, тобто Доведення. Припустимо, що і З даних конгруенцій випливає, що різниця (a-b) ділиться націло на числа m1, m2,…mk, тому (a-b) повинно ділитися на їх НСК. Отже, ІІ. Властивості конгруенцій, пов’язані з додаванням і відніманням. 1. Дві конгруенції за одним і тим же модулем можна почленно додавати та віднімати. Д-ня. Нехай a a-c 2. До будь-якої частини конгруенції можна додавати або віднімати число кратне модулю т.б. a З умови випливає, що a= b+mq, покладемо q=t+q1 тоді a= b+m(t+q1) або a=b+mt+mq1 → a 3. До обох частин конгруенції можна додати (відняти) одне й те ж саме ціле число: a На основі рефлективності конгруентності число с конгруентне само з собою за будь-яким модулем в тому числі і за m. Конгруенції за однаковим модулем можна почленно додавати з чого випливає властивість. 4. З однієї частини конгруенції в іншу можна перенести число взявши його з протилежним знаком. a+c Використавши 1 і 7 маємо a+c ІІІ. Властивості конгруенцій, пов’язані з множенням та діленням. 1. Дві конгруенції з одним і тим же модулем можна почленно перемножити За умовою a=b+mq, c= d+mt, q,tєZ перемноживши рівності дістанемо ac=bd+m(dq+bt+mqt), перепозначивши маємо ac=bd+mq' 2. Обидві частини конгруенції можна підносити до одного і того ж натурального степеня Доведення випливає є попередньої властивості: беремо n штук рівних конгруенцій і перемножуємо. 3. Обидві частини конгруенції можна помножити на одне й те ж саме ціле число. Оскільки a=b+mq то aс=bс+mqс, взявши qс=q' одержимо ac 4. Обидві частини конгруенції і модуль можна скоротити на їх спільний дільник. Справді, ac 5. Якщо одна частина конгруенції і модуль діляться на деяке число, то і інша частина конгруенції повинна ділитися на це число. З означення конгруенції випливає: a=b+mq, qєZ або a - mq =b, оскільки a÷k, m÷k → a - mq÷k →b÷k 6. Обидві частини конгруенції і модуль можна скоротити на їх спільний дільник 7. Якщо одна частина конгруенції і модуль діляться на деяке число, то і ін. частина конгруенції повинна ділитися на це ж число. 8. 9. Т-ма (Ейлера) Якщо (a,m)=1, то Д-ня. Виберемо будь-яку ЗСЛm (зведену систему лишків) {x1, x2, … xψ(m)} За властивістю система {аx1, аx2, … аxψ(m)}, де (а,m)=1 також утворює ЗСЛm. Очевидно, що при відповідній пере нумерації ax1~xi1,, ax2~xi2, … аxψ(m)~ xψ(m). Одержимо, що відповідні елементи визначають один і той же клас лишків по модулюm тобто aх1 ах2 ………………………. aхψ(m) Перемноживши вказані конгруенції маємо: aψ(m) х1х2…хψ(m)
Як наслідок з теореми Ейлера одержимо малу теорему Ферма Т-ма Якщо p- просте число, і (a,p)=1, то Д-ня. Покладемо в теоремі Ейлера m=p, тоді (a,p)=1 тоді і тільки тоді коли a÷p. Враховуючи, що φ(p)=p-1,та підставляючи цей вираз в теорему Ейлера будемо мати Наслідок Якщо аєZ, p – просте число, то (ap - a)÷p. Д-ня.1) Якщо (a,p)=1, то за малою теоремою Ферма
2)Нехай (a,p)≠1 →a÷p →(ap - a)÷p.
9. Функція Ейлера та її властивості. Теорема про мультиплікативність функції Ейлера. Функція, яка визначає кількість натуральних чисел, що не перевищують даного і взаємно прості з ним називається функцією Ейлера. Позначають Date: 2015-04-23; view: 1323; Нарушение авторских прав |