Главная > Математика > Дискретная математика. Алгоритмы и программы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Глава 8. Элементы теории чисел

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

8.1. Наибольший общий делитель

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

Свойства наибольшего общего делителя

1. Если

2. Если тогда общие делители чисел суть те же, что и общие делители чисел в частности,

3. Для определения наибольшего общего делителя применяется алгоритм Евклида. Он состоит в нижеследующем. Пусть положительные целые числа и Составим ряд равенств:

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

4. Из формул (8.1.1) алгоритма Евклида следует, что

Наибольший общий делитель равен последнему не равному нулю остатку алгоритма Евклида.

5. Из формул (8.1.1) алгоритма Евклида следует также, что существуют целые и что . В частности, если то

Пример. Найдем

Последний остаток есть , значит,

6. Пусть любое положительное целое, тогда

7. Если то

8. Если делится на то с делится на

<< Предыдущий параграф Следующий параграф >>
Оглавление