Теория чисел

Виноградов И.М. «Основы теории чисел»

Теория чисел

Делимость

Целые числа: натуральные числа, 0 и отрицательные. Разница между соседними числами 1.
a + b, a - b, a * b целые.
Если a = b * q (при условии b q целые) обозначается b \ a
1. a кратно числу b
2. b делитель числа a
Если b \ m и m \ a то b \ a
Если в равенстве вида
```
a+b+...+m = n+o+...+z
```
известно для всех членов, кроме одного, что они кратны x, то этот один тоже кратен x.
a представляется единственным способом в виде
```
a = bq+r
где 0<=r<b
```
НОД a, b ... z обозначается (a, b, ... z)
Если (a, b, ... z) = 1 то эти числа взаимно простые
Если каждое из чисел (a, b, ... z) взаимно просто с каждым другим, то эти числа попарно простые
Если a кратно b, то совокупность общих делителей чисел a и b совпадает с совокупность делителей b
```
a = q*b
(a,b) = b
```
Поиск НОД - алгоритм Евклида. a, b положительны и a > b. НОД равен последнему не равному 0 остатку.
m любое положительное целое. (am, bm) = (a, b)m
Если (a,b) = 1 то (ac, b) = (c,b)
Если каждое a1 a2 ... an взаимно просто с b1 b2 ... bn то произведение a1 * a2 * ... * an взаимно просто с b1 * b2 * ... * bn

Совокупность общих кратных двух чисел совпадает с совокупностью кратных их общего наименьшего кратного

Общее наименьшее кратное равно их произведению деленному на НОД

Числа либо простые, либо составные. Составные = произведение простых в степени.

Всякое a либо взаимно просто с простым p, либо делится на p

Разложение составного числа на простые сомножители единственно. Это называется каноническое разложение.

Пусть A - каноническое разложение = p[i] ^ a[i] тогда все делители - числа вида p[i] ^ b[i] где 0 <= b[i] <= a[i]

Вещественные числа - разложения, рациональные/иррациональные - стр. 20