1 и 12 взаимно простые. Взаимно простые числа
$p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.
Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.
Пример 1
Найти делители числа $6$.
Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3, 6$. Значит делителем числа $6$ будут числа $1,2,3,6.$
Ответ: $1,2,3,6$.
Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.
Определение 2
Составным называют число, у которого кроме единицы и самого себя есть другие делители.
Примером простого числа может являться число $13$, примером составного число $14.$
Замечание 1
Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.
Взаимно простые числа
Определение 3
Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД и сравнить его с $1$.
Попарно взаимно простые
Определение 4
Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми . Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.
Пример 2
$8, 15$ - не простые, но взаимно простые.
$6, 8, 9$ - взаимно простые числа, но не попарно взаимно простые.
$8, 15, 49$ - попарно взаимно простые.
Как мы видим, для того, чтобы определить являются ли числа взаимно простыми, необходимо сначала разложить их на простые множители. Обратим внимание на то, как правильно это сделать.
Разложение на простые множители
Например, разложим на простые множители число $180$:
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$
Воспользуемся свойством степеней, тогда получим,
$180=2^2\cdot 3^2\cdot 5$
Такая запись разложения на простые множители называется канонической, т.е. для того чтобы разложить в канонической форме число на множители необходимо воспользоваться свойством степеней и представить число в виде произведения степеней с разными основаниями
Каноническое разложение натурального числа в общем виде
Каноническое разложение натурального числа в общем виде имеет вид:
$m=p^{n1}_1\cdot p^{n2}_2\cdot \dots \dots ..\cdot p^{nk}_k$
где $p_1,p_2\dots \dots .p_k$- простые числа, а показатели степеней- натуральные числа.
Представление числа в виде канонического разложения на простые множества облегчает нахождение наибольшего общего делителя чисел, и выступает как следствие доказательства или определения взаимно простых чисел.
Пример 3
Найти наибольший общий делитель чисел $180$ и $240$.
Решение: Разложим числа на простые множества с помощью канонического разложения
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тогда $180=2^2\cdot 3^2\cdot 5$
$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тогда $240=2^4\cdot 3\cdot 5$
Теперь найдем НОД этих чисел, для этого выберем степени с одинаковым основанием и с наименьшим показателем степени, тогда
$НОД \ (180;240)= 2^2\cdot 3\cdot 5=60$
Составим алгоритм нахождения НОД с учетом канонического разложения на простые множители .
Чтобы найти наибольший общий делитель двух чисел с помощью канонического разложения, необходимо:
- разложить числа на простые множители в каноническом виде
- выбрать степени с одинаковым основанием и с наименьшим показателем степени входящих в состав разложения этих чисел
- Найти произведение чисел, найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
Пример 4
Определить, будут ли простыми, взаимно простыми числами числа $195$ и $336$.
$195=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$НОД \ (195;336) =3\cdot 5=15$
Мы видим, что НОД этих чисел отличен от $1$, значит числа не взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Пример 5
Определить, будут ли простыми, взаимно простыми числами числа $39$ и $112$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$НОД \ (39;112)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Пример 6
Определить будут ли простыми, взаимно простыми числами числа $883$ и $997$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
$883=1\cdot 883$
$997=1\cdot 997$
$НОД \ (883;997)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят только множители, равные $1$ и самому числу, значит числа будут являться простыми.
Натуральные числа a и b называют взаимно простыми , если их наибольший общий делитель равен 1 (НОД(a ; b ) = 1). Другими словами, если числа a и b не имеют никаких общих делителей, кроме 1, то они взаимно просты.
Примеры пар взаимно простых чисел: 2 и 5, 13 и 16, 35 и 88 и т. п. Можно указать несколько взаимно простых чисел, например, числа 7, 9, 16 – взаимно просты.
Часто взаимно простые числа обозначают так: (a , b ) = 1. Например, (23, 30) = 1. Эта запись как бы является сокращенной записью обозначения наибольшего общего делителя двух чисел (НОД(23, 30) = 1), и говорит о том, что их наибольший общий делитель равен 1.
Два соседних натуральных числа всегда будут взаимно просты. Например, 15 и 16 - пара взаимно простых чисел, также как 16 и 17. Это легко понять, если принять во внимание «правило» о том, что если два натуральных числа a и b делятся на одно и то же натуральное число большее 1 (n > 1), то и их разница также должна делится на это число n (здесь имеется в виду, что a , b и их разность делятся нацело, т. е. кратны числу n ). Но если a и b два соседних числа (пусть a < b ), то b – a = 1; но 1 делится только на 1 (из ряда натуральных чисел). Следовательно, a и b не имеют других общих делителей, кроме 1.
Из определения взаимно простых чисел и простых чисел также следует, что разные простые числа всегда оказываются взаимно простыми . Ведь делителями любого простого числа являются лишь оно само и 1.
Свойства взаимно простых чисел
- Наименьшее общее кратное (НОК) пары взаимно простых чисел равно их произведению. Например, (3, 8) = 1 (это значит взаимно просты), следовательно, их НОК равен 3 × 8 = 24 (НОК(3, 8) = 24). Действительно, вы не найдете меньшее число, чем 24, которое было бы кратно и 3 и 8.
- Если числа a и b взаимно просты и число c кратно как a , так и b , то это число будет кратно и произведению ab . Это можно записать так: если с a и c b , то c ab . Например, (3, 10) = 1, число 60 кратно как 3, так и 10, а также кратно 30 (3 × 10).
- Если числа a и b взаимно просты и взято число c кратное b (c b ), то произведение ac также будет также кратно b (ac b ). Например, (2, 17) = 1, пусть c = 34. Число 34 кратно b = 17, тогда ac = 2 × 34 = 68. Проверяем: 68 ÷ 17 = 4, т. е. делится нацело, а значит 68 кратно 17.
Обычно выделяют больше свойств, чем приведено здесь. Кроме того, свойства взаимно простых чисел формулируются по разному. Также бывает требуется доказать эти свойства (в данном случае доказательства не приводятся).
$p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.
Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.
Пример 1
Найти делители числа $6$.
Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3, 6$. Значит делителем числа $6$ будут числа $1,2,3,6.$
Ответ: $1,2,3,6$.
Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.
Определение 2
Составным называют число, у которого кроме единицы и самого себя есть другие делители.
Примером простого числа может являться число $13$, примером составного число $14.$
Замечание 1
Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.
Взаимно простые числа
Определение 3
Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД и сравнить его с $1$.
Попарно взаимно простые
Определение 4
Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми . Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.
Пример 2
$8, 15$ - не простые, но взаимно простые.
$6, 8, 9$ - взаимно простые числа, но не попарно взаимно простые.
$8, 15, 49$ - попарно взаимно простые.
Как мы видим, для того, чтобы определить являются ли числа взаимно простыми, необходимо сначала разложить их на простые множители. Обратим внимание на то, как правильно это сделать.
Разложение на простые множители
Например, разложим на простые множители число $180$:
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$
Воспользуемся свойством степеней, тогда получим,
$180=2^2\cdot 3^2\cdot 5$
Такая запись разложения на простые множители называется канонической, т.е. для того чтобы разложить в канонической форме число на множители необходимо воспользоваться свойством степеней и представить число в виде произведения степеней с разными основаниями
Каноническое разложение натурального числа в общем виде
Каноническое разложение натурального числа в общем виде имеет вид:
$m=p^{n1}_1\cdot p^{n2}_2\cdot \dots \dots ..\cdot p^{nk}_k$
где $p_1,p_2\dots \dots .p_k$- простые числа, а показатели степеней- натуральные числа.
Представление числа в виде канонического разложения на простые множества облегчает нахождение наибольшего общего делителя чисел, и выступает как следствие доказательства или определения взаимно простых чисел.
Пример 3
Найти наибольший общий делитель чисел $180$ и $240$.
Решение: Разложим числа на простые множества с помощью канонического разложения
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тогда $180=2^2\cdot 3^2\cdot 5$
$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тогда $240=2^4\cdot 3\cdot 5$
Теперь найдем НОД этих чисел, для этого выберем степени с одинаковым основанием и с наименьшим показателем степени, тогда
$НОД \ (180;240)= 2^2\cdot 3\cdot 5=60$
Составим алгоритм нахождения НОД с учетом канонического разложения на простые множители .
Чтобы найти наибольший общий делитель двух чисел с помощью канонического разложения, необходимо:
- разложить числа на простые множители в каноническом виде
- выбрать степени с одинаковым основанием и с наименьшим показателем степени входящих в состав разложения этих чисел
- Найти произведение чисел, найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
Пример 4
Определить, будут ли простыми, взаимно простыми числами числа $195$ и $336$.
$195=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$НОД \ (195;336) =3\cdot 5=15$
Мы видим, что НОД этих чисел отличен от $1$, значит числа не взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Пример 5
Определить, будут ли простыми, взаимно простыми числами числа $39$ и $112$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$НОД \ (39;112)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Пример 6
Определить будут ли простыми, взаимно простыми числами числа $883$ и $997$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
$883=1\cdot 883$
$997=1\cdot 997$
$НОД \ (883;997)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят только множители, равные $1$ и самому числу, значит числа будут являться простыми.
Определение1 . Целые числа а 1 ,а 2 ,…,a k называются взаимно-простыми, если (а 1 ,а 2 ,…,a k) =1
Определение 2. Целые числа а 1 ,а 2 ,…,a k называются попарно взаимно-простыми, если i,s (i, s = 1, 2, .. , к, is, (а i , а s) =1).
Если числа удовлетворяют определению 2, то они удовлетворяют и определению 1. Обратное утверждение в общем случае неверно, например: (15, 21, 19)= 1, но (15, 21) = 3
Теорема (критерий взаимной простоты)
(а, b) = 1 <=> х, у Z: ах + by = 1
Доказательство:
Докажем необходимость. Пусть (а, b) = 1. Выше мы показали, что если d=(a,b), то х, y Z: d = ax +by.
Т.к. в этом случае d =1, то будут х, y Z (определяемые из алгоритма Евклида): 1 = ах + bу.
Достаточность. Пусть (*) ах + by = 1, докажем, что (а, b)=1. Предположим, что (a, b) = d, тогда в левой части равенства (*)
(a / d) & (b /d) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.
§4. Нок целых чисел и его свойства.
Определение 1. Общим кратным конечного множества целых чисел а 1 ,а 2 ,…,a k , отличных от нуля, называют целое число m, которое делится на все числа a i (i=l, 2,…, к)
Определение 2. Целое число (m) называется наименьшим общим кратным чисел а 1 ,а 2 ,…,a k , отличных от нуля, если:
1 m - является их общим кратным;
2 (m) делит любое другое общее кратное этих чисел.
Обозначение: m = НОК (а 1 ,а 2 ,…,a k) или m = [а 1 ,а 2 ,…,a k ]
Пример. Даны числа: 2, 3, 4, 6, 12.
Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.
НОК определяется однозначно с точностью до порядка следования сомножителей. Действительно, если предположить, что m 1 = [а, b] &m 2 = (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Между наименьшим общим кратным и наибольшим общим делителем двух целых чисел существует зависимость, которая выражается формулой: [а, b] = ab/(а, b) (выведите ее самостоятельно)
Эта связь позволяет утверждать, что для любой пары целых чисел, отличных от нуля, существует их наименьшее общее кратное. Действительно, (а, b) – всегда можно однозначно вывести из алгоритма Евклида и по определению (а, b) 0, тогда дробь ab/(а, b) 0 и будет определена однозначно.
Наиболее просто НОК двух целых чисел вычисляется в том случае, когда (а,b)= 1, тогда [а, b] = ab/1 = а b
Например, = 215/1 = 105, т. к. (21, 5) = 1.
§5. Простые числа и их свойства.
Определение 1. Натуральное число (р) называется простым, если р > 1 и не имеет положит. делителей, отличных от 1 и р.
Определение 2. Натуральное число а >1, имеющее кроме 1 и самого себя другие положительные делители, называется составным.
Из этих определений следует, что множество натуральных чисел можно разбить на три класса:
а) составные числа;
б) простые числа;
в) единица.
Если
а - составное, то а = nq,
где 1 Задача
1.
Доказать, что если aZ
и р - простое число, то (а, р) = 1 v
(a
/ р) Доказательство.
Пусть
d
= (а, р) =>
(a
/d)
& (р /d),
т.к. р - простое число, то оно имеет два
делителя 1 и р. Если (а, р) = 1, то а и р
взаимно просты, если (а, р) = р, то (а/р). Задача
2.
Если произведение нескольких сомножителей
делится на р, то по крайней мере один из
сомножителей делится на р. Решение.
Пусть
произведение (а 1 ,а 2 ,...,
а k)/р,
если все a i
не будут делиться на р, тогда и произведение
будет взаимно просто с р, следовательно,
какой-то сомножитель делится на р. Задача
3.
Доказать, что наименьший отличный от 1
делитель целого числа а>1, есть число
простое. Доказательство.
Пусть
aZ
и а - составное число (если а = р, то
утверждение доказано), тогда а = a 1 q. Пусть
q
- наименьший делитель, покажем, что он
будет простым числом. Если предположить,
что q
- составное число, тогда q
= q 1 k
и а = a 1 q 1 k,
т.к. q 1 Задача
4.
Доказать, что наименьший простой
делитель (р) натурального числа (n)
не превосходит n
. Доказательство.
Пусть
n
= рn 1 ,
причем р < n 1
и р - простое. Тогда n
р 2
=> р<n
. Из
этого утверждения следует, что если
натуральное число (n)
не делится ни на одно простое число р
n
, то n
– простое, в противном случае оно будет
составным. Пример
1
.
Выяснить, будет ли число 137 простым?
11 <137
<12. Выписываем
простые делители, не превосходящие
137:
2, 3, 5, 7, 11. Проверяем, что 137 не делится на
2, на 3, на 5, на 7, на 11. Следовательно, число
137 – простое. Теорема
Евклида
.
Множество простых чисел бесконечно. Доказательство.
Предположим
противное, пусть p 1 ,p 2 ,...,
p k
все
простые числа, где p 1
= 2, а p k
– самое
большое простое число. Составим
натуральное число
=
p 1 p 2
...
p к
+1,
т.к.
p i
, то оно должно быть составным, тогда
его наименьший делитель будет простым
(см. задачу 3). Однако
не делится ни на p 1
, ни на
p 2
,…, ни
на p k
, т.к. 1
не делится на любое p I . Следовательно,
наше предположение о конечности множества
простых чисел было неверно. Однако существует
теорема, которая утверждает, что простые
числа составляют лишь небольшую часть
чисел натурального ряда. Теорема
об интервалах.
В натуральном ряду существует сколь
угодно длинные интервалы, не содержащие
ни одного простого числа. Доказательство.
Возьмём
произвольное натуральное число (n)
и составим последовательность натуральных
чисел (n+1)!+2,
n+1)!+3,…,(n+1)!+(n+1). В
этой последовательности каждое
последующее число на 1 больше предыдущего,
все эти числа составные, т.к. каждое
имеет более двух делителей (например,
первое число делится на 1, на 2 и само на
себя). При n→∞
мы получим сколь угодно длинный интервал,
состоящий только из составных чисел. Теорема Евклида
и теорема об интервалах свидетельствуют
о сложном характере распределения
простых чисел в натуральном ряду. Основная теорема
арифметики
Любое
натуральное число n>1
может быть представлено единственным
образом в виде произведения простых
чисел, с точностью до порядка следования
сомножителей. Доказательство.
Докажем возможность
представления: Пусть
nN
и n>1,
если n
– простое число, то n
= p
и теорема доказана. Если n
– составное, то наименьший его делитель
будет числом простым и n
= p 1 n 1 ,
где n 1 Далее
рассуждаем аналогично. Если n 1
простое число, то теорема доказана, если
n 1
составное число, то n 1
= p 2 n 2
, где n 2
< n 1
и тогда n
= p 1 p 2 n 2
. На каком-то шаге получим n
= p 1 p 2
…p n
, где все p i
- простые числа. Докажем единственность
разложения: Предположим,
что для числа (n)
есть два различных представления: n
= p 1 p 2
…p k ,
n
= q 1 q 2
…q n
и n>k. Тогда
получим, что p 1 p 2
…p k
= q 1 q 2
…q n
(1). Левая
часть равенства (1) делится на p 1 ,
тогда по свойству простых чисел (см.
задача 2), по крайней мере, один из
сомножителей правой части должен
делиться на p 1 . Пусть
(q 1 /p 1)
=> (q 1 =p 1).
Разделив обе части равенства (1) на p 1 ,
получим равенство p 2 p 3
…p k
= q 2 q 3
…q n
. Повторяя
прежнее рассуждение ещё (k-1)
раз, мы получим равенство 1 = q k +1 q k +2
…q n
, т.к. все
q i
>1, то это
равенство невозможно. Следовательно,
в обеих разложениях число сомножителей
одинаково (k=n)
и сами сомножители одинаковы. Замечание.
В разложении числа (n)
на простые сомножители некоторые из
них могут повторяться. Обозначая буквами
1 , 2 ,…, k
кратность
их вхождения в (n),
получим так называемое каноническое
разложение числа (n):
Пример
2.
Каноническое
разложение числа 588000 = 2 5 35 3 7 2 Следствие
1.
Если
Пример
3.
Все делители
числа 720 = 2 4 3 2 5
получим, если в выражении
Искомые делители
будут равны: 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. Следствие
2.
Если
P 1 1
p 2 2
…p k k
,
где
i
= max( I ,
i). Пример
4.
Найти
НОД(a,
b)
и НОК(a,
b),
используя каноническое разложение,
если (24,
42) = 23
= 6
тогда все делители числа (n)
имеют вид:
где 0 i i
(i
= 1, 2,…,k).
вместо 1 ,
2 ,
3
, независимо друг от друга, будем
подставлять значения: 1 =0,
1, 2, 3, 4, 2 =0,
1, 2, 3
= 0, 1.
и
то
(a, b) = p 1 1
p 2 2
…p k k ,
где
i
= min( I ,
i)
