Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23. Единица не является ни простым числом, ни составным.
Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).
Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).
Все натуральные числа считаются либо простыми, либо составными (кроме 1).
Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4. (нет ни дробей, ни 0, ни чисел ниже 0).
Зачастую множество простых чисел в математике обозначается буквой P.
Простые числа до 1000
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
Как определить, является ли число простым?
Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.
Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).
Более структурированный метод — это решето Эратосфена.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Взаимно простые числа
Это натуральные числа, у которых 1 — это единственный общий делитель. Например:
Число Мерсенна
Простое число Мерсенна — это простое число вида:
До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).
Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.
Почему 1 не является простым числом?
Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.
Почему 4 не является простым числом?
Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.
Самое большое простое число
21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:
Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).
НОД (6; 35) = 1. Следовательно, числа 6 и 35 являются взаимно-простыми.
Делители 27: 1; 3 ; 9; 27.
Делители 33: 1; 3 ; 11; 33.
НОД (27; 33) = 3. Так как НОД (27; 33) ≠ 1, то 27 и 33 не являются взаимно-простыми числами.
Можно ли по внешнему виду определить, являются ли числа взаимно-простыми или нет? В некоторых случаях, можно.
Например, если оба числа чётные, то у них есть общий делитель 2, следовательно, два чётных числа не могут быть взаимно-простыми.
Если запись одного числа оканчивается на 5, а другого — на 5 или на 0, то оба числа делятся на 5, а значит, их НОД не единица, и эти числа не взаимно-простые.
Если числа простые, они делятся только на 1 и на себя, значит, их наибольший общий делитель равен 1 и они — взаимно-простые. Является ли число простым, проще всего определить по таблице простых чисел.
В остальных случаях наибольший общий делитель составных чисел находят, разложив эти числа на простые множители, используя признаки делимости. Если при разложении оказывается, что единственный общий делитель равен 1, то эти числа являются взаимно-простыми.
2 Comments
Это определение и для трех чисел? Например, 4, 7 и 15?
Урок 6 Бесплатно Наибольший общий делитель. Взаимно простые числа
Сейчас мы научимся определять наибольший общий делитель для двух или трех чисел, познакомимся с алгоритмом Евклида и узнаем много всего интересного.
Наибольший общий делитель
Самое большое натуральное число, на которое делятся нацело два или более чисел, называется их наибольшим общим делителем (НОД).
При поиске НОД, например, 36 и 24, надо:
1. Записать их в виде разложения на простые множители
3. Вычислить произведение множителей, которые остались: \(\mathbf<2\cdot2\cdot3 = 12>\)
В итоге НОД чисел 36 и 24 равен 12.
Если при нахождении НОДа среди чисел есть одно, на которое делятся все остальные, то оно и будет тем самым НОДом.
Например, у чисел 12, 36 и 48 НОД = 12
Пример 1
Найдите все общие делители чисел:
А) 70, 105
Б) 18, 24
В) 45,75
Г) 324, 111, 432
Д) 320, 640, 960
Решение
Пример 2
На новогоднем утреннике дети получили пакеты с подарками. Всего во всех пакетах находилось 159 апельсинов и 106 яблок. Сколько детей было на новогодней ёлке? Сколько в каждом пакете было яблок и сколько апельсинов?
Решение
Ребят на елке было 53 человека. В каждом пакете подарка было по 3 апельсина и 2 яблока.
Пример 3
Для выезда на природу работникам предоставили несколько автобусов. В каждом автобусе равное число мест для сидения. 184 человека выехали в лес, а 138 отправились на озеро. Так вышло, что все места в автобусах были заняты, и, стоя, никто не ехал. Сколько автобусов было и сколько пассажиров ехало в каждом из них?
Решение
В каждом автобусе было по 23 места. В лес поехало 8 автобусов, а на озеро поехало 6 автобусов. Всего было 8 + 6 = 14 автобусов.
У меня есть дополнительная информация к этой части урока!
Всё достаточно просто: взять пару положительных чисел и получить по правилу новую пару, которая будет состоять из меньшего числа и разницы между большим и меньшим числом. Повторять алгоритм до тех пор, пока числа не получатся одинаковыми. Последнее число и будет НОДом первоначальной пары чисел.
Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной.
Пройти тест и получить оценку можно после входа или регистрации
Взаимно простые числа
Давайте разберёмся с некоторыми натуральными числами.
Число 15 имеет делители 1, 3, 5, а число 16 имеет делители 1, 2, 4, 8
Рассмотрев этот и другие примеры, не сложно догадаться, что натуральные числа, у которых НОД равен 1, называются взаимно простые.
Пример 1
Возьмем две пары чисел 12 и 18, 13 и 21. Выясним, есть ли среди них взаимно простые числа. Для этого каждое из чисел распишем по простым делителям.
12 имеет делители 1, 2, 3, 4, 6, 12
18 имеет делители 1, 2, 3, 6, 9, 18
Значит, числа 12 и 18 кроме единицы имеют общие делители 2, 3, 6, поэтому они не являются взаимно простыми числами. Повторим действия с другой парой чисел 13 и 21.
Число 13 делится нацело на 1, 13, а число 21 делится нацело на 1, 3, 7, 21.
Значит, вторая пара чисел состоит из взаимно простых.
Пример 2
Пусть у нас есть два числа 45 и 32, которые являются натуральными и составными.
Первое из них 45 имеет делители 1, 3, 5, 9, 15, 45, а натуральное число 32 имеет делители 1, 2, 4, 8, 16, 32
Оба числа из этой пары имеют единственный общий делитель- 1
Значит, числа 45 и 32 являются взаимно простыми. Запишем оба числа в виде разложения на простые множители
Числа из нашего примера, 45 и 32, в записи на множители не содержат равных чисел. Значит, разложения на простые множители двух и более взаимно простых чисел не включают одинаковых простых множителей.
Пример 3
Являются ли взаимно простыми числа:
А) 55 и 40
Б) 77 и 92
В) 14, 32 и 41
Г) 231 и 298
Д) 68 и 137
Решение:
Нет, не являются взаимно простыми числами
Да, являются взаимно простыми числами
Да, являются взаимно простыми числами
Да, являются взаимно простыми числами
Да, являются взаимно простыми числами
Пример 4
Найдите разложение на простые множители наибольшего общего делителя чисел a и b, если:
Решение
Признак делимости на произведение взаимно простых чисел: если данное натуральное число делится на каждое из взаимно простых чисел, то оно делится и на их произведение.
Рассмотрим этот признак на примере трех взаимно простых чисел.
Возьмем, например, 420.
Число 420 без остатка делится на 2, на 5 и на 7.
Числа 2, 5, 7 являются взаимно простыми (так как их НОД равен 1). Проверим, будет ли делиться 420 на произведение взаимно простых чисел 2, 5 и 7.
Очевидно, что 420 делится нацело на произведение чисел двух, пяти и семи.
Правило можно применять для любого количества множителей.
Пройти тест и получить оценку можно после входа или регистрации
Интересная информация
Алгоритм Евклида, который используется для нахождения НОДа и с которым мы познакомились выше, широко применяется при решении других математических задач. Например, он связан с цепными дробями и позволяет с их помощью уменьшать большие дроби до маленьких.
Кроме того, алгоритм используется при решении линейных диофантовых уравнений. Это такие уравнения, у которых могут быть несколько неизвестных целых величин, и все их нужно найти. Например, может быть такое уравнение:
Решением этого уравнения будет пара чисел
Могут быть и другие пары решений. Решение таких уравнений начинается обычно с нахождения НОДа чисел, стоящих перед неизвестными. В нашем случае мы бы находили \(\mathbf<НОД(2, 3)>\)
Не всегда данный алгоритм позволяет быстро решать задачи. Иногда можно потратить много времени, сделать много вычислений, прежде чем найти нужный результат. Это единственный большой минус одного из старейших численных алгоритмов.
Заключительный тест
Пройти тест и получить оценку можно после входа или регистрации
Целые числа будут взаимно простыми, когда у них не будет ни одного общего делителя (множителя), не считая ±1.
14, 25 взаимно простые — не существует общих делителей.
15, 25 не взаимно простые (общий делитель 5).
6, 8, 9 взаимно простые — не существует делителей, общих для 3-х чисел.
Пример: расстановим на плоскости точки с целыми координатами нулевой толщины, так чтобы из начала координат были видны лишь точки, у которых координаты взаимно просты.
Числа 4 и 9 взаимно простые, значит, диагональ решетки 4 на 9 не пересекает других точек решетки.
Целые числа a1, a2, …, ak, k>2 будут взаимно простыми, когда НОД этих чисел будет 1.
Свойства взаимно простых чисел.
Числа a и b взаимно просты лишь в том случае, если выполняется одно из эквивалентных условий:
Всякие 2 (разных) простых числа всегда будут взаимно простыми.
Когда a — делитель произведения bc, и a взаимно просто с b, значит a — делитель c.
Возможность того, что любое k, которое выбрано случайным образом, положительных целых чисел окажутся взаимно простыми, соответствует 1/ζ(k), при этом, при N→∞ возможность того, что k положительных целых чисел, которые меньше N (и которые выбраны случайно) окажутся взаимно простыми, стремится к 1/ζ(k).
2 натуральных числа, которые расположены рядом, всегда взаимно просты.
Примеры взаимно простых чисел:
8, 15 — взаимно простые, но не простые.
6, 8, 9 — не попарно взаимно простые, но взаимно простые числа.
8, 15, 49 — попарно взаимно простые.
Применение взаимно простых чисел.
Зачастую количество зубьев на звёздочках и количество звеньев цепи в цепной передаче стараются сделать взаимно простыми. Это дает более равномерный износ: все зубья звёздочки будут по очереди работать с каждым из звеньев цепи.
