Теорема о делении с остатком

Теорема. Для любого целого числа а и любого целого b ≠ 0 существуют и единственные целые числа q и r, такие, что а = bq + r, где 0 Число q называют неполным частным, а r - остатком.

Доказательство. 1. b>0. Рассмотрим числовую прямую и разобьём её на отрезки длины b точками 0, ± b, ±2b, ± Зb,...

-2b -b 0 b 2b

Очевидно, что где бы ни было расположено число а, оно обязательно попадёт в один из полуинтервалов [ bq, b(q + 1)), где q - целое, так как числовая прямая - объединение всех таких полуинтервалов. То есть найдётся целое q, что bq a<b(q + 1). К каждой части неравенства прибавим -bq, получим 0 a-bq <b. Обозначим a-bq-r. Тогда a = bq + r, 0 r <b = .

2. b < 0. Тогда -b > 0 и по доказанному для а и - b существуют целые q и r, что a=(-b)q + r, 0 r < Откуда получаем: а = b(-q)+r, где 0 r < . Существование q и r доказано.

Докажем единственность. Пусть a = bq + r, где 0 r < , и а=b + , где 0 < Имеем: bq + r= b + , b(q - ) = -r. Если q= то r= . Если же q≠ , то ( -r)⁞b и, следовательно, (свойство делимости 5).

Однако противоречие. Следовательно, q=

2. НОД и НОК целых чисел. Свойства. Алгоритм Евклида.

§3. НОД и НОК, алгоритм Евклида

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

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

d = . То есть d=( ), если

1) d € N,

2) d - общий делитель чисел

3)если с - общий делитель чисел , то d⁞c.

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

Определение. Наименьшим общим кратным целых чисел называется такое их общее натуральное кратное m, которое делит любое их общее кратное. Обозначают: m = [

Итак, m = [ ], если

1) m€N

2) m - общее кратное чисел

3) если М - общее кратное чисел , то M⁞m.

Пример: (16,30,12)= 2; [16,30,12] = 16*5 *3 = 240.

Лемма. Если a, b€Z, b≠0 и a=bq + r, то (а,b)=(b,r). Доказательство. Пусть (a,b)= , (b,r)= .Так как a⁞ то r=a-bq . Следовательно, - общий делитель чисел b и r, поэтому их наибольший общий делитель

= (b,r) .

Так как b⁞ , r⁞ ,то a⁞ ,и - общий делитель чисел а и b.

Поэтому ⁞ . Из того, что ⁞ , ⁞ ] и , следует, что

=

Пусть a,b€Z, b≠ 0. По теореме о делении с остатком

a=b . Если , то

b= . Если , то

= . И так далее.

…………..

=

=

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

Полученную цепочку равенств называют алгоритмом Евклида. Алгоритм Евклида, применённый к целым числам а и b, где b≠ 0, заключается в том, что сначала а делим на b с остатком, а затем каждый раз делим делитель на новый остаток, пока ни получим остаток, равный нулю.

Теорема. Последний, не равный нулю остаток в алгоритме Евклида, применённом к целым числам а и b, где b≠0, есть их наибольший общий делитель (НОД).

Доказательство. Применяя лемму к первому, второму и так далее равенствам алгоритма Евклида, имеем:

(а, b)=(b, )=()=... = ()= , так как

Из теоремы следует существование НОД двух чисел, если хотя бы одно из них не равно нулю.