Листок 6. ДЕЛИМОСТЬ

Выдан 20.10.84.

В этом и следующем листочках а...z - натуральные!

Опр.1. Для любого a, b: a⋮b ⇐df⇒ ∃k: a=kb.
Опр.2. d общий делитель a, b ⇐df⇒ a⋮d.AND.b⋮d
Onp.3. d=H0Д(a, b) ⇐df⇒ d - общий делитель a, b AND d делится на любой общий делитель а,b.
Опр.4. a, b -взаимно просты ⇐df⇒ НОД(а,b)=1.
Опр.5. Р ∋ р-простое ⇐df⇒ ∀k (k<р) НОД(k,p)=1
Опр.6. l - составное ⇐df⇒ l - не простое.

1. Сформулировать опр 6 без отрицания.

1.Доказать,что если р не делится на ∀ k: (1 < k ≤ √р)⇒ p ∊P.

2*. Для ∀ а1, а2,. ., an ∃ только один НОД(а1, а2,. ., an). Для этого
а) Расмотреть функцию ( линейную комбинацию) y=а1y1 + а2x2+...+anxn и док., что она делится на люб. общ. делитель
б) разделив аi с остатком на min у, доказать: min у =НОД(а1, а2,. ., an)

3. ДОК. A = {а1, а2,. ., an}.AND. A = A1A∪A2A∪. .∪An .AND. Ai≠0 ⇒
НОД(A) = НОД(НОД(A1), НОД(A2),. ., НОД(An))
Указание св-во 3

4. а,b, с -вз. просты ⇔ ∃х,у,z: ax+by+cz=1

5. bc⋮a .AND. НОД(а,b)=1 ⇒ c⋮a

6** Для док-ва алгоритма Евклида расмотрим следующую програму на языке BASIC91.

  1. Ввести a, b
  2. Присвоить i=1
  3. Найти такие q[i] and r[i], что a=q[i]*b+r[i]
  4. Если r[i]=0, то перейти к строке 7
  5. Переобозначим a=b, b=r[i], i = i + l
  6. Вернуться к 3 строке.
  7. Напечатать: "НОД(а, b)= r[i-1] Докажите !"

Опр. 7. Каноническим разложением КРАЗом для a наз. a = p1i1 * p2i2 * ... * pnin, где все pi простые.

7* Используя КРАЗ сформулировать и доказать критерий взаимной простоты n чисел.

8.Способ получения НОД из КРАЗа.

9. Аналогично НОД определите НОК, сформулируйте утверждения аналогичные 3, 5, 8
b* докажите их

10! НОК(а,b)=а*b/НОД(а,b)

11. а2 - b2 = 1985

11. Док., что простым чисел бесконечно много.

12* Для ∀ k ∃ простое р k≤p≤2k.

13.Решить урав. относительно х, у: а*х + b*у = с
b)** Когда и как можно найти все его решения.