Приложение теории сравнений при проверке результатов арифметических действий

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

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

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

Изучение свойств таких чисел составляет содержание одного из важнейших разделов современной теории чисел, называемого алгебраической теорией чисел. В теорию чисел включают также вопросы, связанные с приближением действительных чисел рациональными дробями. Такие приближения называют обычно диофантовыми приближениями, по имени великого греческого математика Диофанта.

Для современной теории чисел характерно применение весьма разнообразных методов исследований; так, например, многие проблемы теории чисел могут быть, естественно, сформулированы в геометрической форме, и к решению такого рода задач применяют геометрические соображения (геометрическая теория чисел). В современной теории чисел широко пользуются методами математического анализа; в частности, при изучении вопросов, связанных с распределением простых чисел, особенно часто приходится применять теорию функций комплексного переменного. Теоретико-числовые исследования, в которых существенно используются методы математического анализа, являются содержанием весьма значительного раздела теории чисел, получившего наименование «Аналитическая теория чисел».

Развитие теории чисел тесно и непосредственно связано с развитием целого ряда разделов математики.

Теория чисел не только широко использует методы, разработанные в смежных математических дисциплинах, но и сама влияет на формирование этих дисциплин. Так, например, начало глубоких исследований в теории алгебраических чисел было связано с так называемой проблемой Ферма о возможности существования целых положительных решений неопределенного уравнения при п>2; дальнейшее развитие этой теории оказало решающее влияние на современную алгебру, а возникшие в теории чисел понятия «кольца», «идеала» являются одними из основных понятий всей математики нашего времени. Ряд вопросов теории чисел находит себе применение на практике, например в теории телефонных сетей (кабелей), в кристаллографии, при решении некоторых задач теории приближенных вычислений. Современную теорию чисел можно в основном разбить на следующие разделы:

Элементарная теория чисел (теория сравнений, теория форм, неопределенные уравнения). К этому разделу относят вопросы теории чисел, являющиеся непосредственным развитием теории делимости, и вопросы о представимости чисел в определенной форме. Более общей является задача решения систем неопределенных уравнений, т. е. уравнений, в которых значения неизвестных должны быть обязательно целыми числами. Неопределенные уравнения называют также диофантовыми уравнениями, так как Диофант был первым математиком, систематически рассматривавшим такие уравнения. Мы условно называем этот раздел «Элементарная теория чисел», поскольку здесь часто применяются обычные арифметические и алгебраические методы исследования.

Алгебраическая теория чисел. К этому разделу относят вопросы, связанные с изучением различных классов алгебраических чисел,

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

Аналитическая теория чисел. К этому разделу относят вопросы теории чисел, для изучения которых приходится применять методы математического анализа.

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

Целью данной курсовой работы является изучение темы «Приложение теории сравнений при проверке результатов арифметических действий», выработка навыков проверки результатов выполнения арифметических действий, используя сравнения.

1. СРАВНЕНИЯ

1.1 Определение сравнения

Теория чисел имеет свою алгебру, известную, как теория сравнений. Обычная алгебра первоначально развивалась как стенография для операций арифметики. Аналогично, сравнения представляют собой символический язык для делимости, основного понятия теории чисел. Понятие сравнения впервые ввел Гаусс.

Прежде чем мы обратимся к понятию сравнения, сделаем одно замечание о числах, которые будем изучать в этой главе. Мы начали эту книгу, заявив, что будем рассматривать целые положительные числа 1, 2, 3…, и в предыдущих главах мы ограничивались только этими числами и дополнительным числом 0. Но теперь мы достигли стадии, на которой целесообразно расширить наши границы, рассматривая все целые числа:

0, ±1, ±2, ±3….

Это никоим образом не повлияет на наши предыдущие понятия; далее, когда мы будем говорить о простых числах, делителях, наибольших общих делителях и тому подобном, мы будем считать их целыми положительными числами.

Теперь вернемся к языку сравнений. Если а и b -- два целых числа и их разность а - b делится на число m , мы выражаем это записью

ab(mod m ) (1.1.1)

которая читается так:

а сравнимо с b по модулю m.

Делитель m мы предполагаем положительным; он называется модулем сравнения.

Наше высказывание (1.1.1) означает, что

a - b = mk ,

где k -- целое число. (1.1.2)

Примеры.

1) 238 (mod 5), так как 23 - 8 = 15 = 53;

2) 4711 (mod 9), так как 47-11 = 36 = 94;

3) -115 (mod 8), так как - 11- 5 = -16 = 8(-2);

4) 810 (mod 27), так как 81 - 0 = 81 = 273.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать

a0 (mod m ),

так как это означает, что

а - 0 = а = mk ,

где k -- некоторое целое число. Например, вместо того, чтобы сказать, что а - четное число, мы можем записать

a 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению

а 1 (mod 2).

Эта несколько странная терминология является довольно обычной для математических работ.



1.2 Свойства сравнений

Способ, которым мы записываем сравнения, напоминает нам уравнения, и в действительности, сравнения и алгебраические уравнения имеют много общих свойств. Простейшими из них являются три следующих свойства:

a a (mod m ); (1.2.1)

это является следствием того, что

а - а = m - 0,

a b (mod m ) означает, что и ba (mod m ). (1.2.2)

Это следует из того, что b - a = - (а - b ) = m (-k ).

Из

а b (mod m ) и b c (mod m ) (1.2.3)

следует, что аc(mod m), потому что первые два утверждения означают, что

а - b = mk, b - с = ml ,

поэтому

а - с = (а - b ) + (b - с ) = m (k + l ).

Пример . Из того, что 1335 (mod 11) и 35- 9 (mod 11) следует, что 13 - 9 (mod 11).

Мы говорили, что сравнения похожи по своему свойству на равенства. В действительности, мы можем рассматривать равенства как тип сравнения, а именно, сравнения по модулю 0. По определению,

а b (mod 0)

означает, что

a - b = 0 k = 0

или

а = b.

Вы почти никогда не встретите такую форму сравнения для записи уравнений в математической литературе. Но существует другое сравнение, очевидно, довольно тривиальное, которое иногда используется. Когда модуль есть число m = 1, мы имеем, что

a b (mod 1) (1.2.4)

для любой пары целых чисел а и b , так как это означает, что

a - b = 1 k = k (1.2.5)

есть целое число. Но предположим теперь на мгновение, что а и b - произвольные вещественные числа, необязательно целые. Тогда тот факт, что они сравнимы по модулю 1, означает, что их разность есть целое число, т. е. эти два числа имеют одинаковую дробную часть.

Вернемся к свойствам обычных сравнений целых чисел; с этого момента мы будем всегда считать, что модуль является целым числом т.

Мы можем разделить числовую ось, начиная от начала координат в обоих направлениях на отрезки длиной m , как на рис. 1. Тогда каждое целое число а положительное или отрицательное, попадает на один из этих отрезков или на одну из точек деления; таким образом, мы можем записать

a = km + r , (1.2.6)

где k -- некоторое целое число, а r -- одно из чисел

0, 1, 2…, m - 1. (1.2.7)

Рис. 1.

Это является незначительным обобщением деления положительных чисел. Здесь мы также называем число r в формуле (1.2.6) остатком при делении числа а на число m или остатком по модулю m.

Примеры.

1) а = 11, m = 7, 11 = 7 1 + 4,

2) а = -11, m = 7, -11 = 7 (-2) + 3.

Деление (1.2.6) может быть также записано как сравнение

а r (mod m ). (1.2.8)



Таким образом, каждое число сравнимо со своим остатком по модулю m . В приведенных выше примерах мы имеем

114 (mod 7), - 113 (mod 7).

Никакие два остатка в (1.2.7) не сравнимы по (mod m), так как разность между любыми двумя из них меньше, чем m . Поэтому два числа, которые не сравнимы по (mod m), должны иметь разные остатки. Итак, мы делаем вывод: сравнение а b(mod m) выполняется тогда и только тогда, когда числа а и b имеют одинаковые остатки при делении на число m.

Существует другой способ представления этого сравнения. Предположим на мгновение, что а и b - целые положительные числа. Когда число а записано при основании m, а = (аn …, а1, а0)m ,

то последняя цифра а0 является остатком числа а при делении его на число m. Если мы используем этот факт, чтобы иначе выразить нашу интерпретацию сравнения, то можно сказать:

сравнение а b (mod m) выполняется для целых (положительных) чисел а и b тогда и только тогда, когда числа а и b имеют одинаковые последние цифры в записи при основании m.

Например,

37 87 (mod 10),

так как эти два числа имеют одну и ту же последнюю цифру в десятичной системе чисел.

1.3 Алгебра сравнений

Из алгебры мы помним, что уравнения можно складывать, вычитать, умножать. Точно такие же правила справедливы для сравнений. Предположим, что мы имеем сравнения



a b (mod m), с d (mod m). (1.3.1)

По определению, это означает, что

a = b + mk, c = d + ml , (1.3.2)

где k и l - целые числа. Сложим уравнения (1.3.2).

В результате получаем

а + с = b + d + m (k + l),

что можем записать как

теория число сравнение арифметика

а + с b + d (mod m); (1.3.3)

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

a - c b - d (mod m). (1.3.4)

Пример.

11 -5 (mod 8) и 7 - 9 (mod 8). (1.3.5)

Складывая их, получаем

18 - 14 (mod 8),

а вычитая,



4 4 (mod 8).

Оба эти сравнения справедливы.

Можно также перемножить два сравнения. Из (1.3.1) и (1.3.2) следует, что ac = bd + m (kd + bl + mkl),

таким образом,

ас bd (mod m). (1.3.6)

Пример. Когда два сравнения из (1.3.5) перемножены, получается

77 = 45 (mod 8).

Сравнение a b (mod m) может быть умножено на любое целое число с , при этом получаем

ас bc (mod m). (1.3.7)

Это можно рассматривать как частный случай умножения сравнений (1.3.6) при с = d. Его можно также рассматривать как прямое следствие из определения сравнения.

Пример. Когда первое сравнение из (1.3.5) умножается на 3, получаем, что 33 = -15 (mod 8).

Возникает естественный вопрос: в каком случае можно в сравнении (1.3.7) сократить общий множитель с и получить при этом верное сравнение

a b (mod m)?

Именно здесь сравнения отличаются от уравнений. Например, верно, что 22 -2 (mod 8),

но сокращение на множитель 2 дало бы сравнение

11 -1 (mod 8),

которое неверно.

В одном важном случае сокращение допустимо:

если ас bc (mod m), то a b (mod m) при условии, что числа m и с взаимно просты.

Доказательство. Первое сравнение означает, что

ас - bc = (а - b ) с = mk .

Если D (m, с ) = 1, то отсюда следует, что а - b делится на m.

Пример. В сравнении

4 48 (mod 11)

мы можем сократить на множитель 4, так как D (11, 4) = 1. Это дает

2 12 (mod 11).

3 

2. АРИФМЕТИЧЕСКИЕ ПРИЛОЖЕНИЯ ТЕОРИИ СРАВНЕНИЙ

2.1 Арифметические действия

К арифметическим действиям относятся:

- Сложение является начальным понятием, для которого невозможно дать строгое формальное определение. Тем не менее, чтобы придать этому действию некоторое разумное представление, мы скажем, что сложение - это операция нахождения суммы двух или нескольких чисел, где под суммой понимается общее количество единиц, содержащихся в рассматриваемых числах вместе. Эти числа называются слагаемыми. Например, 11 + 6 = 17. Здесь 11 и 6 - слагаемые, 17 - сумма. Если слагаемые поменять местами, то сумма не изменится: 11 + 6 = 17 и 6 + 11 = 17.

- Вычитание является действием, обратным к сложению, так как это операция нахождения одного из слагаемых по сумме и другому слагаемому. Вычесть из одного числа (уменьшаемого) другое (вычитаемое) - значит найти такое третье число (разность), которое при сложении с вычитаемым дает уменьшаемое: 17 - 6 = 11. Здесь 17 - уменьшаемое, 6 - вычитаемое, 11 - разность.

- Умножение. Умножить одно число n (множимое) на другое целое число m (множитель) - значит повторить множимое n в качестве слагаемого m раз. Результат умножения называется произведением. Запись операции умножения: n x m или n • m . Например, 12 x 4 = 12 + 12 + 12 + 12 = 48. Таким образом, 12 x 4 = 48 или 12 • 4 = 48. Здесь 12 - множимое, 4 - множитель, 48 - произведение. Если множимое n и множитель m поменять местами, то произведение не изменится. Например, 12 · 4 = 12 + 12 + 12 + 12 = 48 и соответственно, 4 · 12 = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 48. Поэтому множимое и множитель часто называются сомножителями.

- Деление является действием, обратным к умножению, так как это операция нахождения одного из сомножителей по произведению и другому сомножителю: Разделить одно число (делимое) на другое (делитель) - значит найти такое третье число (частное), которое при умножении на делитель даёт делимое: 48 : 4 = 12. Здесь 48 - делимое, 4 - делитель, 12 - частное. Частное от деления одного целого числа на другое целое число может и не быть целым числом. Тогда это частное представляется в виде дроби. Если частное - целое число, то говорят, что эти числа делятся нацело. В противном случае мы выполняем деление с остатком. Пример: 23 не делится на 4, в этом случае мы можем записать: 23 = 5 · 4 + 3. Здесь 3 - остаток.

- Возведение в степень. Возвести число (основание степени) в целую степень (показатель степени) - значит повторить его сомножителем столько раз, каков показатель степени. Результат называется степенью. Запись возведения в степень:

3 5 = 3 · 3 · 3 · 3 · 3 = 243

Здесь 3 - основание степени, 5 - показатель степени, 243 - степень.

Вторая степень любого числа называется квадратом, третья - кубом. Первой степенью любого числа является само это число.

- Извлечение корня является действием, обратным к возведению в степень, так как это операция нахождения основания степени по степени и её показателю. Извлечь корень n-ой степени (n - показатель корня) из числа a (подкоренное число) - значит найти третье число, n-ая степень которого равна а . Результат называется корнем. Например:

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

2.2 Основные законы арифметики

Про свойства арифметических операций сформулированы пять законов, которые считаются основными законами арифметики:

- Коммутативность: переместительный закон гласит, что от перемены мест слагаемых сумма не меняется. Аналогичный закон известен и для умножения, но он, конечно, говорит о множителях и произведении. Эти законы можно выразить в алгебраической форме с помощью буквенных обозначений:

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

- Дистрибутивность: распределительный закон гласит: чтобы умножить сумму на число, можно умножить каждое слагаемое на это число и потом сложить полученные произведения. В алгебраической форме:

2.3 Проверка результатов арифметических действий

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

Теория сравнений дает следующий способ проверки арифметических действий.

Выбираем некоторый модуль т и заменяем большие числа а, b, с, ..., над которыми нам надо производить действия (сложение, вычитание, умножение, возведение в степень), небольшими числами а', b', с', ..., сравнимыми с ними по модулю т. Произведя действия над а, b, с мы точно такие же действия производим над а', b', с', ... Если действия произведены правильно, то результаты этих действий над а, b, с, ... и над а', b', с', ... должны быть сравнимы по модулю т.

Если aa'(mod m), bb'(mod m),…,

то a+b+… a'+ b'+…(mod m), ab… a' b'…(mod m).

Для проверки соотношения представляем его в виде a=bc. Применение этого способа проверки, конечно, имеет смысл только тогда, когда нахождение таких чисел а', b', c',... может быть осуществлено легко и быстро. Для этого обычно в качестве модуля т выбирают т=9 или m=11. Каждое число, записанное в десятичной системе счисления, сравнимо с суммой его цифр по модулю 9, так что мы можем сформулировать следующий способ “проверки с помощью девятки”.

Для каждого числа вычисляется остаток от деления на 9 суммы цифр. Производя действия над числами, производят такие же действия над этими остатками. Результат рассматриваемых действий над этими остатками должен отличаться от суммы цифр искомого результата на число, кратное девяти.

Конечно, если ошибка такова, что разность между найденной и истинной величинами кратна 9, то она при этом способе проверки не будет замечена.

По модулю m = 11 каждое число, записанное в десятичной системе счисления, будет сравнимо с суммой цифр, взятых справа налево попеременно со знаками „плюс” и „минус”; поэтому мы можем сформулировать следующий способ „проверки с помощью одиннадцати”. Для каждого числа вычисляется остаток от деления на 11 суммы цифр, взятых попеременно справа налево со знаками „плюс” и „минус”. Результат рассматриваемых действий над этими остатками должен отличаться от суммы взятых попеременно со знаками „плюс” и „минус” справа налево цифр искомого результата на число, кратное 11. Если ошибка будет кратна 11, она не будет замечена при этом способе.

При сложных вычислениях имеет смысл проводить две проверки: одну с помощью модуля 9, а другую с помощью модуля 11. В этом случае ошибка не будет замечена только, если она кратна 99, что, конечно, бывает очень редко.

Примеры. Проверим правильность выполнения действий (с помощью 9 и 11):

1)

2)

3)

4)

5)

6)

7)

8)

9)

1)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает правильность получения результата.

2)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает правильность получения результата.

3)

Сравнение не подтверждает правильности выполнения действий.

Проверка одиннадцатью подтверждает неправильность получения результата.

4)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает правильность получения результата.

5)

Сравнение не подтверждает правильности выполнения действий.

Проверка одиннадцатью подтверждает неправильность получения результата.

6)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает правильность получения результата.

7)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает неправильность получения результата.

8)

Сравнение не подтверждает правильности выполнения действий.

Проверка одиннадцатью подтверждает неправильность получения результата.

9)

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

Проверка одиннадцатью подтверждает неправильность получения результата.



ЗАКЛЮЧЕНИЕ

Археология и история учат нас, что человек рано начал считать. Сначала он научился складывать числа, потом, много позже, умножать и вычитать их. Деление чисел было необходимым для распределения на равные части кучи яблок или улова рыбы.

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

В результате выполнения курсовой работы по дисциплине «Теория сравнений» была изучена тема «Приложение теории сравнения при проверке результатов арифметических действий», были закреплены знания и выработаны навыки проверки результатов выполнения арифметических действий, используя сравнения.



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Оре О. Приглашение в теорию чисел (пер. с англ.). - Москва: УРСС, 2003.

2. Бухштаб А.А. Теория чисел. - M.: Просвещение, 1966.

3. Михелович Т.Л. Теория чисел. - М.: Наука, 1983.

4. Банникова Т.М., Баранова Н.А. Основы теории чисел (учебно- методическое пособие). - Ижевск, 2009.

5. Вейль Г. Основы теории чисел. -М., 2004.

6. Ляжен Е.С., Евсеев А.Е. Алгебра и теория чисел. -М.: Высшая школа, 1978.

7. Виноградов И.М. Основы теории чисел. - М.: Наука, 1976.

8. Куликов Л.Я. Алгебра и теория чисел. - М.: Высшая школа, 1979.

9. Бейкер, А. Введение в теорию чисел / А. Бейкер. - Минск: Вышэйшая школа, 1995.

10. Айерленд, К. Классическое введение в современную теорию чисел / К. Айерленд. -М.: Мир, 1987.

Размещено на Allbest.ru