Каноническое разложение числа
При разложении числа на простые множители, простые множители могут повторяться. Эти повторения можно записать более компактно с помощью степеней. Мы разложили какое то число a на простые множители p1,p2,p3 каждое из которых повторяется несколько раз т.е. s1,s2,s3 соответственно. Тогда число a мы можем записать как
a=p1s1 × p2s2 × p3s3 × p4s4 × … × pnsn.
Такая форма записи называется каноническое разложение числа на простые множители.
В разложении числа
a
на простые сомножители, некоторые из
них могут повторяться. Если простой
сомножитель
в разложении (2) повторяется k
раз, то его называют k
кратным множителем числа a,
или говорят, что множитель
имеет кратность k.
Обозначим символами
(m
n)
разные простые сомножители в разложении
(2). Пусть множитель p
,
имеет кратность k
.
Тогда разложение числа a
в произведение сомножителей можно
записать так:
a
=
.
Это представление
числа называют каноническим
разложением числа a на простые сомножители,
или
каноническим представлением числа a.
Поскольку число a
можно единственным способом записать
в виде произведения простых чисел, то
и каноническое представление числа a
единственно.
П р и м е р. Каноническим
разложением числа 588000 будет:
588000 = 2
3
5
7
.
Докажем теперь
несколько теорем, которые касаются
делителей чисел, а также наибольшего
общего делителя и наименьшего общего
кратного нескольких чисел.
Теорема 7. Если
a
=
каноническое
разложение числа
a,
то
множество всех
делителей этого числа
совпадает с
множеством чисел вида
d
=
, (3)
где
0
s
k
, i
= 1, 2, . . . , m.
Д е й с т в и т е л ь н
о, очевидно, что всякое число d
вида (3) является делителем числа a.
Наоборот, если d
является делителем числа a,
то a
= dq,
где q
некоторое натуральное число. Поскольку
для a
существует только одно каноническое
разложение, то из равенства a
= dq
вытекает, что в каноническое разложение
числа d
могут входить только простые числа
,
причем их степени не могут быть выше,
чем
Поэтому каноническое разложение d
имеет вид (3).
П р и м е р.
Все делители
числа 720 = 2
3
5 получим, если в выражении
заставим показатели степеней независимо
друг от друга пробегать значение
= 0, 1, 2, 3, 4,
= 0, 1, 2 и
= 0, 1. Поэтому указанными делителями
будут: 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144, 5,
10, 20, 40, 80, 15, 30, 60, 120, 240, 45, 90, 180, 360, 720
всего
(
+ 1)(
+ 1)(
+ 1)
делителей.
Теорема 8. Наибольшим
общим делителем нескольких чисел
a,
b,
c,
. . . , f
является число
(произведение
степеней) вида
,
где
общие простые
делители всех этих чисел ,
a
,
i
= 1,2,…,s
наименьшие из
показателей,
с
которыми каждое
с
входит в
канонические
разложения этих чисел.
Теорема 9. Совокупность
общих делителей нескольких чисел
совпадает с
совокупностью
делителей их наибольшего общего делителя.
Д е й с т в и т е л ь н
о, пусть d
общий делитель чисел
.
Тогда имеют место равенства вида
,
которые показывают, что: a) всякий простой
делитель p
числа d
должное быть и делителем каждого из
чисел
,
а также что: б) этот делитель p
должный входить в каноническое разложение
числа d
с показателем, который не превосходит
наименьшего из тех, из которым он входит
в канонические разложения чисел
.
Обратно, каждое d,
что удовлетворяет условиям a) и б),
очевидно, является общим делителем
чисел
.
Общим наибольшим
делителем, то есть наибольшим из общих
делителей (определения 1, Л-2) является
тот с последних, в каноническом разложении
которого показатели степеней простых
чисел равняются наименьшим из тех, с
которыми эти простые числа входят в
канонические разложения чисел
.
Остается лишь
отметить, что всякий общий делитель,
который имеет в каноническом разложении
все показатели, которые не превосходят
показателей в каноническом разложении
наибольшего общего делителя, является
делителем последнего.
П р и м е р . Наибольший
общий делитель чисел 6791400 =
=
,
178500 = 2
3
5
7
17 и 27720 = 2
3
5
7
11 равняется (6791400, 178500, 27720) = 2
3
5
7 = 420.
Теорема 10. Наименьшим
общим кратным нескольких чисел
a,
b,
c,
. . . , f
является число
(произведение
степеней) вида
,
где
простые делители
по меньшей мере одного из
этих чисел, a
показатели степеней
,
i =
1, 2, …, s
наибольшие из
показателей,
с которыми
каждое с
входит в
канонические разложения этих чисел.
Теорема 11. Наименьшее
общее кратное нескольких попарно простых
чисел равняется
их произведению.
Теорема 12. Совокупность
общих кратных нескольких чисел совпадает
с
совокупностью
кратных их наименьшего общего кратного.
Д е й с т в и т е л ь н
о, пусть М
общее кратное чисел
.
Тогда имеют место равенства вида M
=
,
…, М
=
,
которые показывают, что а) всякий
простой делитель p
каждого из чисел
должен быть и делителем числа М,
а также, что б) этот делитель p
должный входить в каноническое разложение
числа М
с показателем, не меньшим наибольшего
из тех, с которыми он входит в канонические
разложения чисел
.
Обратно, каждое М,
подчиненное условиям а) и б), очевидно,
является общим кратным чисел
.
Наименьшим общим
кратным, т.е наименьшим из общих кратных
(по определению), является то из последних
в каноническом разложении которого
показатели степеней простых чисел точно
равняются наибольшим из тех, с которыми
эти простые числа входят в канонические
разложения чисел
.
В случае, когда
попарно простые, каждый множитель вида
p
канонического разложения наименьшего
общего кратного входит в каноническое
разложение одного и только одного из
чисел
.
Наименьшее общее кратное последних,
очевидно, равняется их произведению.
Всякое общее кратное,
как то, что имеет в своем каноническом
разложении все показатели, не меньшие
соответствующих показателей в
каноническом
разложении НОК, будет кратным последнего.
П р и м е р . НОК чисел
1800 = 2
3
5
, 3780 = 2
3
5
7, 8910 =
= 2
3
5
11 равняется [1800, 3780, 8910] = 2
3
5
7
11 = 247000.
1
Эратосфен
Киренский (ок. 276-194 до н. э.)
древне-греческий ученый. Заложил основы
матем. географии. Труды по математике
(теории чисел), астрономии, филологии,
философии, музыки. От сочинений Э.
Киренского до нашего времени дошли
лишь отрывки.
6
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
☰
Что такое каноническое разложение числа и где оно используется?
Каноническим разложением натурального числа на простые множители называют такое его разложение, когда множители записываются в порядке возрастания. Например:
50 = 2 × 5 × 5
124 = 2 × 2 × 31
280 = 2 × 2 × 2 × 5 × 7
Обычно каноническое разложение записывают с использованием степеней:
50 = 2 × 52
124 = 22 × 31
280 = 23 × 5 × 7
Общий вид канонического разложения натурального число n имеет вид
, где p1 < p2 < … < pq.
Каноническое разложение чисел используется при нахождении их наибольших общих делителей (НОД) и наименьших общих кратных (НОК).
НОД(a, b) равен произведению множителей, которые входят в разложение на простые множители обоих чисел, при этом степень показателя у каждого из общих множителей должна быть взята, равной меньшему из показателей, с которым множитель входит в разложение a или b. Например, нам надо найти НОД(50, 280). У разложении чисел 50 и 280 есть два общих множителя – это 2 и 5. При этом наименьшие степени этих чисел равны 1. Поэтому НОД(50, 280) = 2 × 5 = 10.
Аналогично рассуждая, можно найти НОД(124, 280) = 22 = 4.
НОК(a, b) равно произведению множителей (с сохранением степени), которые входят в хотя бы одно разложение чисел на простые множители, умноженных на одинаковые для чисел a и b множители, которые надо взять в наибольшей из встречающихся степеней.
Таким образом, получаем НОК(50, 280) = 23 × 52 × 7 = 1400, НОК(124, 280) = 5 × 7 × 31 × 23 = 8680.
Содержание:
- Определение простого числа
- Разложение числа на множители
- Историческая справка
Определение простого числа
Определение
Простое число — это натуральное число, единственными
делителями которого являются только оно само и единица.
Все остальные натуральные числа называются
составными. Натуральное число 1 не является ни простым, ни составным.
Пример
Задание. Какие из записанных ниже натуральных чисел являются простыми:
$$2 ; 5 ; 11 ; 12 ; 13 ; 15 ; 21 ; 27 ; 29 ; 31 ; 32$$
Ответ. $2 ; 5 ; 13 ; 29 ; 31$
Разложение числа на множители
Представление натурального числа в виде произведения натуральных чисел называется разложением на множители.
Если в разложении на множители натурального числа все множители простые числа, то такое разложение называется
разложением на простые множители.
Теорема
(Основная теорема арифметики)
Каждое натуральное число, отличное от 1, может быть разложено на простые множители, и притом единственным образом
(если отождествлять разложения $p cdot q$ и $q cdot p$, где p$ и q$ — простые числа).
Объединяя в разложении числа
$n$ одинаковые простые сомножители, получаем так называемое каноническое разложение числа $n$:
$$n=p_{1}^{k_{1}} cdot p_{2}^{k_{2}} cdot ldots cdot p_{s}^{k_{s}}$$
где $p_{1}, p_{2}, dots p_{s}$, — различные простые числа, а $k_{1}, k_{2}, ldots k_{s}$ — натуральные числа.
236
проверенных автора готовы помочь в написании работы любой сложности
Мы помогли уже 4 430 ученикам и студентам сдать работы от решения задач до дипломных на отлично! Узнай стоимость своей работы за 15 минут!
Пример
Задание. Найти каноническое разложение чисел: $32 ; 108$
Решение. Для нахождения канонического разложения чисел нужно сначала разложить их на простые множители,
а затем объединить одинаковые множители и записать их произведение в виде степени с натуральным показателем:
$$32=2 cdot 2 cdot 2 cdot 2 cdot 2=2^{5}$$
$$108=2 cdot 54=2 cdot 2 cdot 27=2 cdot 2 cdot 3 cdot 3 cdot 3=2^{2} cdot 3^{3}$$
Ответ. $32=2^{5} ; 108=2^{2} cdot 3^{3}$
Историческая справка
Как определить, какое число простое, а какое нет? Наиболее распространенным методом позволяющим найти все простые числа в любом
числовом отрезке, предложил в III в. до н. э. Эратосфен (метод называется «решето Эратосфена»). Предположим, что нам нужно установить,
какие из чисел $2, ldots, N$ являются простыми. Выпишем их в ряд и
вычеркнем каждое второе число из следующих за числом 2 — все они составные, так как кратны числу 2. Первое из оставшихся невычеркнутых чисел —
3 — является простым. Вычеркнем каждое третье число из следующих за числом 3; следующее из невычеркнутых чисел — 5 — также будет простым.
По тому же принципу вычеркнем каждое пятое число из следующих за числом 5 и вообще каждое
$k$-е из следующих за числом $k$. Все оставшиеся невычеркнутыми числа будут простыми.
С увеличением $n$ простые числа постепенно встречаются
все реже и реже. Однако уже древним был хорошо известен тот факт, что их бесконечно много. Его доказательство приводится в «Началах» Евклида.
Предположим, что ряд простых чисел конечен, и обозначим последнее простое число в этом ряду буквой
$N$. Тогда число $x=1 cdot 2 cdot ldots cdot(N-1) cdot N+1$ должно быть составным. Это число при делении на числа
$2,3, ldots,(N-1), N$ всякий раз дает в остатке единицу. Таким образом, $x$ не делится без остатка ни на одно из чисел
$2, ldots, N$ а простых чисел, больших $N$, по нашему предположению, не существует. Но если бы
$x$ было составным числом, то оно должно было делиться хотя
бы на одно простое число. Мы приходим к противоречию — следовательно, ряд простых чисел бесконечен.
Читать дальше: что такое разность чисел.