Листок 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*. Для ∀ а₁, а₂,. ., a_n ∃ только один НОД(а₁, а₂,. ., a_n). Для этого
а) Расмотреть функцию ( линейную комбинацию) y=а₁y₁ + а₂x₂+...+a_nx_n и док., что она делится на люб. общ. делитель
б) разделив а_i с остатком на min у, доказать: min у =НОД(а₁, а₂,. ., a_n)

3. ДОК. A = {а₁, а₂,. ., a_n}.AND. A = A₁A∪A₂A∪. .∪A_n .AND. A_i≠0 ⇒
НОД(A) = НОД(НОД(A₁), НОД(A₂),. ., НОД(A_n))
Указание св-во 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 = p₁^i₁ * p₂^i₂ * ... * p_n^i_n, где все p_i простые.

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

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

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

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

11. а² - b² = 1985

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

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

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