Алгоритм Евклида. Основная теорема арифметики.

Целые числа.

Определение 4.5 Даны a и b N. Если существует d N, такое, что a+d=b, то мы говорим, что a меньше либо равно b. Обозначается ab (либо b больше либо равно a, обозначается: ba).

  1. Докажите следующие утверждения, где a,b,c N:
    a). aa
    b). ((ab) (ba)) (a=b)
    c). ((ab) (bc)) (ac)

Определение 4.6 Если в определении 4.5 d 0 , то мы говорим, что a строго меньше (меньше) b. Обозначается: a < b (либо b строго больше(больше) a, обозначается b > a ).

  1. Доказать ( a,b,c N):
    a). (a < a) - ложно
    b). ((a < b) (b < a)) - ложно
    c). ((a < b) (b < c)) (a< c)

Определение 4.7   Пусть ab, где a,bN, тогда чтобы выразить существование элемента dN такого, что a+d=b, мы будем писать: d=b-a. Операцию, которая каждой такой паре < a , b > ставит в соответствие элемент d, мы назовем вычитанием, а число d - разностью a и b.

  1. Доказать, где a,b,x,y N:
    a). ((a-b=d) (a-b=d1)) (d=d1)
    b). для любого mN : b-a=(b+m)-(a+m)
    c). (a < b) ((a + m) < (b + m)), для любого mN.
    d). ((a < b) (x < y)) ((a + x) < (b + y))

Определение 4.8 Множеством целых чисел Z назовем множество, удовлетворяющее следующим аксиомам:

1). Z=N N-

2). Для любого элемента nN существует единственный элемент (-n) N-

3). Для любого элемента nN- существует единственный элемент (-n) N

Определение 4.9 Аксиомы операции сложения(+) и умножения(* ):

a). a + b = b + a e). x * y = y * x
b). (a + b) + c= a + (b + c) f). (x * y) * z = x * (y * z)
c). a + 0 = a g). x * 1 = x
d). a + (-a) = 0. h). (x + y) * z = x * z + y * z.

Определение 4.10 Операцию, которая каждой паре < a , b > ставит в соответствие элемент d по правилу: d = a + (-b), a,bZ, назовем вычитанием(-) и будем записывать так: d = a - b. Число d назовем разностью между a и b.

  1. Доказать (x, y, z Z):
a). 0 = (-0) d). (-x) + y = x - y
b). x * 0 = 0 e). (-x) * y = x * (-y) = (-1) * x * y
c). (-1) * x = (-x) f). (x - y) * z = (x * z) - (y * z).

Определение 4.11 Даны a и b Z. Если существует d 0, dN, такое, что a+d=b, то мы говорим, что a меньше b. Обозначается a < b (либо b больше a, обозначается: b > a). Числа, большие нуля назовем положительными, а меньшие нуля - отрицательными (понятия , вводятся аналогично определению 4.5).

  1. Доказать, что для любых a, b N (где a = b * q + r, 0 r < b, q > 0)
    a). НОД (a, b) = НОД (a-b, b) b). НОД (a, b) = НОД (b, r)

Определение 4.12 (Алгоритм Евклида) (a, b, q1, q2,..., qn, r1, r2,..., rn N)

1) Пусть a = b * q1 + r1, 0 r1 < b, q1 > 0. По аналогии с задачей 21b от рассмотрения пары <a, b> перейдем к паре <b, r1>.
2) Пусть b = r1 * q2 + r2, 0 r2 < r1, q2 > 0. От пары <b, r1> перейдем к паре <r1, r2>.
3) Пусть r1 = r2 * q3 + r3, 0 r3 < r2, q3 > 0. От пары <r1, r2> перейдем к паре <r2, r3>
и т.д. Алгоритм останавливается, когда rn-1 = rn * qn.

  1. а). Доказать, что для любых исходных a и b алгоритм остановится после конечного числа шагов
    b). Доказать, что НОД (a, b) = НОД (b, r1) = ... = НОД (rn-1, rn) = НОД (rn, 0) = rn.
  2.   Есть 2 банки (емкостью 310 мл. и 210 мл.). Можно ли с помощью этих двух банок перелить из полной бочки достаточного объема в такую же пустую:
    a). 3000 мл. b). 10 мл. c). 45 мл.
  3.   Используя алгоритм Евклида, найти НОД (13471836, 8359848).
  4. а). Доказать, что если a и b - взаимно просты, то существуют такие x, y Z, что ax + by = 1
    b). Доказать, что если НОД (a, b) = d, то существуют такие x, y Z, что ax + by = d
  5. Доказать, что если существуют такие x, y Z, что ax + by = 1, то НОД (a, b) = 1.
  6. Доказать, что если ab делится на p, а a не делится на p, то b делится на p.
  7. (Основная теорема арифметики) Доказать, что любое целое положительное число a > 1 единственным образом (с точностью до перестановки множителей) разложимо в произведение простых чисел. (Иными словами, если , где P - множество простых чисел, то n = m и для всех i от 1 до n pi = qi).

[Вернутся к оглавлению]