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.

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

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

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

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

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

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

Предположим, что нашлась другая пара чисел q’,r’, удовлетворяющая тем же условиям. Тогда
\begin{array}{l}<br />
bq+r=bq’+r’\\<br />
bq-bq’=r’-r\\<br />
b(q-q’)=r’-r.<br />
\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}<br />
a=bq_1+r_1,&0\le r_1< b,\\</p>
<p>b=r_1q_2+r_2,&0\le r_2<r_1,\\</p>
<p>r_1=r_2q_3+r_3,&0\le r_3<r_2\\</p>
<p>\ldots&\\<br />
r_{n-2}=r_{n-1}q_n+r_n,&0\le r_n<r_{n-1},\\</p>
<p>r_{n-1}=r_nq_{n+1}&<br />
\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)=\dots= НОД(r_{n-1},r_n)=r_n.

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

\begin{tabular}{l|l}<br />
7007&4459\\<br />
\cline{2–2}<br />
4459&1\\<br />
\cline{1–1}<br />
\end{tabular}

\begin{tabular}{l|l}<br />
4459&2548\\<br />
\cline{2–2}<br />
2548&1\\<br />
\cline{1–1}<br />
\end{tabular}

\mbox{}\hskip8.25cm\begin{tabular}{l|l}<br />
2548&1911\\<br />
\cline{2–2}<br />
1911&1\\<br />
\cline{1–1}<br />
\end{tabular}

\mbox{}\hskip7.3cm\begin{tabular}{r|l}<br />
1911&637\\<br />
\cline{2–2}<br />
1911&3\\<br />
\cline{1–1}<br />
0&<br />
\end{tabular}

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

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

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

Задачи.

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

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

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

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

\displaystyle{6n+5\over 9n+7}.

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

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

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

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

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

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

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

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

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

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

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

  6. 6 Лейб:

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

    r < b.

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

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