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

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

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

1. avdots m,bvdots mLongrightarrow (a+b)vdots m,(a-b)vdots m;

2. avdots mLongrightarrow abvdots m;

3. avdots b,bvdots cLongrightarrow avdots c.

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

1. Так как avdots m, то a=km,k – целое;
так как bvdots 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, если avdots 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. 0le r < b.

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

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

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

    [begin{array}{l} displaystyle qle{aover b}<q+1,\[2mm] bqle a<bq+b,\[1mm] 0le 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}]

Если qne q', то левая часть этого равенства по модулю не меньше b. В то же время правая часть по модулю меньше b, так как 0le r.  Получили противоречие. Значит, q=q'. Следовательно, r-r'=0Longrightarrowr=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,&0le r_1< b,\ b=r_1q_2+r_2,&0le r_2<r_1,\ r_1=r_2q_3+r_3,&0le r_3<r_2\ ldots&\ r_{n-2}=r_{n-1}q_n+r_n,&0le r_n<r_{n-1},\ r_{n-1}=r_nq_{n+1}& end{array}]

Пусть a,b — натуральные числа. Разделим a на b с остатком. Если r_1ne0, то разделим b на r_1 с остатком. Если r_2ne0, то разделим 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.25cmbegin{tabular}{l|l} 2548&1911\ cline{2--2} 1911&1\ cline{1--1} end{tabular}

mbox{}hskip7.3cmbegin{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+5over 9n+7}.]

Ссылка на основную публикацию