Целые числа

Арифметика остатков

Обозначение

$a\equiv b \pmod{m}$ — числа $a$ и $b$ имеют равные остатки при делении на $m$.

Свойства

1. $a \equiv b ~\Leftrightarrow~ a+c\equiv b+c$;

2. $a \equiv b \pmod{m} ~\Leftrightarrow~ a \cdot c \equiv b \cdot c \pmod{m \cdot c}$;

3. $a\equiv b \pmod{m} ~\Leftrightarrow~ a\cdot c \equiv b \cdot c \pmod{m}$, при $НОД(c,m)=1$;

4. $a\equiv b ~\Rightarrow~a \cdot c \equiv b\cdot c$;

5. $a\equiv b \pmod{m \cdot c} ~\Rightarrow~ a\equiv b \pmod{m}$.

Основная теорема арифметики

Любое натуральное число $N>1$ имеет единственное разложение

$$\large N=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}$$

в котором $p_i$ — простые числа, $\alpha_i \in \N$.