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

проверено

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

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

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

Теорема 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. Наибольшим общим делителем8), или НОД9) чисел $ 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. Наименьшим общим кратным10), или НОК11) чисел $ 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 $ называются взаимно простыми12), если их наибольший общий делитель равен $ 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}$.

Литература

1) divisor
2) multiplier
3) multiple
4) $ m $ делит $ n $
5) $ n $ делится на $ m $
6) prime number
7) composite number
8) greatest common divisor
9) gcd
10) least common multiple
11) lcm
12) coprime, relatively prime
glossary/arithmetic/theorem/fundamental.txt · Последние изменения: 15.02.2014 16:00:22 — ladilova
Наверх
Яндекс.Метрика
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0