Лекция 3. Применение разложения чисел на простые множители.
Уравнения в целых числах. Числа Ферма

При разложении на простые множители числа n удобно объединять одинаковые сомножители, запиывая их в виде степеней. Так как любое число натуральное число $n$ можно записать в виде
MATHгде $p_i$ - простые числа, MATH, $\alpha_i\ge 0$. В этой записи можно было бы считать, что $\alpha_i>0$ (то есть MATH), однако удобно разрешать и $\alpha_i=0$. Тогда некоторые сомножители равны $1$ и соответствующее число $p_i$ в разложении (7) фактически отсутствует. Благодаря этому мы можем любые два числа $a,b\in\QTR{bf}{N}$ записать в виде:
MATHс одними и теми же простыми $p_1$, ..., $p_r$. Здесь $\alpha_i$, $\beta_i$ - неотрицательные целые числа.

Теорема 6. Если $a$ и $b$ записаны в виде (8), то
MATHгде $\min(\alpha,\beta)$ означает наименьшее из двух чисел $\alpha$ и $\beta$.

Доказательство. Если $d\mid \U{430}$, то разложение $d$ на простые множители по теореме единственности есть часть разложения $a$ (если $a=dq$, то разложение $a$ можно получить, перемножая разложения $d$ и $q$). Поэтому MATH, где MATH. Если к тому же $d\mid b$, то MATH, откуда MATH. НОД получается при MATH. Теорема доказана.

Пример. Рассмотрим числа $30$ и $48$. Имеем: $30=2\cdot3\cdot5$, $48=24\cdot3$. Отсюда $(30,48)=2\cdot3=6$.

Определение. Наименьшим общим кратным (НОК) двух отличных от $0$ целых чисел $a$ и $b$ называется наименьшее число $k$, для которого $a\mid k$ и $b\mid k$. НОК чисел $a$ и $b$ мы будем обозначать через $\{a,b\}$.

Теорема 7. Пусть натуральные числа $a$ и $b$ записаны в виде (8). Тогда:
MATHгде $\max(\alpha,\beta)$ означает наибольшее из двух чисел $\alpha$, $\beta$.

Доказательство аналогично доказательству предыдущей теоремы.

Пример. MATH.

Следствие 1. MATH.

В самом деле, MATH.

Следствие 2. Если $a\mid k$ и $b\mid k$, то $\{a,b\}$ $\mid$ $k$.

Теорема 8 (Евклид). Простых чисел бесконечно много.