Содержание

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

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

проверено

Делимость целых чисел

Определение 1. Число $m\in\mathbb{Z}$ называется делителем¹⁾, или множителем²⁾ целого числа $n$ , если $n=mt$ для некоторого $t\in\mathbb{Z}$ . При этом $n$ называется кратным³⁾ $m$ . Для обозначения делимости используют символы $m|n$ ⁴⁾ или $n\vdots m$ ⁵⁾.

Определение 2. Положительное целое число $p\neq 1$ , которое не имеет других делителей, кроме $\pm 1$ и $\pm p$ , называется простым⁶⁾, в противном случае оно называется составным⁷⁾.

Теорема 1. (Основная теорема арифметики) Каждое положительное целое число $n\neq 1$ может быть записано в виде произведения простых чисел: $n=p_1\ldots p_s$ . Эта запись единственна с точностью до порядка множителей.

Обычно одинаковые простые множители группируют и используют запись: $n=p_1^{\varepsilon_1}\ldots p_k^{\varepsilon_k}$ , где $\varepsilon_i>0,\quad 1\leqslant i\leqslant k$ .

Теорема 2 (Теорема Евклида). Множество простых чисел бесконечно.

Наибольший общий делитель и наименьшее общее кратное

Для любых двух целых чисел можно записать их разложение на простые множители в виде произведения степеней одних и тех же простых чисел: $n=\pm p_1^{\alpha_1}\ldots p_k^{\alpha_k}$ и $m=\pm p_1^{\beta_1}\ldots p_k^{\beta_k}$ , где $\alpha_i,\beta_i\geqslant 0$

Определение 3. Наибольшим общим делителем⁸⁾, или НОД⁹⁾ чисел $n$ и $m$ называется число НОД $(m,n)=p_1^{\gamma_1}\ldots p_k^{\gamma_k}$ , где $\gamma_i=\textrm{min}\{\alpha_i,\beta_i\}, 1\leqslant i\leqslant k$ .

Определение 4. Наименьшим общим кратным¹⁰⁾, или НОК¹¹⁾ чисел $n$ и $m$ называется число НОК $(n,m)=p_1^{\delta_1}\ldots p_k^{\delta_k}$ , где $\delta_i=\textrm{max}\{\alpha_i,\beta_i\}, 1\leqslant i\leqslant k$ .

Определение 5. Два целых числа $n$ и $m$ называются взаимно простыми¹²⁾, если их наибольший общий делитель равен $1$ .

Предложение 1. НОД $(m,n)\vert n$ , НОД $(m,n)\vert m$ , и если $d\vert m,d\vert n$ , то $d\vert$ НОД $(m,n)$ .

Предложение 2. $n\vert$ НОК $(m,n)$ , $m\vert$ НОК $(m,n)$ , и если $m\vert u,n\vert u$ , то НОК $(m,n)\vert u$ .

Предложение 3. НОД $(m,n)\cdot$ НОК $(m,n)=mn$ . Если $n$ и $m$ взаимно просты, то НОК $(m,n)=mn$ .

Деление целых чисел

Предложение 4. При заданных $a,b\in\mathbb{Z},\,b>0$ , всегда найдутся $q,r\in\mathbb{Z}$ такие, что $a=bq+r,\,0\leqslant r<b$ .

Предложение 5. Наибольший общий делитель двух целых чисел $n$ и $m$ , не равных нулю одновременно, всегда записывается в виде $nu+mv$ для некоторых $u,v\in\mathbb{Z}$ . В частности, целые числа $n$ и $m$ взаимно просты тогда и только тогда, когда $nu+mv=1$ для некоторых $u,v\in\mathbb{Z}$ .

Литература

Кострикин А.И. «Введение в алгебру. Основы алгебры», МЦНМО, 2012.

теория чисел, делитель числа, кратное, множитель, наибольший общий делитель, наименьшее общее кратное, НОД, НОК, основная теорема арифметики, простое число, составное число, теорема евклида

¹⁾

divisor

²⁾

multiplier

³⁾

multiple

⁴⁾

$m$ делит $n$

⁵⁾

$n$ делится на $m$

⁶⁾

prime number

⁷⁾

composite number

⁸⁾

greatest common divisor

⁹⁾

gcd

¹⁰⁾

least common multiple

¹¹⁾

lcm

¹²⁾

coprime, relatively prime

glossary/arithmetic/theorem/fundamental.txt · Последние изменения: 15.02.2014 12:00:22 — Ладилова Анна

Наверх