Теория чисел и основные алгебраические структуры • Z - целые числа + − · > • N - натуральные числа • R - вещественные числа Аксиома индукции. A ⊂ N; A ̸= ø ⇒ в A есть наименьший элемент Th. ( о делении с остатком a, b ∈ Z b ̸= 0

⇒ ∃!q, r ∈ Z : a = b · q + r, 0 ≤ r < |b| Доказательство

• Существование 1. a > 0, b > 0 fix b Пусть не так, есть плохие a (множество плохих a ̸= ø) Пусть a0 - наименьшее плохое, значит a0 − 1 - хорошее, можно разделить с остатком a0 − 1 = b · q + r, 0 ≤ r < b, тогда a0 = (b · q + r) + 1, r + 1 < b a0 = b · (q + 1), т.е. a0 - хорошее 2. a < 0, b > 0 −a = b · q + r, 0 ≤ r < b a = −b · q − r 2.1. r = 0 a = b · (−q) + 0 2.2. r > 0 a = b · (−q) − b + b − r = b · (−q − 1) + b − r, 0 < r < b ⇒ 0 < b − r < b 3. b < 0, −b > 0 a = −b · q + r = b · (−q) + r, 0 ≤ r < b • Единственность Пусть q, q′ , r, r′ a = b · q + r a = b · q ′ + r ′ a − a = b · q + r − b · q ′ − r ′

0 = b · (q − q ′ ) + (r − r ′ )

r ′ − r = b · (q − q ′ ), q ̸= q ′ , |q − q ′ | ≥ 1

|b · (q − q ′ )| ≥ |b| r ′ , r ∈ [0; |b| − 1] |r − r ′ | < |b| − 1 Противоречие ⇒ q = q ′ , r = r ′

Def. a, b ∈ Z, a . . .b(b|a), если ∃c ∈ Z : a = bc

Rem. 0 . . .0 ∀x ∈ Z0 = 0 · x Основные свойства делимости: 1. 0 . . .a

1

2. a . . .1 3. a, b . . .c ⇒ a + b . . .c

4. a, k . . .c ⇒ k · a . . .c

5. a . . .a 6. a . . .b, b . . .a ⇒ a = ±b 7. a . . .b, b . . .c ⇒ a . . .c 8. ac . . .bc, c ̸= 0 ⇒ a . . .b

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

3. a . . .c ⇒ ∃qa : a = qa · c b . . .c ⇒ ∃qb : b = qb · c a + b = (qa + qb) · c 6. a = bx b = ay a = ayx a = a(xy) ⇒ "

a = 0, b ̸= 0

a ̸= 0, xy = 1 ⇒ x, y = ±1, a = ±b

8. ac . . .bc, c ̸= 0 ac = bc · x c · a = c · bx ⇒ a = bx (a . . .b)

Задача: при каких a, b, c ∈ Z уравнение ax + by = c имеет решение в целых числах (⇔ из чего состоит < a, b >? c ∈< a, b >?) Def. Идеалом называется подмножество I ⊂ Z: 1. I ̸= ø 2. a, b ∈ I ⇒ a + b ∈ I 3. a ∈ I, k ∈ Z ⇒ a · k ∈ I Ex. 1 c ∈ Z < c >= {n · c} = {x ∈ Z|x . . .c} - идеал, порожденный c - главный идеал

Ex. 2 c1, c2 · · · ck ∈ Z < c1, c2 · · · ck >= {n1c1 + n2c2 + · · · + nkck|ni ∈ Z} Th. в Z любой идеал - главный

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

I - идеал в Z, хотим b ∈ Z, I =< b > 1. I = {0} =< 0 >

2

2. ∃a ∈ I, a ̸= 0 ⇒ a ∈ I, a ∈ N. Рассмотрим наименььший натуральный b ∈ I Докажем I =< b > < b >⊂ I, b ∈ I, k · b ∈ I a ∈ I делим с остатком a = bq + r, 0 ≤ r < b r = a − bq b ∈ I ⇒ −bq ∈ I ⇒ a − bq ∈ I ⇒ r ∈ I r ∈ N - противоречие (b - наименььшее) ⇒ r /∈ N ⇒ r = 0 В частности ∀a, b ∈ Z ∃d :< a, b >=< d > Def. a, b ∈ Z НОД(a, b) = gcd(a, b) = (a, b) - такое d ∈ Z, что: 1. a . . .d, b . . .d 2. ∀d ′ : a . . .d ′ , b . . .d ′ ⇒ d . . .d ′

Rem. НОД определен однозначно с точностью до знака Доказательство

   d1 = (a, b) ⇒ a . . .d1, b . . .d1, d2 . . .d1

d2 = (a, b) ⇒ a . . .d2, b . . .d2, d1 . . .d2 ⇒ d1 = ±d2

Th. a, b ∈ Z 1. ∃(a, b) = d 2. ∃x, y ∈ Z : ax + by = d - линейное представление НОДа 3. ax + by = c имеет решение ⇔ c . . .d Доказательство 1 Рассмотрим I =< a, b > - по предыдущей теореме он главный < d >=< a, b > d = d · 1 ∈ I ⇒ d ∈< a, b >, т.е. ∃x, y : ax + by = d d = (a, b) n a . . .d’ ⇒ ax . . .d ′ b . . .d ′ ⇒ by . . .d ′ ⇒ d . . .d ′ a = a · 1 + b · 0 ∈< a, b >=< d >⇔ a . . .d

Аналогично b . . .d

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

⇒: c = ax + by    a . . .(a, b) b . . .(a, b) ⇒ c = ax + by . . .(a, b)

⇐: Пусть c . . .(a, b) = d, т.е. c = d · k, k ∈ Z ax + by = d anew = ak, bnew = bk anewx + bnewy = dk Lem. (a, b) = (a, b − a)    a, b . . .d ⇒ b − a ⇒ d a, b-a . . .d ⇒ b = a + (b − a) . . .d ⇒ одинаковые общие делители Следствие: b = aq + r ⇒ (a, b) = (a, r). Доказывается аналогично лемме Алгоритм Евклида:

3

1. a = bq + r1 b = r1q + r2 · · · 2. (a, b) = (r1, b) = (r1, r2)· · · , ∃i ∈ N : ri = 0 3. (a, b) = · · · = (rk, rk + 1) = (rk, 0) = rk Rem. a1, a2 · · · ak ∈ Z ∃(a1, a2 · · · ak) = d ∃x1 · · · xk ∈ Z : d = x1a1 + x2a2 + · · · + xkak

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

Рассмотрим идеал < a1, a2 · · · ak > ∃d :< d >=< a1 · · · ak >. Далее все как при k = 2 Def. a, b ∈ Z называются взаимнопростыми, если (a, b) = 1 Lm. a, b - взаимнопросты ⇔ ∃x, y : ax + by = 1

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

⇒ (a, b) = 1 ⇒ ∃x, y : ax + by = 1 ⇐ ax + by = 1 ⇒ 1 . . .(a, b) (a, b) = 1

Lm. об отбрасывании взаимнопростого множителя a, b, c ∈ Z    ab . . .c (a, c) = 1 ⇒ b . . .c

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

ab = cx ay + cz = 1 ⇒ aby + cbz = b . . .c

Def. p ∈ Z. p называется простым, если 1. |p| > 1 2. p ̸= xy |x|, |y| < |p| Ясно, что это равносильно тому, что p имеет ровно 4 делителя (±1, ±p) Lm. p - простое ⇔ ab . . .p ⇒    a . . .p b . . .p , |p| > 1

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

⇐ p = xy ⇒ xy . . .p ⇒    x . . .p y . . .p ⇒ " |x| ≥ p |y| ≥ p

⇒ Пусть p - простое, ab . . .p

   (a, p) = 1 ⇒ b . . .p (a, p) = p ⇒ a .