Теореми про еквівалентні порівняння - Методи теорії порівнянь

Теорема 1.Нехай дано порівняння

Тоді мають місце такі твердження:

1)Якщо до обох частин порівняння (3.6) додати будь-який многочлен, то вийде порівняння, еквівалентне порівнянню (3.6).
2) Якщо обидві частини порівняння (3.6) помножити на те саме ціле число, взаємно просте з модулем, то вийде порівняння, еквівалентне порівнянню (3.6).
3) Якщо обидві частини порівняння і модуль помножити на те саме натуральне число, то вийде порівняння, еквівалентне порівнянню (3.6).

Доведення. Нехай клас відрахувань по модулю рішення порівняння (3.6), тобто для порівняння

є вірним порівнянням, отже, порівняння

де, теж правильно. Тому клас відрахувань по модулю є рішенням порівняння

Назад також вірно: якщо рішення порівняння (3.9), то для , буде вірне порівняння (3.8), а, отже, вірне порівняння (3.7), тому є рішенням порівняння (3.6).

Таким чином, порівняння (3.6) та (3.9) еквівалентні.

1) Нехай клас відрахувань по- рішення порівняння (3.6), тоді для, отримаємо правильне порівняння. Візьмемо ціле число, взаємно просте з модулем:. Помножимо останнє порівняння почленно на , отримаємо правильне порівняння:

звідси отримаємо, що клас відрахувань за модулем рішення порівняння

Назад, якщо клас відрахувань за модулем рішення порівняння (3.11), то для правильного порівняння (3.10), отже, буде вірним і порівняння:

(Зауважимо, що , оскільки, інакше було б: ). Тому клас відрахувань за модулем рішення порівняння (3.6).

Таким чином, порівняння (3.6) та (3.11), де будуть еквівалентними.

3) Нехай клас відрахувань по модулю рішення порівняння (3.6), тоді для правильного порівняння, а,значить, вірно і порівняння
4)

для будь - якого натурального числа , тому клас відрахувань за модулем рішення порівняння

Назад, якщо клас відрахувань за модулем рішення порівняння (3.13), то для правильно порівняння (3.12), але тоді за якістю порівнянь правильне порівняння:, тому клас відрахувань по модулю рішення порівняння (3.6). Отже, порівняння (3.6) та (3.13) еквівалентні. Теорему доведено.

Надалі порівняння (3.6) можна замінити еквівалентним порівнянням:

де Теорему 1 доведено.

Теорема 2.Нехай дані порівняння Тоді порівняння еквівалентні.

Доведення. Помножимо почленно вірні порівняння на деяке ціле число:

Складемо почленно отримані порівняння, тоді отримаємо порівняння:

звідси отримаємо, що . Але тоді в. Отже, порівняння та еквівалентні. Теорему 2 доведено.

Зауважимо, з доведеної теореми, зокрема, випливає, що порівняння заміниться еквівалентним, якщо відкинути (або додати) доданок з коефіцієнтами, що поділяються на модуль.

3. 4 Порівняння по простому модулю з одним невідомим

Переходячи від порівнянь 1-го ступеня до порівнянь вищих ступенів, доцільно спочатку розглянути випадок, коли модуль - просте число. У цьому випадку є ряд важливих теорем, які, взагалі кажучи, неправильні для складових модулів. Разом про те теорія порівнянь по простому модулю є основою, де будується вивчення порівнянь по складовому модулю.

У всьому цьому розділі літерою будемо позначати модуль, що є простим числом.

Теорема 1. Якщо, то порівняння

може бути замінено еквівалентним порівнянням з коефіцієнтом при старшому члені, що дорівнює одиниці.

Доведення. Розглянемо порівняння 1-го ступеня; оскільки те порівняннямає рішення. Знайдемо число , що задовольняє цьому порівнянні, тобто таке, що .

Тоді порівняння еквівалентно порівнянню

а отже, порівняння

Приклад 1. Замінити порівняння

еквівалентним порівнянням з коефіцієнтом при старшому члені, що дорівнює 1.

Вирішуємо порівняння та знаходимо. Дане нам порівняння еквівалентно порівнянню

Теорема 2.Якщо і багаточлени з цілими коефіцієнтами, то порівняння по простому модулю

Доведення. Нехай задовольняє порівнянню (3,15), тобто.. Оскільки при будь-якому згідно теоремі Ферма , то

Користуючись тією самою теоремою Ферма, отримуємо, що й задовольняє порівнянні (3,16), то, отже, порівняння (3,15) і (3,16) еквівалентні.

З цієї теореми безпосередньо випливає така.

Теорема 3.Порівняння за простим модулем , ступінь якого більший, ніж цей модуль або дорівнює йому, може бути замінено еквівалентним порівнянням ступеня, меншим .

Доведення. Нехай багаточлен із цілими коефіцієнтами ступеня. При розподілі на ), приватна та залишок будуть також багаточленами з цілими коефіцієнтами:

де ступінь менший за ступінь, тобто. менше ніж . Відповідно до попередньої теореми, порівняння та еквівалентні.

Приклад 2. Порівняння замінити еквівалентним порівнянням ступеня меншого ніж 7.

Рішення. Ми отримаємо еквівалентне порівняння, якщо замінимо на ,на , . Таким чином, задане порівняння еквівалентне порівнянню

Теорема 4.Якщо багаточлени з цілими коефіцієнтами:, і всі коефіцієнти діляться на просте число, то будь-яке рішення порівняння

є рішенням принаймні одного з порівнянь:

Доведення. Нехай рішення порівняння (3.17), тобто. Оскільки всі коефіцієнти діляться на , будемо також мати , тому

З порівнянностітвори з нулем за модулем випливає, що принаймні один із цих множників порівняємо з нулем за цим модулем, тобто. рішення принаймні одного із порівнянь (3.18).

Приклад 3. У порівнянні ліву частину можна подати у вигляді, і ми знаходимо всі рішення цього порівняння, вирішуючи порівняння: , тобто. Всі ці чотири класи задовольняють наше порівняння.

Для складових модулів ця теорема неправильна. Наприклад, порівняння

задовольняє клас , який є рішенням жодного з порівнянь:

Теорема 5.Порівняння ступеня по простому модулю з коефіцієнтом при старшому члені, що не ділиться на , може мати не більше ніж рішень.

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

Припустимо, що твердження теореми правильне всім многочленов () - й ступеня зі старшими коефіцієнтами, які не діляться на простий модуль . Візьмемо тепер довільний багаточлен-й ступеня:

, де, і розглянемо порівняння

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

Якщо це порівняння має рішення, то візьмемо будь-яке число , задовольняє йому, і розділимо на . Відповідно до теореми Безу матимемо: .

Коефіцієнти многочлена-й ступеня можуть бути знайдені за схемою Горнера і є цілі числа, причому .

Оскільки задовольняє порівнянню (3.19), то всі рішення (3,19) знаходяться серед рішень порівнянь і, задовольняючи або одному з них, або обом.

Порівняння має одне рішення, а порівняння є порівнянням () - й ступеня по простому модулю з коефіцієнтом при старшомучлена, що не ділиться на , і, за припущенням, може мати не більше ніж рішень. Отже, порівняння (5) має більше, ніж, тобто. не більше ніж рішень.

Відповідно до принципу математичної індукції, справедливість теореми доведена.

Приклад 4.задовольняє порівнянню Знайти усі рішення цього порівняння.

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

Для складових модулів ця теорема неправильна. Порівняння ступеня за складовим модулем з коефіцієнтом при старшому члені, що не ділиться на модуль або навіть взаємно простому з модулем, може мати більше ніж рішень. Наприклад, порівняння має 4 рішення: .

Теорема 6.Якщо порівняння ступеня за простим модулем має більше ніж рішень, то всі коефіцієнти порівняння діляться на .

Доведення. Візьмемо будь-яке просте число. Якщо порівняння має більше ніж одне рішення, то, тобто. Таким чином, за теореми вірна. Припустимо, що твердження теореми правильне для многочленів ступеня, меншою ніж , тобто. припустимо, що число рішень порівняння ступеня, меншою ніж , може перевищувати ступінь порівняння лише тоді, коли всі коефіцієнти поділяються на модуль .

Візьмемо будь-яке порівняння ступеня:

має більше, ніж рішень. У такому порівнянні ділиться на , а тоді порівняння

еквівалентне порівнянню (3.20) також має більше ніж рішень.

У порівнянні (3.21), ступінь якого менше ніж , а число рішень перевищує ступінь згідно з припущенням, всі коефіцієнти повинні ділитися на , тобто. Оскільки вже раніше було встановлено, що , твердження теореми правильне для . Відповідно до принципу математичної індукції, справедливість теореми доведена.

Теорема 7.Нехай багаточлен з цілими коефіцієнтами та вільним членом , де просте число, причому . Порівняння має рішень тоді й лише тоді, коли всі коефіцієнти залишку від поділу на кратні.

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

1) Доведемо достатність умови. Нехай коефіцієнти поділяються на .

Позначимо через і відповідно кількість рішень порівнянь

Порівняння теореми Ферма має рішень. Кожне з цих рішень є рішенням хоча б одного із порівнянь: (3.22) або (3.23), тобто.

Порівняння (3.23) ступеня має коефіцієнт при старшому члені, рівний одиниці, так що, отже,

Оскільки у своїй , отримуємо , тобто. виділимості коефіцієнтів слід, що число рішень порівняння (3.22) дорівнює .

2) Доведемо необхідність умови. Нехай порівняння (3.22) має рішення. Якщорішення порівняння (3.22), то й разом з тим, оскільки , то , а, отже, відповідно до теореми Ферма, так що

Таким чином, кожне рішення порівняння (3.22) є рішенням порівняння , ступінь якого менше ніж . Отже, всі коефіцієнти поділяються на .

Приклад 5. Порівнянню задовольняють класи та . Чи це порівняння має ще одне рішення?

отже, і, отже, це порівняння має три рішення.

3. 5 Порівняння по простому модулю з кількома невідомими

Деякі з розглянутих нами теорем можна легко узагальнити на випадок порівнянь з декількома невідомими видами:

де многочлен із цілими коефіцієнтами, апросте число.

Теорема 1. Якщо в лівій частині порівняння (3.24) деякі з невідомих зустрічаються у вигляді ступеня з показником, то порівняння (3.24) можна замінити еквівалентним порівнянням, в якому ступінь кожногоз невідомих не перевищує.

Доведення. Порівняння (3.24) еквівалентно порівнянню

де довільний многочлен із цілими коефіцієнтами.

Якщо серед доданків є член виду

де , то ми можемо, взявши

замінити його членом, потім і т.д.

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

Теорема 2.Якщо порівняння ступінь якого по кожному невідомому менше, ніж , задовольняється при всіх цілих, то всі коефіцієнти многочлена діляться на .

Доведення. Проведемо індукцію за кількістю невідомих. При затвердженні теореми вірно. Припустимо, що твердження теореми правильне при , і візьмемо довільне тотожне порівняння, ступінь якого по кожному невідомому менше. Якщо найбільший показник ступеня невідомого , порівняння можна у вигляді:

де багаточлени з цілими коефіцієнтами, ступеня яких по кожному невідомому менше ніж . Якщо замість підставити будь-які цілі числа, то отримаємо тотожне порівняння з невідомою ступенем. Усі коефіцієнти цього порівняння: повинні за будь-яких значеннях ділитися на . Оскільки згідно з припущенням для многочленів відаргументів твердження теореми вірне, всі коефіцієнти цих многочленів, отже, і многочлена повинні ділитися на .

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