Глава 2. Основы теории чисел

Делимость чисел

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

    Определение 1.1. Пусть  и  – целые числа. Говорят, что число   делится на число , если найдется такое целое число , что . При этом число  называют делимым, число  – делителем, а число – частным.

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

    Примеры. 1) 65 13, так как ;

                        2) 0 3, так как ;

                        3) 5, так как .

 

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

                        .

Если , то . Значит, в случае, когда делитель отличен от нуля, частное единственно.

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

В дальнейшем, говоря о делении, всегда будем предполагать, что делитель отличен от 0.

 

Свойства делимости

 

1. Если , то (– ); (– ) ; (– ) (– ).

Доказательство. Пусть , это значит, что существует такое целое число , что . Тогда , причем число  также является целым. Следовательно, по определению делимости (– ). Остальные утверждения доказываются аналогично.

2. Если  и , то .

Доказательство. , где ; , где . Тогда . Число  – целое, значит, .

Следствие. Из свойств 1 и 2 непосредственно следует, что если  и , то .

3. Если  и , то .

Доказательство. , где . Умножим обе части последнего равенства на , получим . Число – целое, значит, .

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

Доказательство. Предположим, что данное утверждение неверно: . Это значит, что , где . Тогда . Но , где . Следовательно, . Поскольку , получим, что , что противоречит условию. Полученное противоречие доказывает, что сделанное нами предположение неверно.

5. Если  и , то .

Доказательство. , где , причем . Тогда . Но , значит .

Следствие 1. Если , то либо , либо .

Доказательство. Если , то по свойству 5 справедливо неравенство . При этом  – целое число, отличное от 0. Следовательно, , а это и значит, что либо , либо .

Следствие 2. Если  и , то либо , либо .

Доказательство. Если  и , то по свойству 5 справедливы неравенства  и . Одновременное выполнение этих неравенств может быть только в случае, когда , что и означает, что либо , либо .

Отметим, что отношение делимости является бинарным отношением на множестве . Рассмотрим его свойства делимости как бинарного отношения.

1. Рефлексивность. Очевидно, что . Значит, отношение делимости рефлексивно.

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

 Заметим, что если рассмотреть отношение делимости на множестве натуральных чисел N, то окажется, что это отношение обладает свойством антисимметричности. Действительно, в этом случае следствие 2 к свойству 5 примет вид: если  и , то  (поскольку на множестве N равенство невыполнимо).

3. Транзитивность отношения делимости означает, что если  и , то . Докажем, что отношение делимости транзитивно. Действительно,

, где ;

, где .

Следовательно, , при этом, очевидно, , а это и означает, что .

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

 

Деление с остатком

Определение 2.1. Пусть  и  – целые числа. Разделить число   на число   с остатком, значит найти такие целые числа  и , что выполняются условия:

1)

2) .

При этом  называется неполным частным, а – остатком от деления   на .

    Примеры. 1) Разделить 5 на 3 с остатком. В соответствии с определением представим число 5 в виде: 5=3 1+2. Здесь . Условие 2 из определения, очевидно, выполняется.

    2) Разделить (–5) на 3 с остатком: (–5)=3 (–2)+1. Здесь ; .

    3) Разделить 5 на (–3) с остатком: 5=(–3) (–1)+2. Здесь ; .

    4) Разделить (–5) на (–3) с остатком: (–5)=(–3) 2+1. Здесь ; .

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

    Доказательство. Рассмотрим случай, когда ,

1) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут отрицательными. Пусть последним из неотрицательных членов будет число . Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Если бы это неравенство не выполнялось, то . Последние неравенство противоречит тому, что является последним неотрицательным числом в последовательности. Таким образом мы доказали, что число  делится на с остатком.

2) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут положительными. Пусть – первое неотрицательное число в этой последовательности. Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Предположим, что неравенство не выполняется, тогда . Но – первое неотрицательное число в последовательности. Полученное противоречие доказывает, что сделанное нами предположение неверно. Положим , тогда .

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

 Случай, когда , рассматривается аналогично.

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

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

 

 

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

Определение 3.1. Рассмотрим  целых чисел  и целое число , причем . Число  называется общим делителем чисел , если каждое из этих чисел делится на : , ,…, .

Определение 3.2. Рассмотрим  целых чисел  и целое число . Число  называется наибольшим общим делителем чисел (НОД) чисел , если

1) является общим делителем чисел ,

2) делится на любой из общих делителей чисел .

НОД чисел  обозначают .

    Определение 3.3. Если , то числа  называются взаимно простыми.

        

                  Свойства НОД

 

    Теорема 3.1. НОД чисел  определен однозначно с точностью до знака, т. е., если числа  и  – наибольшие общие делители чисел , то либо , либо .

    Доказательство. Из определения НОД следует, что  и , поскольку оба этих числа являются общими делителями чисел . Тогда по следствию 2 к свойству 5 делимости чисел либо , либо .

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

    Теорема 3.2. Пусть (т. е. число  является наибольшим общим делителем чисел ). Тогда число является наибольшим по величине общим делителем этих чисел.

Доказательство. Пусть  – общий делитель чисел . Тогда из определения НОД следует, что . По свойству 5 делимости чисел . Мы условились считать, что НОД чисел положителен, следовательно, . Учитывая, что , получим требуемое утверждение.

Теорема 3.3. Пусть – целые числа. Для того, чтобы число  было НОД чисел  и  необходимо и достаточно, чтобы существовали такие взаимно простые числа  и , что .

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

Достаточность. Пусть , где . Докажем, что . Из условия утверждения следует, что  и , следовательно,  – делитель чисел  и .

Предположим, что – не является наибольшим общим делителем чисел  и . Пусть . Тогда . Это значит, что , где  – целое число, причем . Из определения НОД получим, что . Тогда . Из единственности частного следует, что . Значит, числа  и  не являются взаимно простыми, что противоречит сделанному нами предположению. Полученное противоречие доказывает справедливость утверждения.