Как уже отмечалось, кольцо имеет перед полукольцом то преимущество, что в кольце однозначно разрешимо уравнение а + х = Ь для любых элементов кольца а и Ь. Это, в частности, и отличает кольцо целых чисел от полукольца натуральных чисел. Возможность всегда однозначно решить такое уравнение позволяет определить в кольце новую операцию - вычитание.

3.1.5. Определение. Пусть дано кольцо (К, +, ?). Для любых а,ЬеК определим b-а как решение уравнения а + х = Ь. Отображение КхК -»К , сопоставляющее всякой упорядоченной паре элементов (Ь>а) элемент b-а , называется вычитанием , а элемент b-а называется разностью элементов baa.

Непосредственной проверкой убеждаемся, что элемент Ь + (-а) является решением уравнения а + х = Ь, а из единственности решения получаем b-a = b + (-а).

Используя понятие разности элементов кольца, установим еще одну характеризацию системы целых чисел, которую также можно взять в качестве ее определения.

3.1.6. Теорема. Система (К, +, ) есть система целых чисел тогда и только тогда , когда она является кольцом, содержащим полукольцо натуральных чисел {N 9 +, ), причем всякий элемент из К представим в виде разности натуральных чисел, то есть для любого а е К существуют пн п е N такие, что а = т - н .

Доказательство. (=>) Пусть К, +, ) есть система целых чисел мае К. Докажем, что элемент а представим в виде

разности натуральных чисел. По условию 2) из определения 3.1.2, К = Z = N^j{0}kj-N. EcnuaeN, то a = (a + 1)-1; если й g{0}, то а = п-п, где п е N ; если же а е -N , то а = -п и а = 1 - (п +1).

(К, +, ) содержит полукольцо натуральных чисел (N, +, ) и всякий элемент из К представим в виде

разности натуральных чисел. Докажем, что К = ;Vu{0}u-;V = Z. По условию, для любого аеК существуют т,п е N такие, что а = т -п. Но для натуральных чисел т и п имеет место одно и только одно из соотношений: либо т = п + к при некотором к е N , либо т = п , либо п = т + 1 при некотором / е N . В первом случае получаем а = т-п = к е N, во втором а = т - п = 0 € {0}, а в третьем а = т - п = -le -N. ?

Упражнения

1. Приведите примеры полуколец, в которых уравнение вида а + .v = h не всегда разрешимо.
2. Докажите, что в кольце уравнение а+х - b имеет единственное решение.
3. Приведите примеры колец: коммутативных и не коммутативных, с единицей и без единицы, конечных и бесконечных.
4. Во всяком ли кольце сложение обладает свойством сократимости (т.е. из а + с = Ь + с следует а -Ь)1 А умножение (всегда ли из ас = Ьс и с* 0 следует а = ЬУ>
5. Докажите, что изоморфный образ кольца целых чисел есть кольцо целых чисел.
6. Говорят, что кольцо (К, +, ) с единицей е имеет характеристику 0, если для любого п € Л" имеет место неравенство не * 0. Докажите, что в кольце характеристики 0 подмножество {не |« е Z J является подкольцом, изоморфным кольцу целых чисел. Отсюда получаем еще одно краткое по форме определение системы целых чисел: кольцо целых чисел ? это минимальное кольцо характеристики 0.
7. Пусть дано кольцо (К, +, > с единицей е. Элемент аеК называется обратимым , если для него существует обратный элемент а~" такой, что а а~ [ = а "а=е. Докажите, что множество обратимых элементов кольца замкнуто относительно умножения, ему принадлежит единица и для всякого элемента этого множества в нем существует обратный элемент. В силу этих свойств это множество называется мультипликативной группой кольца и обозначается К*. Найдите мультипликативные группы колец (Z, +, > и (?Л+, ).
8. Докажите, что пересечение двух подколец есть подкольцо. Найдите пересечения подколец 2Z и 3Z, 6Z и 15Z, kZ и mZ.
9. Подкольцо // коммутативного кольца (К, +, > называется идеалом, если оно выдерживает умножение на любой элемент кольца, т.е. если для любых h е Н

и к еК произведения kh и hk принадлежат Н . Докажите, что для любых элементов а,а 2 *...»е ЛГ, множество Н = {ka + k 2 (i 2 + -- + k n a n } является идеалом кольца (К, +, ), который обозначается через (д,а 2 »-»я я > (читается: идеал, порожденный элементами Л|,а 2 , а„). При;; = 1 такой идеал называется главным и обозначается (а,). Покажите, что mZ является главным идеалом кольца целых чисел (Z, +, >.

10. Докажите, что в кольце целых чисел всякий идеал является главным. (Указа- н и е. Если Н - ненулевой идеал кольца (Z, +, >, то Н = (т) , где т - наименьшее натуральное число в Я.)

Из курса программирования известно, что целое число может быть представлено в памяти компьютера разными способами, в частности, это представление зависит от того, как оно описано: как величина типа integer , или real , или string . При этом в большинстве языков программирования под целыми числами понимаются числа из весьма ограниченного диапазона: типичный случай - от -2 15 = -32768 до 2 15 - 1 = 32767 . Системы компьютерной алгебры имеют дело с большими целыми числами, в частности, любая такая система умеет вычислять и выводить в десятичной записи числа вида 1000 ! (более тысячи знаков).

В данном курсе мы будем рассматривать представление целых чисел в символьном виде и не вдаваться в подробности, какая память отводится для записи одного символа (бит, байт или другая). Наиболее распространенным является представление целых чисел в позиционных системах счисления . Такая система определяется выбором основания счисления, например, 10 . Множество десятичных целых чисел обычно описывается следующим образом:

Выписанное определение целых чисел дает однозначность представления каждого такого числа, и аналогичное определение (только, может быть, с другим основанием) используется в большинстве систем компьютерной алгебры . Пользуясь таким представлением, удобно реализовать арифметические операции над целыми числами. При этом сложение и вычитание являются относительно "дешевыми" операциями, а умножение и деление - "дорогими" . При оценке сложности арифметических операций следует учитывать как стоимость элементарной операции (одноразрядной), так и количество одноразрядных операций для выполнения какого-либо действия над многозначными числами. Сложность умножения и деления обусловлена, в первую очередь, тем, что с ростом длины числа (его записи в какой-либо системе счисления) количество элементарных операций увеличивается по квадратичному закону, в отличие от линейного для сложения и вычитания. К тому же, то, что мы обычно называем алгоритмом деления многозначных чисел, в действительности основано на переборе (часто весьма значительном) возможной очередной цифры частного, и при этом недостаточно просто воспользоваться правилами деления однозначных чисел. При большом основании системы счисления (часто оно может иметь порядок 2 30 ) этот способ малоэффективен.

Пусть - натуральное число (записанное в десятичной системе). Чтобы получить его запись в -ичной системе счисления, можно воспользоваться следующим алгоритмом ( обозначает целую часть числа ):

Дано: 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 , . . . ,m n) (осно вание счисления) и запись K = (k 0 , k 1 , . . . , k n) обозначает число k = k 0 +m 1 (k 1 +m 2 (k 2 +· · ·+m n ·k n) . . .)) . Написать программу, которая по данным (день недели, часы, минуты, секунды) определяет, сколько секунд прошло с начала недели (понедельник, 0, 0, 0) = 0 , и выполняет обратное преобразование.

В различных разделах математики, а также в применении математики в технике, часто встречается ситуация, когда алгебраические операции производятся не над числами, а над объектами иной природы. Например сложение матриц, умножение матриц, сложение векторов, операции над многочленами, операции над линейными преобразованиями и т.д.

Определение 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. Отметим, что множество нечетных чисел не является кольцом т.к. сумма двух нечетных чисел является четным числом.

Кольцо, в котором введено отношение «быть больше нуля» (обозначается а > 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=> ac < bc;

Те же свойства имеют место и для других знаков <, , .

Докажем, например, свойство (в). По определению, из условия 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 => aa > 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 > 0b = 0 => ab > 0.

Теорема 2. Кольцо целых чисел является расположенным кольцом (упорядоченной системой).

Доказательство: Воспользуемся определением 2 кольца целых чисел (см. 2.1). Согласно данному определению любое целое число это либо натуральное число (число n задаётся как [], либо противоположное натуральному (– n соответствует классу [<1, n / >] , либо 0 (класс [<1, 1>]). Введём определение «быть больше нуля» для целых чисел по правилу:

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| = |a|  |b|.

Доказательство: 1) Отметим, что из определения очевидно, что |a| есть величина всегда неотрицательная (в первом случае |a| = a ≥ 0, во втором |a| = –а, но а < 0, откуда –а > 0). Также справедливы неравенства |a| ≥ a, |a| ≥ –a (модуль равен соответствующему выражению, если оно неотрицательно, и больше его, если оно отрицательно). Аналогичные неравенства справедливы и для b: |b| ≥ b, |b| ≥ –b. Складывая соответствующие неравенства и применяя свойство (б) расположенных колец, получаем

|a| + |b| ≥ a + b |a| + |b| ≥ – a – b.

Согласно определению модуля

|a + b| =
,

но оба выражения в правой части равенства, как показано выше, не превосходят |a| + |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 = 51 = 15 = –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? Каково максимально возможное значение данного частного?

Определение:

Суммой и произведением целых р-адических чисел определяемых последовательностями и, называются целые р-адические числа, определяемые соответственно последовательностями и.

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

Очевидно,что при данном нам определении действий над целыми - адическими числами они образуют коммуникативное кольцо, содержащее кольцо целых рациональных чисел в качестве подкольца.

Делимость целых - адических чисел определяется так же,как и в любом другом кольце: , если существует такое целое - адическое число, что

Для исследования свойств деления важно знать, каковы те целые - адические числа,для которых существуют обратные целые - адические числа. Такие числа называют делителями единицы или единицами. Мы их будем называть - адическими единицами.

Теорема 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-ичной дроби с конечным числом цифр после запятой и, возможно, бесконечным числом ненулевых цифр до запятой. Деление таких чисел можно также производить аналогично «школьному» правилу, но начиная с младших, а не старших разрядов числа.