6027-1 (675530)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Сравнения высших степеней

Вступ

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

Невизначені рівняння 1-го степеня почали розглядатися ще індуськими математиками приблизно з V століття. Деякі такі рівняння з двома і трьома невідомими з'явилися в зв'язку з проблемами, що виникли в астрономії, наприклад, при розгляді питань, зв'язаних з визначенням періодичного повторення небесних явищ.

У другому виданні книги французького математика Баше де Мезір’яка “Problemis plaisans et delectables que se font par les nombres”, що вийшли в 1624 р., зважується невизначене рівняння ax+by=c. Баше де Мезір’як фактично застосовує процес, що зводить до послідовного обчислення не повних часток і розгляду придатних дробів; однак він не розглядав неперервних дробів як таких. Популярний твір Баше де Мезір’яка дуже вплинув на розвиток теорії чисел, так як сприяв виникненню інтересу до цієї області математики.

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

Невизначені рівняння 1-го степеня стали записуватися й розв'язуватися у формі порівняння значно пізніше, починаючи з Гауса. Він вперше систематизував теорію та визначив поняття конгруенції, в своїй книзі “Disquisitiones arithmeticae” (“Дослідження з арифметики”).

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

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

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

1. Конгруенції і класи

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

1.1. Конгруенції та їх основні властивості

Припустимо, що m є натуральне число; розглядатимемо цілі числа в зв'язку з остачами від ділення їх на дане натуральне т, яке називають модулем. Згідно з теоремою про ділення з остачею кожному числу а відповідатиме певна остача r від ділення а на r :

a=mq+r, 0 ≤ r < m.

Якщо двом цілим числам a і b відповідає одна і та сама остача r від ділення їх на m, то вони називаються конгруентними за модулем m. Це позначається символом:

a≡b(mod m) (1)

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

Деякі автори позначають це коротше:

a≡b(m). (1′)

Співвідношення (1) або (1′) між числами називаються порівнянням, або конгруенцією.

Приклади. 48 ≡ 84 (mod 18);

131 ≡ 1 (mod 13);

10 ≡ –1 (mod 11).

Конгруенції мають багато властивостей, подібних до властивостей рівностей.

Властивість 1. Для конгруенцій справджуються три основні закони рівностей: рефлексивності, симетрії і транзитивності, тобто відповідно:

а) a≡a(mod m),

б) з конгруенції a≡b(mod m) випливає, що b≡a(mod m);

в) якщо a≡b(mod m) і b≡c(mod m), то a≡c(mod m).

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

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

Висновок 2. Можна додати до обох частин або відняти від обох частин конгруенції одне і те саме число.

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

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

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

Висновок 2. Обидві частини конгруенції можна підносити до одного і того самого цілого невід'ємного степеня, тобто, якщо a≡b(mod m), то aⁿ≡bⁿ(mod m), де n — ціле ≥0.

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

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

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

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

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

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

Властивість 10. Числа а і b, конгруентні між собою за модулем т, мають з ним одного і того самого найбільшого спільного дільника.

1.2. Класи за даним модулем

Візьмемо деяке натуральне число т; при діленні на т, будь-яких цілих чисел можна дістати тільки т різних невід'ємних остач, а саме: 0, 1,2, ... , т-1. Отже, множина всіх цілих чисел розіб'ється на т класів чисел, що не перетинаються; при цьому числа, які при діленні на т, даватимуть одну і ту саму остачу r (0 ≤ r < т), тобто числа, конгруентні за модулем т, утворюють клас чисел за модулем т.

Із сказаного випливає, що всім числам даного класу відповідає одна і та сама остача r; отже, дістанемо всі числа цього класу, якщо в формі mq+r, де r — стале, припустимо, що q набирає значення всіх цілих чисел.

З означення конгруентності двох чисел а і b за модулем т із щойно сказаного відразу ж випливає таке твердження.

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

Позначимо через C₀ клас чисел, які діляться на т; через C₁— клас чисел, які при діленні на т дають в остачі 1, і т. д. і нарешті, через C_m-1 — клас чисел, які при діленні на т дають в остачі т-1.

Будь-яке число даного класу називається лишком, або представником цього класу. Отже, якщо число a є представником деякого класу за модулем т, то будь-яке інше число b цього класу задовольняє умову: b≡a(mod m), або b=а + тt, де t — деяке ціле число, тобто, інакше кажучи, b = а + тt є загальний вигляд цілих чисел, які належать до того самого класу, що й а.

2. Конгруенції з невідомою величиною

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

2.1. Класи розв'язків конгруенції довільного степеня

Припустимо, що т — натуральне число. Конгруенція виду

f (x) ≡ 0(mod m), (1)

де f (х)= а₀х^п + а₁х^п-1 + . . . + а_n-1x + a_n, є многочлен степеня n з цілими коефіцієнтами і а₀ ≠ 0 (mod m) називається алгебраїчною конгруенцією п-го степеня з одним невідомим x.

Цілі значення х, що задовольняють конгруенцію (1), називаються коренями або розв'язками цієї конгруенції.

Розв'язати конгруенцію — це означає знайти всі значення невідомих, які її задовольняють.

Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок однієї конгруенції є розв’язком іншої.

Теорема 1. Якщо x = x₁ задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем т , що й число x₁, також задовольняє цю конгруенцію, тобто розв'язком буде весь клас чисел

х ≡ х₁(mod т).

Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехай х₂ — будь-яке число, яке належить до того самого класу лишків за модулем т, що й х₁; тоді х₂ ≡ x₁(mod m). За умовою х₁ є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f(x₁) ≡ 0 (mod т), але тоді матиме місце й конгруенція f(x₁) ≡ 0 (mod т), тобто x₂ також буде розв'язком конгруенції. Оскільки x₂ — будь-яке число класу х ≡ х₁(mod т), то весь цей клас задовольнятиме дану конгруенцію.

Розв'язки конгруенції (1), що належать до одного класу чисел за модулем т, приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.

Приклад. Конгруенція

8x⁵ — 12x³ — 13x² — 15x + 6 ≡ 0 (mod 5)

є еквівалентною конгруенції

Зх⁵ — 2x³ — Зx² +1 ≡ 0 (mod 5),

або конгруенції

Зх⁵ + 3x³ + 2x² +1 ≡ 0 (mod 5).

Щоб знайти розв'язки останньої конгруенції, випробуємо, приклад, абсолютно найменші лишки за модулем 5: 0, 1, 2, -2, -1. Безпосередньо видно, що 0, 1, -1 задану конгруенцію не задовольняють. При дальшому випробуванні можна скористатись схемою Горнера ( Див. Додаток) з тією тільки відмінністю, що для полегшення кожного разу можна відкидати числа, кратні модулю.

Отже, конгруенція Зх⁵ + 3x³ + 2x² +1 ≡ 0 (mod 5) не має розв'язків, а тому не має розв'язків і конгруенція

8x⁵ — 12x³ — 13x² — 15x + 6 ≡ 0 (mod 5).

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

Приклад. Конгруенція

x⁴ + х³ + х² + х + 1 ≡ 0 (mod 5),

як ми вище бачили, має один розв'язок: x ≡ 1 (mod 5). Але, якщо обидві частини цієї конгруенції помножити на 5, то дістанемо конгруенцію:

5x⁴ + 5х³ + 5х² + 5х + 5 ≡ 0 (mod 5),

розв'язком якої буде вже будь-яке ціле число. Вона, по суті, перетворюється в конгруенцію 0 ≡ 0 (mod 5).

Конгруенції виду 0 ≡ 0 (mod 5) мають очевидно розв'язком будь-яке ціле значення невідомого х, тобто є тотожною конгруенцією.

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

Теорема 2. Якщо обидві частини конгруенції (1) помножити на ціле число k, взаємно просте з модулем т, то дістанемо конгруенцію, еквівалентну даній.

Справді, припустимо, що

х = α (mod т)

є який-небудь розв'язок конгруенції (1), тоді

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата