Простые и составные числа
Натуральное число $p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.
Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.
Найти делители числа $6$.
Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3, 6$. Значит делителем числа $6$ будут числа $1,2,3,6.$
Ответ: $1,2,3,6$.
Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.
Составным называют число, у которого кроме единицы и самого себя есть другие делители.
Примером простого числа может являться число $13$, примером составного число $14.$
Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.
Взаимно простые числа
Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД и сравнить его с $1$.
Попарно взаимно простые
Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.
$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$- простые числа, а показатели степеней- натуральные числа.
Представление числа в виде канонического разложения на простые множества облегчает нахождение наибольшего общего делителя чисел, и выступает как следствие доказательства или определения взаимно простых чисел.
Найти наибольший общий делитель чисел $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.Полученное число и будет искомым наибольшим общим делителем.
Определить, будут ли простыми, взаимно простыми числами числа $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$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Определить, будут ли простыми, взаимно простыми числами числа $39$ и $112$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
-
$39=3\cdot 13$
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
-
$НОД \ (39;112)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.
Определить будут ли простыми, взаимно простыми числами числа $883$ и $997$.
Решение: Воспользуемся для разложения на множители каноническим разложением:
-
$883=1\cdot 883$
$997=1\cdot 997$
-
$НОД \ (883;997)=1$
Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят только множители, равные $1$ и самому числу, значит числа будут являться простыми.
