7. Целые числа. Делимость

Определение. Пусть a и bцелые числа. Говорят, что число a делится на число b, если a можно представить в виде a=nb, где n – целое число.
Обозначение. a\vdots b.

Теорема. Пусть a,b,c,m – целые числа. Тогда

1. a\vdots m,b\vdots m\Longrightarrow (a+b)\vdots m,(a-b)\vdots m;

2. a\vdots m\Longrightarrow ab\vdots m;

3. a\vdots b,b\vdots c\Longrightarrow a\vdots c.

Доказательство.

1. Так как a\vdots m, то a=km,k – целое;
так как b\vdots m, то b=lm,l – целое.

Следовательно,
a+b=(k+l)m, где  k+l – целое число;
a-b=(k-l)m, где k-l – целое число.

Значит, (a+b)\vdots m,(a-b)\vdots m.

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

Определение. Говорят, что b — делитель a, если a\vdots b.

Определение. Число d называется общим делителем чисел a и b, если оно является как делителем a, так и делителем b.

Определение. Самый большой из всех общих делителей a и b называется их наибольшим общим делителем.

Обозначение. НОД(a,b), GCD(a,b), gcd(a,b) или просто (a,b).

Теорема о делении с остатком. Пусть a – целое число, b – натуральное. Тогда существует единственная пара чисел q,r, удовлетворяющих условиям

1. q,r – целые числа;

2. a=bq+r;

3. 0\le r < b.

Доказательство.

Существование.

Пусть \displaystyle q=\left[{a\over b}\right] — целая часть числа \displaystyle{a\over b}, т.е. наибольшее целое число, не превосходящее \displaystyle{a\over b}. Тогда

    \[\begin{array}{l} \displaystyle q\le{a\over b}<q+1,\\[2mm] bq\le a<bq+b,\\[1mm] 0\le a-bq<b. \end{array}\]

Пусть r=a-bq. Найденные q и r удовлетворяют всем условиям теоремы.

Единственность.

Предположим, что нашлась другая пара чисел q',r', удовлетворяющая тем же условиям. Тогда

    \[\begin{array}{l} bq+r=bq'+r'\\ bq-bq'=r'-r\\ b(q-q')=r'-r. \end{array}\]

Если q\ne q', то левая часть этого равенства по модулю не меньше b. В то же время правая часть по модулю меньше b, так как 0\le r.  Получили противоречие. Значит, q=q'. Следовательно, r-r'=0 \Longrightarrow r=r'.

Значит, q,r — та же пара чисел, что и q',r'.

Число r называется остатком от деления a на b, q — неполным частным.

Алгоритм Евклида

Древнегреческая геометрия достигла своего апогея в III в. до н.э. в работах знаменитого математика Евклида, написавшего 13 книг, объединенных общим названием “Начала”. В трудах Евклида логическая сторона геометрии была доведена до очень высокого уровня.


Однажды на вопрос царя Птолемея I Сотера (305–283 до н.э.), — не существует ли более короткого пути для изучения геометрии, чем штудирование “Начал”, — Евклид сказал в ответ: “В геометрии нет царского пути!” В Египте же того времени были две системы дорог: одна для царя и его курьеров, другая для всего населения.


В другой раз один из учеников, выучив первое предложение “Начал”, спросил Евклида: “А что я могу заработать, выучив все это?” Евклид позвал своего раба и сказал: “Дай ему три обола, так как бедняжка хочет заработать деньги своим учением (Примечание. Обол — мелкая серебряная монета в Древней Греции.)”.


Из ответов Евклида видно, что величайший геометр требовал должного уважения и даже благоговения к математике.

Лемма. Пусть a=bq+r, где a,b,q,r – целые числа. Тогда любой общий делитель чисел a и b является общим делителем чисел b и r. Обратно: любой общий делитель чисел b и r является общим делителем чисел a и b.

    \[\begin{array}{ll} a=bq_1+r_1,&0\le r_1< b,\\ b=r_1q_2+r_2,&0\le r_2<r_1,\\ r_1=r_2q_3+r_3,&0\le r_3<r_2\\ \ldots&\\ r_{n-2}=r_{n-1}q_n+r_n,&0\le r_n<r_{n-1},\\ r_{n-1}=r_nq_{n+1}& \end{array}\]

Пусть a,b — натуральные числа. Разделим a на b с остатком. Если r_1\ne0, то разделим b на r_1 с остатком. Если r_2\ne0, то разделим r_1 на r_2 с остатком и т.д. Этот процесс оборвется, так как каждый следующий остаток меньше предыдущего и неотрицателен. Так что некоторый остаток r_{n-1} разделится на остаток r_n без остатка.

Из леммы следует, что
НОД(a,b)= НОД(b,r_1)=НОД(r_1,r_2)=\ldots= НОД(r_{n-1},r_n)=r_n.

Пример. Найти НОД(7007,4459).

\begin{tabular}{l|l} 7007&4459\\ \cline{2--2} 4459&1\\ \cline{1--1} \end{tabular}

\begin{tabular}{l|l} 4459&2548\\ \cline{2--2} 2548&1\\ \cline{1--1} \end{tabular}

\mbox{}\hskip8.25cm\begin{tabular}{l|l} 2548&1911\\ \cline{2--2} 1911&1\\ \cline{1--1} \end{tabular}

\mbox{}\hskip7.3cm\begin{tabular}{r|l} 1911&637\\ \cline{2--2} 1911&3\\ \cline{1--1} 0& \end{tabular}

Ответ. НОД(7007,4459)=637.

Задача.Найти НОД(6188,4709).

Блок-схема алгоритма Евклида

Задачи.

1. Доказать теорему.

2. Найти НОД(81719,52003,33649,30107).

3. Найти НОД(2^{40}-1,2^{30}-1).

4. Доказать, что для всех натуральных n несократима дробь

    \[{6n+5\over 9n+7}.\]

Комментариев: 9

  1. 1 И.М. Виноградов ``Основы теории чисел'' | Математика, которая мне нравится:

    [...] не менее, знать начала теории чисел довольно полезно, в особенности тем, кто собирается [...]

  2. 2 Еще одна книга о математике | Математика, которая мне нравится:

    [...] Однако прочитала книгу Саймона Сингха о шифрах, и захотелось о ней рассказать. Как и любая книга или статья, написанная Сингхом, она очень познавательна и читается легко. В “Книге шифров’’ приводится много интереснейших фактов из истории. Ведь были и войны, в которых выигрывал тот, кто знал больше, были секреты, которые нужно было тщательно скрывать от посторонних глаз, была зашифрованная информация, от корой зависели жизни людей (в частности, шотландской королевы Марии Стюарт). А уж в наше время значение информации трудно переоценить. И не последнюю роль в развитии криптографии всегда играла математика, в частности, теория чисел. [...]

  3. 3 Чет и нечет | Математика, которая мне нравится:

    [...] четное целое число представимо в виде , где — целое число. [...]

  4. 4 Числа-вампиры | Математика, которая мне нравится:

    [...] количеством цифр. Разделите это число на два дочерних числа равной длины (с равными количествами цифр), в которых [...]

  5. 5 Грант на исследования в теории чисел может привести к достижениям в сфере беспроводной связи | Математика, которая мне нравится:

    [...] приближения — это раздел теории чисел, который восходит к древним грекам и китайцам, [...]

  6. 6 Лейб:

    В теореме о делении с остатком в третьем условии справа должно быть строгое неравенство:

    r < b.

    Иначе нарушается единственность.

    [Ответить]

  7. 7 Елизавета Александровна Калинина:

    Спасибо! Конечно же, Вы правы. Исправила.

    [Ответить]

  8. 8 Вася Пупкин:

    “:=” — этот символ обозначает присвоение?

    [Ответить]

Оставьте свой отзыв

Добавить изображение