≡×МЕНЮ

• Здоров'я
• Вагітність
• Діти
• Відносини
• Пологи

Кільце цілих чисел його властивості. Кільце цілих р-адичних чисел

З курсу програмування відомо, що ціле число може бути представлене в пам'яті комп'ютера різними способами, зокрема, це уявлення залежить від того, як воно описано: як величина типу 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. ВПРАВИ.

1. Оцінити кількість однорозрядних множень, що використовуються при множенні стовпчиком m значного числа на n - значне.
2. Показати, що два двозначні числа можна перемножити, використовуючи лише 3 множення однозначних чисел і збільшивши число додавань.
3. Знайти алгоритм розподілу довгих чисел, що не вимагає великого перебору при знаходженні першої цифри частки.
4. Описати алгоритм перекладу натуральних чиселз m-їчної системи числення в n-ічну.
5. В римської нумераціїдля запису чисел використовуються такі символи: I – одиниця, V – п'ять, X – десять, L – п'ятдесят, C – сто, D – п'ятсот, M – тисяча. Символ вважається негативним, якщо правіше за нього знайдеться символ більшого числа, і позитивним інакше. Наприклад, число 1948 у цій системі запишеться так: MCMXLVIII. Сформулювати алгоритм переведення числа з римського запису до десяткового і назад. Реалізувати отриманий алгоритм однією з алгоритмічних мов (наприклад, C ). Обмеження на вихідні дані: 1<= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
6. Сформулювати алгоритм та написати програму складання натуральних чисел у римській нумерації.
7. Говоритимемо, що ми маємо справу з системою числення з змішаною або векторною основою, якщо нам заданий вектор з n натуральних чисел M = (m 1 , . k = k 0 +m 1 (k 1 +m 2 (k 2 +· ··+m n ·k n) . . .))). Написати програму, яка за даними (день тижня, годин, хвилин, секунд) визначає, скільки секунд пройшло з початку тижня (понеділок, 0, 0, 0) = 0, та виконує зворотне перетворення.

Федеральне агентство з освіти

Державний освітній заклад вищої професійної освіти

Вятський державний гуманітарний університет

Математичний факультет

Кафедра математичного аналізу та методики
викладання математики

Випускна кваліфікаційна робота

на тему: Кільце цілих чисел Гауса.

Виконав:

студент V курсу

математичного факультету

Гнусов В.В.

___________________________

Науковий керівник:

старший викладач кафедри

алгебри та геометрії

Семенов А.М.

___________________________

Рецензент:

кандидат фіз.-мат. наук, доцент

кафедри алгебри та геометрії

Ковязіна Є.М.

___________________________

Допущена до захисту у ДАК

Зав. кафедрою________________ Вечтомов Є.М.

« »________________

Декан факультету Варанкіна В.І.

Вступ.

Кільце цілих комплексних чисел

було відкрито Карлом Гауссом і названо на його честь гаусовим.

К. Гаус прийшов до думки про можливість і необхідність розширення поняття цілого числа у зв'язку з пошуком алгоритмів розв'язання порівнянь другого ступеня. Він переніс поняття цілого числа до числа виду

, де - довільні цілі числа, а - є коренем рівняння На даній множині К. Гаус вперше побудував теорію ділимості, аналогічну теорії ділимості цілих чисел. Він обґрунтував справедливість основних властивостей ділимості; показав, що в кільці комплексних чисел існує лише чотири оборотні елементи: ; довів справедливість теореми про поділ із залишком, теореми про єдиність розкладання на прості множники; показав які прості натуральні числа залишаться простими і в кільці; з'ясував природу найпростіших цілих комплексних чисел.

Розвинена До. Гауссом теорія, описана у його праці «Арифметичні дослідження», стала фундаментальним відкриттям теорії чисел і алгебри.

У випускній роботі було поставлено такі цілі:

1. Розвинути теорію подільності у кільці чисел Гауса.

2. З'ясувати природу простих гаусових чисел.

3. Показати застосування гаусових чисел під час вирішення звичайних діофантових задач.

РОЗДІЛ 1. ДІЛИМІСТЬ У КІЛЬЦІ ЧИСЕЛ ГАУСА.

Розглянемо багато комплексних чисел. За аналогією з безліччю дійсних чисел у ньому можна виділити деяке підмножина цілих чисел. Безліч чисел виду

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

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

відповідає вектор з початком у точці і з кінцем . Отже, модуль гауссова числа є. Зауважимо, що в розглянутій множині, підмодульне вираз завжди є негативне ціле. Тому в деяких випадках зручніше користуватися нормою , тобто квадрат модуля. Таким чином . Можна виділити такі характеристики норми. Для будь-яких гаусових чисел справедливо: (1) (2) (3) (4) (5) – безліч натуральних чисел, тобто цілих позитивних чисел.

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

Кільце гаусових чисел - це комутативне кільце без дільників 0, оскільки воно є підкільцем поля комплексних чисел. Звідси випливає мультиплікативна скоротливість кільця

, тобто (6)

1.1 ЗВЕРНЕНІ І СПІЛКОВІ ЕЛЕМЕНТИ.

Подивимося, які гаусові числа будуть оборотними. Нейтральним по множенню є

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

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

ділиться на , якщо існує таке, що .Для будь-яких гаусових чисел , а також оборотних справедливі властивості. (7) (8) (9) (10) , де (11) (12)

Легко перевіряються (8), (9), (11), (12). Справедливість (7) випливає з (2), а (10) випливає з (6). В силу властивості (9), елементи множини

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

Визначення 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. Зазначимо, що багато непарних чисел не є кільцем т.к. сума двох непарних чисел є парним числом.