Кільце цілих р-адичних чисел. Проблема представлення даних Безліч цілих чисел є кільцем
У різних розділах математики, а також у застосуванні математики в техніці, часто зустрічається ситуація, коли операції алгебри проводяться не над числами, а над об'єктами іншої природи. Наприклад додавання матриць, множення матриць, додавання векторів, операції над багаточленами, операції над лінійними перетвореннями і т.д.
Визначення 1. Кільцем називається безліч математичних об'єктів, у якому визначено дві дії - "складання" та "множення", які зіставляють упорядкованим парам елементів їх "суму" і "твір", що є елементами тієї самої множини. Дані дії відповідають таким вимогам:
1.a+b=b+a(Комутативність складання).
2.(a+b)+c=a+(b+c)(Асоціативність складання).
3. Існує нульовий елемент 0 такий, що a+0=a, за будь-якого a.
4. Для будь-кого aіснує протилежний елемент - aтакий, що a+(−a)=0.
5. (a+b)c=ac+bc(Ліва дистрибутивність).
5".c(a+b)=ca+cb(Права дистрибутивність).
Вимоги 2, 3, 4 означають, що безліч математичних об'єктів утворює групу, а разом з пунктом 1 ми маємо справу з комутативною (абельною) групою щодо додавання.
Як очевидно з визначення, у загальному визначенні кільця на множення не накладається жодних обмежень, крім дистрибутивності зі складанням. Проте за різних ситуаціях виникає необхідність розглядати кільця з додатковими вимогами.
6. (ab)c=a(bc)(Асоціативність множення).
7.ab=ba(Комутативність множення).
8. Існування одиничного елемента 1, тобто. такого a· 1 = 1 · a=a, для будь-якого елемента a.
9. Для будь-якого елемента aіснує зворотний елемент a−1 такий, що aa −1 =a −1 a= 1.
У різних кільцях 6, 7, 8, 9 можуть виконуватись як окремо, так і в різних комбінаціях.
Кільце називається асоціативним, якщо виконується умова 6, комутативним, якщо виконано умову 7, комутативним та асоціативним якщо виконані умови 6 та 7. Кільце називається кільцем з одиницею, якщо виконано умову 8.
Приклади кілець:
1. Безліч квадратних матриць.
Справді. Виконання пунктів 1-5, 5" очевидна. Нульовим елементом є нульова матриця. Крім цього виконується пункт 6 (асоціативність множення), пункт 8 (одиничним елементом є одинична матриця). Пункти 7 і 9 не виконуються тому що в загальному випадку множення квадратних матриць некомутативна, а також не завжди існує зворотне до квадратної матриці.
2. Безліч всіх комплексних чисел.
3. Безліч всіх дійсних чисел.
4. Безліч всіх раціональних чисел.
5. Безліч всіх цілих чисел.
Визначення 2. Будь-яка система чисел, що містить суму, різницю та добуток будь-яких двох своїх чисел, називається числовим кільцем.
Приклади 2-5 є числовими кільцями. Числовими кільцями є також всі парні числа, а також усі цілі числа, що діляться без залишку на деяке натуральне число n. Зазначимо, що багато непарних чисел не є кільцем т.к. сума двох непарних чисел є парним числом.
Визначення:
Сумою і добутком цілих р-адичних чисел, що визначаються послідовностями і називаються цілі р-адичні числа, що визначаються відповідно до послідовностей і.
Щоб бути впевненим у коректності цього визначення, ми повинні довести, що послідовності визначають деякі цілі - адичні числа і що ці числа залежать тільки від, а не від вибору визначальних їх послідовностей. Обидві ці властивості доводяться шляхом очевидної перевірки.
Очевидно, що при даному нам визначенні дій над цілими - адичними числами вони утворюють комунікативне кільце, що містить кільце цілих раціональних чисел як підкільце.
Подільність цілих - адичних чисел визначається так само,як і в будь-якому іншому кільці: , якщо існує таке ціле - адичне число, що
Для дослідження властивостей розподілу важливо знати, які ті цілі – адичні числа, для яких існують зворотні цілі – адичні числа. Такі числа називають дільниками одиниці чи одиницями. Ми їх називатимемо - адичними одиницями.
Теорема 1:
Ціле - адичне число, що визначається послідовністю, тоді і лише тоді є одиницею, коли.
Доказ:
Нехай є одиницею, тоді існує таке ціле – адичне число, що. Якщо визначається послідовністю, то умова означає, що. Зокрема, отже, Назад, нехай З умови легко випливає, що, отже. Отже, для будь-якого n можна знайти таке, що справедливе порівняння. Так як і, то. Це означає, що послідовність визначає деяке ціле - адическое число Порівняння показують, що, тобто. що є одиницею.
З доведеної теореми випливає, що ціле раціональне число. Будучи розглянуто як елемент кільця, тоді і лише тоді є одиницею, коли. Якщо ця умова виконана, міститься в. Звідси випливає, будь-яке ціле раціональне b ділиться на таке a в, тобто. що будь-яке раціональне число виду b/a, де a і b цілі і, міститься в Раціональні числа такого виду називаються цілими. Вони утворюють явним чином кільце. Отриманий результат можна тепер сформулювати так:
Наслідок:
Кільце цілих - адичних чисел містить підкільце, ізоморфне кільце- цілих раціональних чисел.
Дробові p-адичні числа
Визначення:
Дроб виду, k >= 0 визначає дробове p-адичне число або просто p-адичне число. Два дроби, і, визначають одне і теж p -адічне число, якщо в.
Сукупність всіх p-адичних чисел позначається p. Легко перевірити, що операції додавання та множення продовжуються з p на p і перетворюють p на поле.
2.9. Теорема. Будь-яке p -адичне число єдиним чином представляється у вигляді
де m - ціле число, а - одиниця кільця p.
2.10. Теорема. Будь-яке відмінне від нуля p -адичне число однозначно представляється як
Властивості:Поле p-адичних чисел містить у собі поле раціональних чисел. Неважко довести, що будь-яке ціле p-адичне число некратне p оборотне в кільці p , а кратне p однозначно записується у вигляді, де x кратно p і тому оборотне, а. Тому будь-який ненульовий елемент поля p може бути записаний у вигляді де x не кратно p, а m будь-яке; якщо m негативно, то, виходячи з уявлення цілих p-адичних чисел у вигляді послідовності цифр у p-ічній системі числення, ми можемо записати таке p-адичне число у вигляді послідовності, тобто формально подати у вигляді p-ичної дроби з кінцевим числом цифр після коми та, можливо, нескінченним числом ненульових цифр до коми. Поділ таких чисел можна також виробляти аналогічно «шкільному» правилу, але починаючи з молодших, а чи не старших розрядів числа.
З курсу програмування відомо, що ціле число може бути представлене в пам'яті комп'ютера різними способами, зокрема, це уявлення залежить від того, як воно описано: як величина типу integer або real , або string . При цьому в більшості мов програмування під цілими числами розуміються числа з обмеженого діапазону: типовий випадок - від -2 15 = -32768 до 2 15 - 1 = 32767 . Системи комп'ютерної алгебримають справу з великими цілими числами, зокрема, будь-яка така система вміє обчислювати та виводити у десятковому записі числа виду 1000 ! (більше тисячі знаків).
В даному курсі ми розглядатимемо уявлення цілих чисел у символьному вигляді і не вдаватимемося в подробиці, яка пам'ять відводиться для запису одного символу (біт, байт або інша). Найбільш поширеним є уявлення цілих чисел у позиційних системах числення. Така система визначається вибором підстави числення, наприклад, 10 . Безліч десяткових цілих чисел зазвичай описується так:
Виписане визначення цілих чисел дає однозначність уявлення кожного такого числа, і аналогічне визначення (тільки, можливо, з іншою основою) використовується в більшості систем комп'ютерної алгебри. Користуючись таким уявленням, зручно реалізувати арифметичні операції над цілими числами. У цьому додавання і віднімання є щодо " дешевими " операціями, а множення і розподіл - " дорогими " . Оцінюючи складності арифметичних операцій слід враховувати як вартість елементарної операції (однорозрядної), і кількість однорозрядних операцій виконання будь-якої дії над багатозначними числами. Складність множення і розподілу обумовлена, насамперед, тим, що зі зростанням довжини числа (його запису у будь-якій системі числення) кількість елементарних операцій збільшується за квадратичним законом, на відміну лінійного до складання і віднімання. До того ж, те, що ми зазвичай називаємо алгоритмом розподілу багатозначних чисел, насправді засноване на переборі (часто дуже значному) можливої чергової цифри частки, і при цьому недостатньо просто скористатися правилами розподілу однозначних чисел. При великій підставі системи числення (часто воно може мати порядок 230) цей спосіб малоефективний.
Нехай – натуральне число (записане в десятковій системі). Щоб отримати його запис 
в -ічній системі числення, можна скористатися наступним алгоритмом (позначає цілу частину числа):
Дано: A-натуральне число в десятковій системі числення k > 1-натуральне число Потрібно: A-запис числа A в k-ічній системі числення Початок i:= 0 цикл поки A > 0 bi:= A (mod k) A:= i:= i + 1 кінець циклу dA:= i - 1 Кінець
Для відновлення десяткового числа за послідовністю його k-іншого запису використовується наступний алгоритм:
Дано: k > 1-натуральне число послідовність цифр, що представляють число A в k-ній системі Потрібно: A-запис числа A в десятковій системі числення Початок A:= 0 цикл поки не кінець послідовності b:= черговий елемент послідовності A:= A * k + b кінець циклу Кінець
1.2. ВПРАВА. Поясніть, чому для переведення числа з десяткової системи в k-ічну використовується розподіл, а для перекладу з k-їчної системи в десяткову - множення.
Перемножуючи "стовпчиком" два двозначні числа в десятковій системі числення, ми виконуємо наступні операції:
(10a + b) (10c + d) = 100ac + 10 (ad + bc) + bd,
тобто 4 операції множення однорозрядних чисел, 3 операції додавання та 2 операції множення на ступінь підстави числення, які зводяться до зсуву. Оцінюючи складності можна враховувати все елементарні операції, не поділяючи їх за вагами (у цьому прикладі маємо 9 елементарних операцій). Завдання оптимізації алгоритму зводиться при цьому підході до мінімізації загальної кількості елементарних операцій. Можна, проте, вважати, що множення є " дорогою " операцією, ніж додавання, яке, своєю чергою, " дорожче " зсуву. Враховуючи лише найдорожчі операції, ми отримуємо, що мультиплікативнаскладність множення двоцифрових чисел "стовпчиком" дорівнює 4.
У параграфі 5 розглядаються алгоритми обчислення найбільших спільних дільників та оцінюється їхня складність.
Розглянуте уявлення не є єдиним канонічним уявленням цілих чисел. Як зазначалося, для вибору канонічного уявлення можна скористатися единостью розкладання натурального числа на прості множники. Таке уявлення цілого числа може бути застосоване в тих завданнях, де використовуються тільки операції множення та поділу, тому що вони стають дуже "дешевими", проте незрівнянно зростає вартість операцій складання та віднімання, що перешкоджає використанню такого уявлення. У деяких завданнях відмова від канонічного уявлення дає значний виграш у швидкодії, зокрема може використовуватися часткове розкладання числа на множники. Особливо корисний аналогічний метод під час роботи не з числами, а з багаточленами.
Якщо відомо, що при роботі програми всі цілі обчислення цілі числа обмежені по абсолютній величині деякою заданою константою, то можна використовувати для завдання таких чисел їх систему відрахувань за модулями деяких взаємно простих чисел, твір яких перевершує згадану константу. Обчислення з класами відрахувань виконуються, зазвичай, швидше, ніж арифметика багаторазової точності. А арифметикою багаторазової точності при такому підході потрібно користуватися тільки при введенні або виведенні інформації.
Зазначимо, що поряд із канонічними уявленнями в системах комп'ютерної алгебривикористовуються та інші уявлення. Зокрема, бажано, щоб наявність або відсутність знака + перед цілим числом не впливало на сприйняття його комп'ютером. Таким чином, для позитивних чисел виходить неоднозначне уявлення, хоча форму негативних чисел визначено однозначно.
Інша вимога - на сприйняття числа не повинно впливати наявність нулів перед першою цифрою.
1.3. ВПРАВИ.
- Оцінити кількість однорозрядних множень, що використовуються при множенні стовпчиком m значного числа на n - значне.
- Показати, що два двозначні числа можна перемножити, використовуючи лише 3 множення однозначних чисел і збільшивши число додавань.
- Знайти алгоритм розподілу довгих чисел, що не вимагає великого перебору, знаходячи першу цифру частки.
- Описати алгоритм перекладу натуральних чиселз m-їчної системи числення в n-ічну.
- В римської нумераціїдля запису чисел використовуються такі символи: I – одиниця, V – п'ять, X – десять, L – п'ятдесят, C – сто, D – п'ятсот, M – тисяча. Символ вважається негативним, якщо правіше за нього знайдеться символ більшого числа, і позитивним інакше. Наприклад, число 1948 у цій системі запишеться так: MCMXLVIII. Сформулювати алгоритм переведення числа з римського запису до десяткового і назад. Реалізувати отриманий алгоритм однією з алгоритмічних мов (наприклад, C ). Обмеження на вихідні дані: 1<= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
- Сформулювати алгоритм та написати програму складання натуральних чисел у римській нумерації.
- Говоритимемо, що ми маємо справу з системою числення з змішаною або векторною основою, якщо нам заданий вектор з n натуральних чисел M = (m 1 , . k = k 0 +m 1 (k 1 +m 2 (k 2 +· ··+m n ·k n) . . .))). Написати програму, яка за даними (день тижня, годин, хвилин, секунд) визначає, скільки секунд пройшло з початку тижня (понеділок, 0, 0, 0) = 0, та виконує зворотне перетворення.
Кільце, в якому введено відношення «бути більше за нуль» (позначається а > 0), називається розташованим кільцемякщо для будь-яких елементів цього кільця виконуються дві умови:
1) справедлива одна і тільки одна з умов
a > 0 \/ –a >0 \/ a = 0
2) a > 0 / b > 0 = > a + b > 0 / ab > 0.
Безліч, в якому введено деяке відношення порядку – нестрогого (рефлексивно, антисиметрично та транзитивно), або строгого (антирефлексивно та транзитивно) називається упорядкованим. Якщо виконується закон про трихотомію, то безліч називається лінійноупорядкованим. Якщо ми розглядатимемо не довільне безліч, а деяку систему алгебри, наприклад, кільце або поле, то для впорядкованості такої системи вводяться також вимоги монотонності щодо введених в даній системі (алгебраїчної структурі) операцій. Так упорядкованим кільцем/полемназивається ненульове кільце/поле, в якому введено відношення лінійного порядку (a > b), що задовольняє двом умовам:
1) а > b => a + c > b + c;
2) а > b, c > 0 => a c > b c;
Теорема 1.Будь-яке розташоване кільце є впорядкованою системою (кільцем).
Дійсно, якщо в кільці введено відношення «бути більше 0», то можна ввести і відношення більше для двох довільних елементів, якщо покласти, що
a > b a – b > 0.
Таке ставлення є ставленням суворого, лінійного порядку.
Дане відношення «більше» є антирефлексивним, оскільки умова а > a рівносильна умові а – а > 0, останнє ж суперечить тому, що а – а = 0 (за першою умовою розташованого кільця елемент не може бути одночасно більшим за 0 і дорівнює 0) . Отже, твердження а > a є хибним будь-якого елемента а, тому ставлення антирефлексивно.
Доведемо транзитивність: якщо а > b та b > c, то a > c. За визначенням, з умови теореми випливає, що a – b > 0 і b – c > 0. Складаючи ці два елементи великі нуля, ми знову отримаємо елемент більший за нуль (згідно з другою умовою розташованого кільця):
a - b + b - c = а - с> 0.
Останнє означає, що а > c. Таким чином, введене ставлення є ставленням до суворого порядку. Більше того, дане відношення є відношенням лінійного порядку, тобто для множини натуральних чисел справедлива теорема про трихотомію:
Для будь-яких двох натуральних чисел справедливе одне і лише одне з наступних трьох тверджень:
Дійсно (з першої умови розташованого кільця) для числа a – b справедлива одна і тільки одна з умов:
1) a – b > 0 = > a > b
2) – (a – b) = b – a > 0 => b > a
3) a - b = 0 = > a = b.
Властивості монотонності також виконуються для будь-якого розташованого кільця. Дійсно
1) а > b => a – b > 0 = > a + c – c – b > 0 = > a + c > b + c;
2) а > b /\ c > 0 => a – b > 0 => (за другою умовою розташованого кільця) (a – b)c > 0 => ac – bc > 0 => ac > bc.
Таким чином, ми довели, що будь-яке розташоване кільце є впорядкованим кільцем (упорядкованою системою).
Для кожного розташованого кільця будуть також справедливими такі властивості:
а) a + c > b + c => а > b;
б) а > b / c > d => a + c > b + d;
в) а > b /\ c< 0=>ac< bc;
Ті ж властивості мають місце і для інших знаків<, , .
Доведемо, наприклад, властивість (в). За визначенням, з умови a > b випливає, що а – b > 0, та якщо з умови з< 0 (0 >c) слід, що 0 – з > 0, а значить і число – з > 0, перемножимо два позитивні числа (а – b)(–c). Результат також буде позитивним за другою умовою розташованого кільця, тобто
(а – b)(–c) > 0 => –аc + bc > 0 => bc – ac > 0 => bc > ac => ac< bc,
що і потрібно було довести.
г) аа = а 2 0;
Доказ: За першою умовою розташованого кільця або а > 0, або -а > 0, або а = 0. Розглянемо ці випадки окремо:
1) а > 0 => aa > 0 (за другою умовою розташованого кільця) => a 2 > 0.
2) –а > 0 => (–а)(–а) > 0, але за якістю кільця (–а)(–а) = аа = a 2 > 0.
3) а = 0 => аа = a 2 = 0.
Таким чином, у всіх трьох випадках a 2 або більше нуля, або дорівнює 0, що саме означає, що a 2 ≥ 0 і властивість доведено (зауважимо, що ми також довели, що квадрат елемента розташованого кільця дорівнює 0 тоді і лише тоді, коли сам елемент дорівнює 0).
д) ab = 0 a = 0 \/ b = 0.
Доказ: Припустимо неприємне (ab = 0, але ні а, ні b нулю не рівні). Тоді а можливі лише два варіанти, або а > 0, або – а > 0 (варіант а = 0 виключено нашим припущенням). Кожен із цих двох випадків розпадається ще два випадки залежно від b (або b > 0, чи – b > 0). Тоді можливі 4 варіанти:
a > 0, b > 0 = > ab > 0;
- а > 0, b > 0 => ab< 0;
a >0, b > 0 => ab< 0;
- а> 0 -b> 0 => ab> 0.
Як бачимо, кожен із цих випадків суперечить умові ab = 0. Властивість доведена.
Останнє властивість означає, що кільце є областю цілісності, що також є обов'язковою властивістю упорядкованих систем.
Теорема 1 показує, що будь-яке кільце є впорядкованою системою. Вірно і зворотне – будь-яке впорядковане кільце розташоване. Дійсно, якщо в кільці є відношення a > b і будь-які два елементи кільця можна порівняти між собою, то і 0 порівняємо з будь-яким елементом а, тобто або а > 0, або а< 0, либо а = 0, что почти точно совпадает с первым условием расположенного кольца, требуется только доказать, что условие а < 0 равносильно в упорядоченном кольце условию –a >0. Для того, щоб довести останнє, застосуємо властивість монотонності упорядкованих систем: до правої та лівої частини нерівності а< 0 прибавим –а, в результате чего получим требуемое.
Друга умова розташованого кільця випливає з властивостей монотонності та транзитивності:
a > 0, b > 0 => а + b > 0 + b = b > 0 => a + b >0,
a > 0, b > 0 => аb > 0b = 0 => ab > 0.
Теорема 2.Кільце цілих чисел є розташованим кільцем (упорядкованою системою).
Доказ:Скористаємося визначенням 2 кільця цілих чисел (див. 2.1). Відповідно до даного визначення будь-яке ціле число це чи натуральне число (число n задається як [
a > 0 а N
Тоді перша умова розташованого кільця автоматично виконується для цілих чисел: якщо а - натуральне, то воно більше 0, якщо а - протилежне натуральному, то -а - натуральне, тобто теж більше 0, можливий варіант а = 0, який також робить істинною диз'юнкцію у першій умові розташованого кільця. Справедливість другого умови розташованого кільця випливає з того, що сума і добуток двох натуральних чисел (цілих чисел більше за нуль) є знову число натуральне, а значить і більше за нуль.
Таким чином, всі властивості розміщених кілець автоматично переносяться на всі цілі числа. Крім того, для цілих чисел (але не для довільних розташованих кілець) справедлива теорема про дискретність:
Теорема про дискретність.Між двома сусідніми цілими числами не можна вставити жодне ціле число:
( а, х Z) .
Доказ: розглянемо всі можливі випадки для а, і будемо припускати неприємне, тобто, що існує такий х, що
а< x < a +1.
1) якщо а – натуральне число, то й а + 1 – натуральне. Тоді за теоремою про дискретність для натуральних чисел між а та а / = а + 1 не можна вставити ніяке натуральне число x, тобто х, у всякому разі, не може бути натуральним. Якщо припустимо, що х = 0, то наше припущення, що
а< x < a +1
приведе нас до умови а< 0 < a + 1 (здесь мы просто подставили х = 0), откуда видим, что а < 0, что противоречит тому, что а – натуральное. Если х не натуральное и не 0, но х – целое, значит –х – натуральное, тогда х < 0. При этом, согласно нашему предположению, а < x, что по свойству транзитивности опять приводит к тому, что а < 0, что невозможно, так как а – натуральное. Таким образом, для натуральных а утверждение а < x < a +1 всегда ложно, и теорема справедлива.
2) а = 0. Тоді а + 1 = 1. Якщо виконується умова а< x < a + 1, то мы получим 0 < x < 1, то есть с одной стороны х – натуральное (целое, большее нуля), а с другой стороны х меньше 1, что невозможно для натуральных чисел. Таким образом, для нуля наша теорема справедлива.
3) а – негативно (–a > 0), тоді а + 1 0. Якщо а + 1< 0, то умножая условие а < x < a + 1 на –1 получим:
-а-1< – x < –a,
тобто приходимо до ситуації розглянутої в першому випадку (оскільки і -а-1, і -а натуральні), звідки - х не може бути цілим числом, а значить і х - не може бути цілим. Ситуація, коли а + 1 = 0 означає, що а = -1, тобто
–1 < x < 0.
Помноженням цієї нерівності на (–1), приходимо до випадку 2. Таким чином у всіх ситуаціях теорема справедлива.
Терема Архімеда.Для будь-якого цілого числа і цілого b > 0 існує таке натуральне n, що a< bn.
Для натурального а теорема вже було доведено, оскільки умова b > 0 означає натуральність числа b. Для а 0 теорема також очевидна, оскільки права частина bn є числом натуральним, тобто також більшим за нуль.
У кільці цілих чисел (як і в будь-якому розташованому кільці) можна ввести поняття модуля:
|a| = 
.
Справедливі властивості модулів:
1) | a + b | |a| + | b |;
2) | a - b | |a| – |b|;
3) |a b| = | |b|.
Доказ: 1) Зазначимо, що з визначення очевидно, що | є величина завжди неотрицательная (у разі |a| = a ≥ 0, у другому |a| = –а, але а< 0, откуда –а >0). Також справедливі нерівності | ≥ a, |a| ≥ –a (модуль дорівнює відповідному виразу, якщо воно не негативне, і більше його, якщо воно негативне). Аналогічні нерівності справедливі й у b: |b| ≥ b, | b | ≥ –b. Складаючи відповідні нерівності та застосовуючи властивість (б) розташованих кілець, отримуємо
|a| + | b | ≥ a + b |a| + | b | ≥ – a – b.
Відповідно до визначення модуля
|a + b| = 
,
але обидва висловлювання у правій частині рівності, як показано вище, не перевищують | + |b|, що доводить першу властивість модулів.
2) Замінимо у першому властивості а на а – b. Отримаємо:
|a - b + b| ≤ |a – b| + | b |
|a | ≤ |a – b| + | b |
Перенесемо | b | з правої частини до лівої з протилежним знаком
|a| - | b| ≤ |a – b| => | a - b | |a| – |b|.
Доказ якості 3 надається читачеві.
Завдання:Вирішити в цілих числах рівняння
2у 2 + 3ху - 2х 2 + х - 2у = 5.
Рішення: Розкладемо ліву частину на множники Для цього представимо доданок 3ху = - ху + 4ху
2у 2 + 3ху - 2х 2 + х - 2у = 2у 2 - ху + 4ху - 2х 2 + х - 2у =
У (2у - х) + 2х (2у - х) - (2у - х) = (у + 2х - 1) (2у - х).
Таким чином, наше рівняння може бути переписане у вигляді
(у + 2х - 1) (2у - х) = 5.
Оскільки нам потрібно вирішити його в цілих числах, х і у повинні бути цілими цілими, а значить і множники в лівій частині нашого рівняння теж є числами цілими. Число ж 5 у правій частині нашого рівняння може бути представлене як добуток цілих множників лише 4 способами:
5 = 51 = 15 = –5(–1) = –1(–5). Тому можливі такі варіанти:
1)
2)
3)
4)
Серед перерахованих систем тільки (4) має ціле рішення:
х = 1, у = -2.
Завдання для самостійного рішення
№2.4. Для елементів а, b, c, d довільного розташованого кільця довести властивості:
а) a + c > b + c => а > b; б) а > b / c > d => a + c > b + d.
№2.5. Розв'язати у цілих числах рівняння:
|
а) у 2 - 2ху - 2х = 6; б) 2х 2 - 11ху + 12у 2 = 17; в) 35ху + 5х - 7у = 1; г) х 2 – 3ху + 2у 2 = 3; д) |
е) ху + 3х - 5у + 3 = 0; ж) 2ху - 3у 2 - 4у + 2х = 2; з) ху 2 + х = 48; і) 1! + 2! + 3! + … + n! = y 2; к) х 3 – 2у 3 – 4z 3 = 0 |
;№2.6. Знайдіть чотиризначне число, яке є точним квадратом і таке, що його перші дві цифри рівні між собою та останні дві цифри рівні між собою.
№2.7. Знайдіть двозначне число, що дорівнює сумі чисел його десятків і квадрата його одиниць.
№2.8. Знайдіть двозначне число, яке дорівнює подвоєному добутку його цифр.
№2.9. Доведіть, що різниця між трицифровим числом і числом, записаним тими самими цифрами у зворотному порядку може бути квадратом натурального числа.
№2.10. Знайдіть усі натуральні числа, що закінчуються на 91, які після викреслювання цих цифр зменшуються в ціле число разів.
№2.11. Знайдіть двозначне число, що дорівнює квадрату його одиниць, складеному з кубом його десятків.
№2.12. Знайдіть шестизначне число, що починається з цифри 2, яке від перестановки цієї цифри до кінця числа збільшується в 3 рази.
№2.13. На дошці записано понад 40, але не менше 48 цілих чисел. Середнє арифметичне всіх цих чисел дорівнює – 3, середнє арифметичне позитивних із них дорівнює 4, а середнє арифметичне негативних із них одно – 8. Скільки чисел написано на дошці? Яких чисел більше, позитивних чи негативних? Якою є максимально можлива кількість позитивних чисел?
№2.14. Чи може частка тризначного числа та суми його цифр дорівнювати 89? Чи може це приватне дорівнювати 86? Яким є максимально можливе значення даного приватного?
Натуральні числа є кільцем, оскільки 0 не є натуральним числом, і навіть для натуральних чисел немає натуральних протилежних їм. Структура, що утворюється натуральними числами, називається півкільцем.Більш точно,
Півкільцемназивається комутативна напівгрупа за додаванням і напівгрупа з множення, в якій операції складання та множення пов'язані дистрибутивними законами.
Введемо тепер суворі визначення цілих чисел і доведемо їхню еквівалентність. Виходячи з уявлень про структури алгебри і того факту, що безліч натуральних числа є півкільцем, але не є кільцем, можна ввести таке визначення:
Визначення 1.Кільцем цілих чисел називається мінімальне кільце, що містить у собі півкільце натуральних чисел.
Дане визначення нічого не повідомляє про зовнішньому виглядітаких чисел. У шкільному курсі цілі числа визначаються як натуральні числа, їм протилежні та 0. Дане визначення також можна взяти за основу для побудови суворого визначення.
Визначення 2.Кільцем цілих чисел називається кільце, елементами якого є натуральні числа, їм протилежні та 0 (і тільки вони).
Теорема 1. Визначення 1 та 2 еквівалентні.
Доказ: Позначимо через Z 1 кільце цілих чисел у сенсі визначення 1, а через Z 2 – кільце цілих чисел у сенсі визначення 2. На початку доведемо, що Z 2 включається до Z 1 . Дійсно, всі елементи Z 2 це або натуральні числа (вони належать Z 1 , так як Z 1 містить у собі півкільце натуральних чисел), або їм протилежні (вони теж належать Z 1 , так як Z 1 кільце, а значить для кожного елемента цього кільця існує протилежний, і для кожного натурального n Î Z 1 , –n також належить Z 1), або 0 (0 Î Z 1 , так як Z 1 кільце, а в будь-якому кільці є 0), таким чином, будь-який елемент із Z 2 належить також і Z 1 , отже Z 2 Í Z 1 . З іншого боку, Z 2 містить у собі півкільце натуральних чисел, а Z 1 є мінімальним кільцем, що містить у собі натуральні числа, тобто не може містити в собі жодного іншогокільця, що задовольняє цій умові. Але ми показали, що воно містить у собі Z 2 , отже Z 1 = Z 2 . Теорему доведено.
Визначення 3.Кільцем цілих чисел називається кільце, елементами якого є всі можливі елементи, що у вигляді різниці b – а (всі можливі рішення рівняння a + x = b), де а і b – довільні натуральні числа.
Теорема 2. Визначення 3 еквівалентне двом попереднім.
Доказ: Позначимо через Z 3 кільце цілих чисел у сенсі визначення 3, а через Z 1 = Z 2 , як і раніше, - кільце цілих чисел у сенсі визначення 1 та 2 (їх рівність вже встановлено). Спочатку доведемо, що Z 3 включається до Z 2 . Справді, всі елементи Z 3 можна як деяких різниць натуральних чисел b – а. Для будь-яких двох натуральних чисел за теоремою про трихотомію можливо три варіанти:
І тут різниця b – і навіть є числом натуральним тому належить Z 2 .
У цьому випадку різницю двох рівних між собою елементів позначимо символом 0. Доведемо, що це дійсно нуль кільця, тобто нейтральний елемент щодо додавання. Для цього скористаємося визначенням різниці a – a = x ó a = a + x та доведемо, що b + x = b для будь-якого натурального b. Для доказу достатньо додати до правої та лівої частини рівності a = a + x елемент b, а потім скористатися законом скорочення (всі ці дії можна виконувати, виходячи з відомих властивостей кілець). Нуль належить Z 2 .
У цьому випадку різницю a – b є число натуральне, позначимо
b – a = – (a – b). Доведемо, що елементи a – b та b – a дійсно є протилежними, тобто у сумі дають нуль. Справді, якщо позначити a – b = х, b – a = у, отримаємо, що a = b + х, b = у + a. Складаючи почленно отримані рівності та скорочуючи b, отримаємо a = х + у + a, тобто х + у = а – а = 0. Таким чином a – b = – (b – a) є числом протилежним до натурального, тобто знову належить Z2. Таким чином, Z 3 I Z 2 .
З іншого боку Z 3 містить у собі півкільце натуральних чисел, тому що будь-яке натуральне число n завжди можна уявити як
n = n / – 1 Î Z 3 ,
а значить Z 1 Í Z 3 , так як Z 1 є мінімальним кільцем, що містить у собі натуральні числа. Користуючись вже доведеним фактом, що Z 2 = Z 1 отримуємо Z 1 = Z 2 = Z 3 . Теорему доведено.
Хоча на перший погляд може здатися, що ніяких аксіом у перерахованих визначеннях цілих чисел немає, дані визначення є аксіоматичними, так як у всіх трьох визначеннях говориться, що безліч цілих чисел є кільцем. Тому аксіомами в аксіоматичній теорії цілих чисел служать умови визначення кільця.
Доведемо, що аксіоматична теорія цілих чисел несуперечлива. Для підтвердження необхідно побудувати модель кільця цілих чисел, користуючись свідомо несуперечливою теорією (у разі це може бути лише аксіоматична теорія натуральних чисел).
Згідно з визначенням 3, кожне ціле число є у вигляді різниці двох натуральних z = b – а. Порівняємо кожному цілому числу z відповідну пару
Введене ставлення є рефлексивним, симетричним та транзитивним (доказ надається читачеві).
Як і будь-яке відношення еквівалентності, це ставлення породжує розбиття безлічі різноманітних пар натуральних чисел на класи еквівалентності, які ми позначатимемо як [
1) [
2) [
Покажемо, що запроваджені визначення коректні, тобто залежать від вибору конкретних представників із класів пар. Іншими словами, якщо еквівалентні пари
Доказ: Застосуємо визначення еквівалентності пар:
Почленно склавши рівності (1) та (2), отримаємо:
а + b 1 + с + d 1 = b + a 1 + d + c 1 .
Всі доданки в останній рівності – натуральні числа, тому ми маємо право застосувати комутативний та асоціативний закони складання, що призводить нас до рівності
(а + с) + (b 1 + d 1) = (b + d) + (a 1 + c 1),
Для доказу коректності множення, рівність (1) помножимо на с, отримаємо:
ас + b 1 с = bс + a 1 с.
Потім перепишемо рівність (1) у вигляді b + a 1 = а + b 1 і помножимо на d:
bd+a1d=аd+b1d.
Почленно складемо отримані рівності:
ас + bd + a 1 d + b 1 с = bс + аd + b 1 d + a 1 с,
що означає, що
Потім ту ж процедуру проробимо з рівністю (2), тільки множити його на а 1 і b 1 . Отримаємо:
а 1 с + а 1 d 1 = а 1 d + а 1 c 1
b 1 d + b 1 c 1 = b 1 с + b 1 d 1 ,
а 1 с + b 1 d + b 1 c 1 + а 1 d 1 = а 1 d + b 1 d + b 1 c 1 + а 1 c 1 ó
ó @
(тут ми довели, що ×
Таким чином, коректність введених ухвал доведена.
Далі безпосередньо перевіряються всі властивості кілець: асоціативний закон додавання та множення для класів пар, комутативний закон додавання, дистрибутивні закони. Наведемо як приклад доказ асоціативного закону складання:
Оскільки всі компоненти пар числа натуральні
= <(a + c) +m), (b + d) +n)> =
= <(a + c), (b + d)> +
Інші закони перевіряються аналогічно (зауважимо, що корисним прийомом може бути окреме перетворення лівої і правої частини необхідної рівності одного й тому виду).
Необхідно також довести наявність нейтрального елемента додавання. Їм може бути клас пар виду [<с, с>]. Справді,
[
а + c + b = b + c + a (справедливо будь-яких натуральних чисел).
Крім того, для кожного класу пар
Можна також довести, що введена множина класів пар є комутативне кільце з одиницею (одиницею може бути клас пар [
[
Перевіримо, користуючись цим правилом, справедливість умов С1 та С2 (з визначення додавання натуральних чисел). Умова С1 (а + 1 = а/) у цьому випадку перепишеться у вигляді:
[
a + c / + b = a + b + 1 + c = b + c + a +1 = b + с + a /
(Ще раз нагадаємо, що це компоненти натуральні).
Умова С2 матиме вигляд:
[
Перетворимо окремо ліву та праву частини даної рівності:
[
([
Отже, бачимо, що ліві і праві частини рівні, отже умова С2 справедливо. Доказ умови У1 надається читачеві. Умова У2 є наслідком дистрибутивного закону.
Отже, модель кільця цілих чисел побудована, отже, аксіоматична теорія цілих чисел несуперечлива, якщо несуперечлива аксіоматична теорія натуральних чисел.
Властивості операцій над цілими числами:
2) а×(–b) = –a×b = –(ab)
3) – (– a) = a
4) (–a)×(–b) = ab
5) a×(–1) = – a
6) a – b = – b + a = – (b – a)
7) - a - b = - (a + b)
8) (a – b) ×c = ac – bc
9) (a – b) – c = a – (b + c)
10) a – (b – c) = a – b + c.
Докази всіх властивостей повторюють докази відповідних властивостей для кілець.
1) а + а×0 = а×1 + а×0 = a×(1 + 0) = a×1 = а, тобто а×0 є нейтральним елементом за додаванням.
2) а×(–b) + ab = a(–b + b) = a×0 = 0, тобто елемент а×(–b) є протилежним до елемента а×b.
3) (– a) + a = 0 (за визначенням протилежного елемента). Аналогічно (– a) +(– (– a)) = 0. Прирівнюючи ліві частини рівностей та застосовуючи закон скорочення, отримаємо – (– a) = а.
4) (–a)×(–b) = –(a×(–b)) = –(–(а×b)) = ab.
5) a×(–1) + а = a×(–1) + a×1 = a×(–1 + 1) = a×0 = 0
a×(–1) + а = 0
a×(–1) = –а.
6) За визначенням різниці a – b є така кількість х, що а = х + b. Додаючи до правої та лівої частини рівності –b зліва та користуючись комутативним законом, отримуємо першу рівність.
– b + a + b – a = –b + b + а – a = 0 + 0 = 0, що свідчить друге рівність.
7) – a – b = – 1×a – 1×b = –1×(a +b) = – (a +b).
8) (a – b) ×c = (a +(–1)× b) ×c = ac +(–1)×bc = ac – bc
9) (a - b) - c = х,
a - b = х + c,
a – (b + c) = х, тобто
(a – b) – c = a – (b + c).
10) a – (b – c) = a + (– 1)×(b – c) = a + (– 1×b) + (–1)× (– c) = a – 1×b + 1× c = = a - b + c.
Завдання для самостійного вирішення
№2.1. У правому стовпці таблиці знайти пари еквівалентні парам, наведеним у лівому стовпці таблиці.
| а)<7, 5> | 1) <5, 7> |
| б)<2, 3> | 2) <1, 10> |
| в)<10, 10> | 3) <5, 4> |
| г)<6, 2> | 4) <15, 5> |
| 5) <1, 5> | |
| 6) <9, 9> |
Для кожної пари вказати їй протилежну.
№2.2. Обчислити
а) [<1, 5>] + [ <3, 2>]; б) [<3, 8>] + [<4, 7>];
в) [<7, 4>] – [<8, 3>]; г) [<1, 5>] – [ <3, 2>];
д) [<1, 5>] × [ <2, 2>]; е) [<2, 10>]× [<10, 2>].
№2.3. Для моделі цілих чисел, описаних у даному розділі, перевірити комутативний закон додавання, асоціативний та комутативний закони множення, дистрибутивні закони.
