Что такое наибольший простой делитель

Как находить наибольший общий делитель (НОД) двух чисел

Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.

Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение, используемое в математике.

Общие понятия и определения

Необходимо знать:

В математике приняты следующие записи:

Различные способы найти НОД

Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.

Например, НОД (15;45) = 15, НОД (48;24) = 24.

Но такие случаи в математике являются весьма редкими, поэтому для того, чтобы находить НОД используются более сложные приёмы, хотя проверять этот вариант перед началом работы все же весьма рекомендуется.

Способ разложения на простые сомножители

Если необходимо найти НОД двух или более различных чисел, достаточно разложить каждое из них на простые сомножители, а затем произвести процесс умножения тех из них, которые имеются в каждом из чисел.

Пример 1

Рассмотрим, как находить НОД 36 и 90:

НОД (36;90) = 1*2*3*3 = 18.

Теперь посмотрим как находить то же самое в случае трёх чисел, возьмём для примера 54; 162; 42.

Как разложить 36 мы уже знаем, разберёмся с остальными:

Таким образом, НОД (36;162;42) = 1*2*3 = 6.

Следует заметить, что единицу в разложении писать совершенно необязательно.

Рассмотрим способ, как просто раскладывать на простые множители, для этого слева запишем необходимую нам цифру, а справа станем писать простые делители.

Разделять колонки можно, как знаком деления, так и простой вертикальной чертой.

Евклидов способ

Этот вариант известен человечеству ещё со времён древнегреческой цивилизации, он во многом проще, и приписывается великому математику Евклиду, хотя весьма похожие алгоритмы применялись и ранее. Этот способ заключается в использовании следующего алгоритма, мы делим большее число с остатком на меньшее. Затем наш делитель делим на остаток и продолжаем так действовать по кругу пока не произойдёт деление нацело. Последнее значение и окажется искомым наибольшим общим делителем.

Приведём пример использования данного алгоритма:

попробуем выяснить какой НОД у 816 и 252:

Итак, по завершении нашего процесса мы получили НОД (816;252) = 12.

Действия при необходимости определения НОД если задано более двух значений

Мы уже разобрались, что делать в случае, когда имеется два различных числа, теперь научимся действовать, если их имеется 3 и более.

При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.

Заключение

Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.

Видео

С помощью видео вы сможете узнать, как найти наибольший общий делитель.

Источник

Наибольший общий делитель (НОД), свойства и формулы

Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).

Понятие наибольшего общего делителя

Начнем с самого начала и вспомним, что такое общий делитель. У целого числа может быть несколько делителей. А сейчас нам особенно интересно, как обращаться с делителями сразу нескольких целых чисел.

Делитель натурального числа — это такое натуральное число, которое делит данное число без остатка. Если у натурального числа больше двух делителей, его называют составным.

Если b — делитель целого числа a, которое не равно нулю, то модуль числа b не может быть больше модуля числа a. Значит любое число, не равное 0, имеет конечное число делителей.

Наибольшим общим делителем двух чисел a и b называется наибольшее число, на которое a и b делятся без остатка. Для записи может использоваться аббревиатура НОД. Для двух чисел можно записать вот так: НОД (a, b).

Проверить результаты вычислений можно с помощью онлайн-калькулятора НОД и НОК.

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Взаимно простые числа — это натуральные числа, у которых только один общий делитель — единица. Их НОД равен 1.

Помимо НОД есть еще и НОК, что расшифровывается, как наименьшее общее кратное и означает наименьшее число, которое делится на каждое из исходных чисел без остатка.

Еще один пример. Рассчитаем НОД для 28 и 64.

Д (64) = 2 * 2 * 2 * 2 * 2 * 2

НОД (28; 64) = 2 * 2 = 4

Ответ: НОД (28; 64) = 4

Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.

Свойства наибольшего общего делителя

У наибольшего общего делителя есть ряд определенных свойств. Опишем их в виде теорем и сразу приведем доказательства.

Важно! Все свойства НОД будем формулировать для положительных целых чисел, при этом будем рассматривать делители только больше нуля.

Свойство 1. Наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и а, то есть НОД (a, b) = НОД (b, a). Перемена мест чисел не влияет на конечный результат.

Доказывать свойство не имеет смысла, так как оно напрямую исходит из самого определения НОД.

Свойство 2. Если а делится на b, то множество общих делителей чисел а и b совпадает со множеством делителей числа b, поэтому НОД (a, b) = b.

Доказательство

Любой общий делитель чисел а и b является делителем каждого из этих чисел, в том числе и числа b. Так как а кратно b, то любой делитель числа b является делителем и числа а, благодаря свойствам делимости. Из этого следует, что любой делитель числа b является общим делителем чисел а и b.

Значит, если а делится на b, то совокупность делителей чисел а и b совпадает с совокупностью делителей одного числа b. А так как наибольшим делителем числа b является само число b, то наибольший общий делитель чисела и b также равен b, то есть НОД (а, b) = b.

В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.

Доказанное свойство наибольшего делителя можно использовать, чтобы найти НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число.

Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.

Доказательство

Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.

Поэтому должны совпадать и наибольшие из этих общих делителей, и равенство НОД (a, b) = НОД (b, c) можно считать справедливым.

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).

Доказательство

Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.

Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.

Способы нахождения наибольшего общего делителя

Найти наибольший общий делитель можно двумя способами. Рассмотрим оба, чтобы при решении задач выбирать самую оптимальную последовательность действий.

1. Разложение на множители

Чтобы найти НОД нескольких чисел, достаточно разложить их на простые множители и перемножить между собой общие множители для всех чисел.

Пример 1. Найти НОД (84, 90).

Ответ: НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Ответ: НОД (15, 28) = 1.

Пример 3. Найти НОД для 24 и 18.

Ответ: НОД (24, 18) = 6

2. Алгоритм Евклида

Способ Евклида помогает найти НОД через последовательное деление. Сначала посмотрим, как работает этот способ с двумя числами, а затем применим его к трем и более.

Алгоритм Евклида заключается в следующем: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем. Использовать метод Евклида можно легко по формуле нахождения наибольшего общего делителя.

Формула НОД: НОД (a, b) = НОД (b, с), где с — остаток от деления a на b.

Пример 1. Найти НОД для 24 и 8.

Так как 24 делится на 8 и 8 тоже делится на 8, значит, 8 — общий делитель этих чисел. Этот делитель является наибольшим, потому что 8 не может делиться ни на какое число, большее его самого. Поэтому: НОД (24, 8) = 8.

В остальных случаях для нахождения наибольшего общего делителя двух чисел нужно соблюдать такой порядок действий:

Пример 2. Найти наибольший общий делитель чисел 140 и 96:

Последний делитель равен 4 — это значит: НОД (140, 96) = 4.

Ответ: НОД (140, 96) = 4

Пошаговое деление можно записать столбиком:

Чтобы найти наибольший общий делитель трех и более чисел, делаем в такой последовательности:

Знакомство с темой наибольшего общего делителя начинается в 5 классе с теории и закрепляется в 6 классе на практике. В этой статье мы узнали все основные определения, свойства и их доказательства, а также как найти НОД.

Источник

Теория чисел

Простые числа

Простым называется натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается. Составным числом называют непростое число, которое еще и не единица.

Проверка на простоту за линию

Проверка на простоту за корень

Разложение на простые множители

Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.

\[11 = 11 = 11^1\] \[100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2\] \[126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1\]

Рассмотрим, например, такую задачу:

Условие: Нужно разбить \(N\) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

\[N= p_1^ \times p_2^ \times \ldots \times p_k^\]

Алгоритм разложения на простые множители

Напишем алгоритм факторизации:

Задание

За сколько работает этот алгоритм?

Решение

Задание

Докажите, что число \(N\) имеет не больше, чем \(O(\log)\) простых множителей в факторизации.

Разные свойства простых чисел*

Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:

Решето Эратосфена

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до \(N\) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

У этого алгоритма можно сразу заметить несколько ускорений.

Асимптотика

Такой код будет работать за \(O(N \log \log N)\) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Каждое из этих слагаемых имеет вид \[\frac<1> <2^j>+ \ldots + \frac<1> <2^— 1> \le \frac<1> <2^j>+ \ldots + \frac<1> <2^j>= 2^j \frac<1> <2^j>= 1\]

Попытка объяснения асимптотики** (для старших классов)

Но вообще-то решето можно сделать и линейным.

Задание

Решите 5 первых задач из этого контеста:

Линейное решето Эратосфена*

Основное утверждение такое:

НОД и НОК

Введем два определения.

Например, * НОД(18, 30) = 6 * НОД(60, 180, 315) = 15 * НОД(1, N) = 1 * НОК(12, 30) = 6 * НОК(1, 2, 3, 4) = 12 * НОК(1, \(N\) ) = \(N\)

Зачем они нужны? Например, они часто возникают в задачах.

Еще пример задачи на применение НОД и НОК:

Решение: Вертолет пересечет по вертикали \((m-1)\) границу. С этим ничего не поделать — каждое считается как новое посещение какого-то квартала. По горизонтали то же самое — \((n-1)\) переход в новую ячейку будет сделан.

Алгоритм Евклида

Осталось придумать, как искать НОД и НОК. Понятно, что их можно искать перебором, но мы хотим хороший быстрый способ.

Из этого равенства сразу следует следующее равенство: \[НОД(a, b) = НОД(a, b \operatorname <\%>a), b > a\]

Это равенство дает идею следующего рекурсивного алгоритма:

\[НОД(a, b) = НОД(b \operatorname <\%>a, a) = НОД(a \operatorname <\%>\, (b \operatorname <\%>a), b \operatorname <\%>a) = \ldots\]

Например: \[НОД(93, 36) = \] \[= НОД(36, 93\space\operatorname<\%>36) = НОД(36, 21) = \] \[= НОД(21, 15) = \] \[= НОД(15, 6) = \] \[= НОД(6, 3) = \] \[= НОД(3, 0) = 3\]

Задание:

Примените алгоритм Евклида и найдите НОД чисел: * 1 и 500000 * 10, 20 * 18, 60 * 55, 34 * 100, 250

По-английски наибольший общий делитель — greatest common divisor. Поэтому вместо НОД будем в коде писать gcd.

А за сколько оно вообще работает?

Задание

Кстати, интересный факт: самыми плохими входными данными для алгоритма Евклида являются числа Фибоначчи. Именно там и достигается логарифм.

Как выразить НОК через НОД

По этой формуле можно легко найти НОК двух чисел через их произведение и НОД. Почему она верна?

Посмотрим на разложения на простые множители чисел a, b, НОК(a, b), НОД(a, b).

\[ a = p_1^\times p_2^\times\ldots\times p_n^ \] \[ b = p_1^\times p_2^\times\ldots\times p_n^ \] \[ ab = p_1^\times p_2^\times\ldots\times p_n^ \]

Из определений НОД и НОК следует, что их факторизации выглядят так: \[ НОД(a, b) = p_1^\times p_2^\times\ldots\times p_n^ \] \[ НОК(a, b) = p_1^\times p_2^\times\ldots\times p_n^ \]

Как посчитать НОД/НОК от более чем 2 чисел

Для того, чтобы искать НОД или НОК у более чем двух чисел, достаточно считать их по цепочке:

С НОК то же самое, только фразу “множество общих делителей” надо заменить на “множество общих кратных”.

Задание

Решите задачи F, G, H, I из этого контеста:

Расширенный алгоритм Евклида*

Очень важным для математики свойством наибольшего общего делителя является следующий факт:

Мы сейчас не только докажем, что решения у таких уравнений существуют, но и приведем быстрый алгоритм нахождения этих решений. Здесь нам вновь пригодится алгоритм Евклида.

Предположим, что у нас есть решение данного уравнения для чисел \(b\) и \(r\) (их наибольший общий делитель, как известно, тоже равен \(d\) ): \[bx_0 + ry_0 = d\]

Это удобно реализовывать рекурсивно:

Действительно, \(116\times(-3) + 44\times8 = 4\)

Задание

Решите задачу J из этого контеста:

Операции по модулю

Выражение \(a \equiv b \pmod m\) означает, что остатки от деления \(a\) на \(m\) и \(b\) на \(m\) равны. Это выражение читается как « \(a\) сравнимо \(b\) по модулю \(m\) ».

Сложение, вычитение и умножение по модулю определяются довольно интуитивно — нужно выполнить соответствующую операцию и взять остаток от деления.

С делением намного сложнее — поделить и взять по модулю не работает. Об этом подробнее поговорим чуть дальше.

Задание

Для умножения (в C++) нужно ещё учитывать следующий факт: при переполнении типа всё ломается (разве что если вы используете в качестве модуля степень двойки).

Зачем нужно считать ответ по модулю

Быстрое возведение в степень

Мы хотим научиться возводить число в большую степень быстро, не просто умножая \(a\) на себя \(b\) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.

Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):

Нужно только после каждой операции делать mod: * \(a^0 \pmod c = 1\) * \(a^ <2k>\pmod c = (a^ \pmod c)^2 \pmod c\) * \(a^ <2k+1>\pmod c = ((a^<2k>\pmod c) \times a) \pmod c\)

Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)

Задание

Решите задачу K из этого контеста:

Задание

Решите как можно больше задач из практического контеста:

Деление по модулю*

Давайте все-таки научимся не только умножать, но и делить по простому модулю. Вот только что это значит?

Утверждение: в кольце остатков по простому модулю \(p\) у каждого остатка (кроме 0) существует ровно один обратный элемент.

Например, обратный к \(2\) по модулю \(5\) это \(3\) ( \(2 \times 3 = 1 \pmod 5\) ))

Задание

Найдите обратный элемент к: * числу \(3\) по модулю \(5\) * числу \(3\) по модулю \(7\) * числу \(1\) по модулю \(7\) * числу \(2\) по модулю \(3\) * числу \(9\) по модулю \(31\)

Есть несколько способов это сделать.

Через малую теорему Ферма

Обобщение У малой теоремы Ферма есть обобщение для составных \(p\) :

Но с этим возникают большие проблемы: посчитать функцию Эйлера сложно. Более того, на предполагаемой невозможности быстро ее посчитать построены некоторые криптографические алгоритм типа RSA. Поэтому быстро делить по составному модулю этим способом не получится.

Через расширенный алгоритм Евклида

Этим способом легко получится делить по любому модулю! Рекомендую.

Давайте найдем корни уравнения

Тогда если взять остаток по модулю \(p\) :

Источник

Делимость чисел в математике с примерами решения

Содержание:

Делимость чисел

Делители натурального числа

18 конфет можно разделить поровну между 3 детьми, дав каждому ребенку по 6. Это же количество конфет, не разрезая их, нельзя разделить поровну между 4 детьми. Если каждому ребенку дать по 4 конфеты, то останется 2. Запишем:

Число 18 делится на число 3 без остатка (еще говорят: 18 делится на 3). Число 3 называют делителем числа 18. Число 18 не делится без остатка на 4 (еще говорят: 18 не делится на 4). Число 4 не является делителем числа 18.

Любое натуральное число, на которое делится данное натуральное число, называют делителем этого числа.

Запишем все натуральные числа, на которые делится число 18 Такими числами являются 1,2,3,6,9, 18. Итак, число 18 имеет 6 делителей: 1,2, 3,6,9 и 18.

Число 1 имеет только один делитель — 1. Любое другое число, например, 23, обязательно имеет по крайней мере два делителя — число 1 и само число (23), причем I — наименьший делитель, само число (23) — наибольший.

Пример:

Найти все делители числа 36.

Решение:

Чтобы найти все делители числа 36, будем делить его на натуральные числа, начиная с 1: 36 : 1 = 36; 36 : 2 = 18; 36 : 3 = 12; 36 : 4 = 9; 36 : 5 = 7 (ост. 1); 36 : 6 = 6; 36 : 7 = 5 (ост. 1); 36 : 8 = 4 (ост. 4) и т. д.

Количество делений можно уменьшить. Найдя один делитель, сразу можем записать еще один, который является частным от деления числа 36 на этот делитель. Делители удобно записать так:

Итак, делителями числа 36 являются: 1, 2, 3,4, 6, 9, 12, 18, 36.

Признаки делимости на 2, 5 и 10

Как известно из изученного в пятом классе, чтобы умножить натуральное число на 10, нужно к записи этого числа дописать справа один нуль, например, 137 • 10 = 1370. Поскольку 10 является делителем числа 1370, то число 1370 делится на 10. В общем, на 10 делятся все числа, запись которых оканчивается цифрой 0.

Число, запись которого не оканчивается цифрой 0, например, 457, на 10 не делится.

Натуральное число, запись которого оканчивается цифрой 0, делится на 10.

Натуральное число, запись которого не оканчивается цифрой 0, не делится на 10.

Это правило называют признаком делимости на 10.

Найдем признак делимости на 5. Для этого разделим на 5 некоторые числа, например, 19, 82, 140, 245, 344, 515, 630, 1027.

Запишем в первый столбик те числа, которые делятся на 5, а во второй — те, которые не делятся на 5.

Какую вы заметили особенность чисел, которые делятся на 5; не делятся на 5?

Натуральное число, запись которого оканчивается цифрой 0 или 5, делится на 5.

Натуральное число, запись которого оканчивается цифрой, отличной от 0 или 5, не делится на 5.

Числа, которые делятся на 2, называют четными, а числа, которые на 2 не делятся, — нечетными. Например, 24 — число четное, поскольку оно делится на 2, а число 25 — нечетное, поскольку оно не делится на 2.

Однозначные числа 0, 2,4, 6, 8 являются четными, а числа 1, 3, 5, 7, 9 — нечетными.

Запись каждого числа, которое делится на 2, оканчивается однозначным четным числом. Если запись числа оканчивается однозначным нечетным числом, то оно не делится на 2.

Натуральное число, запись которого оканчивается однозначным четным числом, делится на 2.

Натуральное число, запись которого оканчивается однозначным нечетным числом, не делится на 2.

Для тех, кто хочет знать больше

Зная последнюю цифру в записи натурального числа, можно установить, делится ли оно на 2, 5 или 10.

Зная две последние цифры в записи натурального числа, можно ответить на вопрос, делится ли число на 4, на 25. А именно:

Натуральное число делится на 4, если число, образованное двумя его последними цифрами, делится на 4.

Натуральное число не делится на 4, если число, образованное двумя его последними цифрами, не делится на 4

Натуральное число делится на 25. если число, образованное двумя его последними цифрами, делится на 25.

Натуральное число не делится на 25, если число, образованное двумя его последними цифрами, не делится на 25.

Признаки делимости на 9 и на 3

Найдем признак делимости на 9. Для этого разделим на 9 некоторые числа, например, 288, 361,441, 814. 917, 8919.

Запишем в первый столбик те числа, которые делятся на 9, а во второй — те, которые не делятся на 9.

Какую вы заметили особенность чисел которые делятся на 9; не делятся на 9?

Воспользуйтесь такой подсказкой: найдите сумму цифр каждого из этих чисел.

Какое свойство имеет сумма цифр тех чисел, которые делятся на 9?

Какое свойство имеет сумма цифр тех чисел, которые не делятся на 9?

Натуральное число делится на 9, если сумма его цифр делится на 9.

Натуральное число не делится на 9, если сумма его цифр не делится на 9.

Признак делимости на 3 аналогичен признаку делимости на 9.

Натуральное число делится на 3, если сумма его цифр делится на 3.

Натуральное число не делится на 3, если сумма его цифр не делится на 3.

Для тех. кто хочет знать больше

Признак делимости на 9, например, для числа 468, следует из таких преобразований:

Число — 9 делится на 9. Сумма 4+6+8 является суммой цифр числа 468. Если она делится на 9, то и число 468 делится на 9. Так как сумма 4 + 6 + 8 = 18 делится на 9, то и число 468 делится на 9.

Простые и составные числа

Возьмем несколько натуральных чисел и найдем все их делители.

Мы видим, что числа имеют разное количество делителей. Число 1 имеет только один делитель — само это число. Числа 2, 3, 17 имеют по два делителя: 1 и само себя. Числа 4, 12,21 и 30 имеют больше, чем два делителя.

Натуральное число называют простым, если оно имеет только два разных делителя: единицу и само это число. Число, имеющее более двух делителей, называют составным.

Итак, числа 2, 3, 17 — простые, а числа 4, 12, 21, 30 — составные. Число 1 не является ни простым, ни составным числом.

Если число имеет делитель, отличный от I и самого себя, то это число имеет более двух делителей и поэтому является составным. Число 12 475 — составное, так как имеет среди делителей, например, число 5.

Наименьшим простым числом является число 2. Наибольшего простого числа не существует. Все простые числа, кроме числа 2, являются нечетными.

Таблица простых чисел, которые не превышают 1000, находится на форзаце учебника.

Интересные рассказы

История математики знает имена ученых, которые приложили немало усилий для составления таблиц простых чисел. Первые такие попытки были сделаны еще в Древней Греции.

Если «высеять» все простые числа, не превышающие 30, то получим:

2, 3, 5, 7, II, 13, 17, 19, 23, 29 — первые 10 простых чисел.

Эратосфенов метод «высевания» простых чисел называют еще «решетом Эратосфена». Это связано с тем, что древние греки писали на папирусе или табличках, покрытых воском, и числа не вычеркивали, а выкалывали иголкой, после чего папирус или табличка напоминали решето.

В 1603 году итальянский математик Пьетро Катальди опубликовал в Болонье первую известную нам таблицу простых чисел меньше 750. Позже математики продвигались все дальше в глубь натурального ряда чисел, открывая все новые и новые простые числа.

Уже в 1770 голу немецкий математик Иоанн Генрих Ламберт (1728- 1777) опубликовал таблицу наименьших делителей всех чисел меньше 102 000, которые не делятся на 2, 3 и 5. Это была огромная работа. Не зря, призывая ученых продолжить составление таблицы, Ламберт гарантировал бессмертие тому, кто получит таблицу делителей до 1 000 000.

В середине XIX века в прессе появились сообщения, которые казались совершенно невероятными: Венская академия наук получила рукопись пражского математика Якуба Филиппа Кулика, содержащую таблицу деятелей чисел, не делящихся 2, 3 и 5, которую ученый расширил до 100 миллионов.

Редактор таблиц простых чисел Лемер посетил Вену и убедился, что в библиотеке академии хранится семь больших томов рукописных таблиц «Большой канон делителей всех чисел, которые не делятся на 2, 3 и 5, и простых чисел между ними до 100 330 201 Якуба Филиппа Кулика, публичного ординарного профессора высшей математики Пражского университета».

Якуб Филипп Кулик (1793 1863) родился во Львове. Окончив местную гимназию, он изучал философию, право и математику во Львовском университете, ас 1814 гола преподавал математику в лицее. С 1826 года Кулик стал профессором высшей математики Пражского университета. Много сил ученый отдал развитию культуры, науки и образования в родном крае. Он подарил много книг галицким гимназиям и Львовскому университету. Кулик является автором многих научных работ, но в историю математики он вошел как непревзойденный вычислитель и составитель математических таблиц.

Разложение натуральных чисел на простые множители

Составное число 24 можно записать как произведение двух множителей, например, 24 = 6•4. Говорят, что число 24 разложили на два множителя — 6 и 4. Числа 6 и 4 тоже можно разложить на множители: 6 = 3•2; 4 = 2•2. Теперь число 24 можно записать так: 24 = 3 • 2 • 2 • 2. В произведении 3 • 2 • 2 • 2 все множители являются простыми числами. Итак, число 24 разложили на простые множители.

Разложить число на простые множители означает записать его в виде произведения простых чисел. Любое составное число можно разложить на простые множители. Например:

Раскладывая числа на простые множители, надо найти простые делители этого числа. При этом можно использовать признаки делимости чисел. Чтобы разложить на множители большие числа, пользуются специальной схемой.

Пусть надо разложить на простые множители число 630.

Записываем это число и проводим справа вертикальную черту Наименьшим простым делителем этого числа является 2; записываем 2 справа or черты. Делим 630 на 2 и записываем частное 315 слева от черты под числом 630. Находим теперь наименьший простой делитель числа 315. Им является число 3, записываем его справа от черты. Делим 315 на 3, частное 105 записываем слева. Делим 105 на 3, получаем 35; 35 делим на 5, получаем 7. Число 7 простое, разделив его на 7, получим I. Разложение закончено.

Итак,

Пример:

Найти все делители числа 126.

Решение:

Разложим число 126 на простые множители:

Делителями числа 126 являются: 1, простые числа 2, 3, 7 в полученном разложении и всевозможные произведения чисел 2, 3, 3, 7, то есть:

И так, делителями числа 126 являются:

Запишем все делители в порядке их возрастания:

Интересные рассказы

Расположение простых чисел

Утверждение о том, что каждое отличное от 1 натуральное число можно записать в виде произведения простых множителей и притом единственным способом, если не принимать во внимание порядок расположения сомножителей, является так называемой основной теоремой арифметики — одной из древнейших математических наук (в переводе с греческого «арифметика» — «искусство чисел»).

В соответствии с основной теоремой арифметики простые числа являются как бы кирпичами, из которых «строятся» натуральные числа. Этим и объясняется внимание к простым числам со стороны математиков всех времен. Еще древнегреческий математик Эвклид (ок. 365 ок. 300 г. до н. э.) доказал, что простых чисел есть бесконечно много, поэтому наибольшего простого числа не существует. Но еще до сих пор не изучены закономерности расположения простых чисел в натуральном ряду.

Талантливые математики многих стран стремились найти закон расположения простых чисел.

О свойствах простых чисел выдвинуто много интересных гипотез. Среди них самой интересной является гипотеза члена Петербургской академии наук Кристиана Гольдбаха (1690 1764), сформулированная так: любое натуральное число больше 5 является суммой трёх простых чисел

Свойства простых чисел можно наглядно представить так:

Перед нами откроется следующая картина.

Наибольший общий делитель

Выпишите все делители чисел 18 и 24 и подчеркните их общие делители

Общими делителями (они подчеркнуты) чисел 18 и 24 являются числа 1, 2, 3, 6, наибольшим из них является 6. Число 6 является наибольшим натуральным числом, на которое делятся и 18, и 24.

Наибольшее натуральное число, на которое делится каждое из данных чисел, называют наибольшим общим делителем этих чисел.

Итак, наибольшим общим делителем чисел 18 и 24 являегся число 6. Сокращенно это записывают так: НОД( 18; 24) 6.

В рассмотренном примере мы легко нашли наибольший общий делитель чисел, записав все делители каждого из них. Если числа большие и имеют много делителей, то нахождение наибольшего общего делителя этим способом является достаточно сложным.

Рассмотрим еще один способ нахождения наибольшего общего делителя, взяв числа 210 и 294. Разложим каждое из этих чисел на простые множители:

Подчеркнем все общие простые множители в разложении данных чисел: 2, 3, 7. Числа 210 и 294 делятся на каждое из чисел 2, 3, 7 и на их произведение: 2•3•7 =42. Число 42 является наибольшим общим делителем чисел 210 и 294:

Назовите последовательность шагов при нахождении НОД двух чисел.

Для нахождения наибольшего общего делителя двух чисел можно разложить эти числа на простые множители и найти произведение их общих множителей.

По такому правилу можно находить наибольший общий делитель трёх и более чисел. Найдем, например, наибольший общий делитель чисел 45, 75 и 90. Разложим эти числа на простые множители и подчеркнем общие для всех чисел множители:

Итак,

Если среди данных чисел есть число, на которое делятся другие из данных чисел, то это число является наибольшим обидим делителем данных чисел. Например:

Два числа, наибольший общий делитель которых равен 1, называют взаимно простыми числами. Например, числа 16 и 27 являются взаимно простыми, так как их наибольшим общим делителем является 1.

Взаимно простые числа вообще имеют только один общий делитель — число 1. Поэтому, если два числа имеют общий делитель, отличный от 1, то они не взаимно простые. Например, числа 18 и 45 не являются взаимно простыми, так как имеют общий делитель 3.

Пример:

Какое наибольшее количество одинаковых букетов можно составить из 24 васильков и 32 ромашек, использовав все цветы?

Решение:

Из данных цветов можно, например, составить 2 букета. в каждом из которых будет 12 васильков и 16 ромашек. Нельзя составить три букета, так как 32 ромашки нельзя разделить на 3 одинаковые части. Можно составить четыре одинаковых букета, так как и 24 василька, и 32 ромашки можно разделить на 4 одинаковые части. Очевидно, что для решения задачи нужно найти наибольшее число, на которое можно разделить 24 василька и 32 ромашки, то есть найти наибольший общий делитель чисел 24 и 32. Поскольку НОД(24; 32) = 8, то можно составить самое большее 8 одинаковых букетов. Каждый такой букет будет состоять из 24 : 8 = 3 васильков и 32 : 8 = 4 ромашек.

Кратные натурального числа. Наименьшее общее кратное

Числа 36, 72, 180 делятся на 18. Говорят, что числа 36, 72, 180 кратны числу 18.

Любое натуральное число, которое делится на данное натуральное число, называют кратным данного числа.

Все числа, кратные числу 18, можно получить, умножая число 18 последовательно на числа 1,2, 3,4, 5.

18, 36, 54, 72, 90. — числа, кратные 18.

Каждое натуральное число имеет бесконечно много чисел, кратных ему, наименьшим из которых является само это число.

Запишите числа, кратные 9. и числа, кратные 12, и подчеркните их общие кратные.

Наименьшим общим кратным двух натуральных чисел называют наименьшее натуральное число, которое делится на каждое изданных чисел.

То, что наименьшим общим кратным чисел 9 и 12 является число 36, сокращенно записывают так: НОК(9; 12) = 36.

Разложим числа 9, 12 и их наименьшее общее кратное 36 на простые множители:

Мы видим, что разложение числа 36 можно получить, если разложение числа 9 умножить на 2 • 2. Числа 2 и 2 — это такие множители из разложения числа 12, которых нет в разложении числа 9

Назовите последовательность шагов при нахождении НОК двух чисел.

Чтобы найти наименьшее общее кратное двух чисел, можно каждое из них разложить на простые множители и разложение одного из чисел умножить на те множители другого числа, которых нет в разложении первого.

Найдем наименьшее общее кратное чисел 90 и 210.

Если одно из чисел делится на другое, то большее из них является наименьшим общим кратным этих чисел. Например, НОК(21; 63) = 63.

Наименьшим общим кратным двух взаимно простых чисел являегся произведение этих чисел. Например, НОК(8; 9) = 72.

Наименьшее общее кратное можно найти не только для двух, но и для трех и более чисел.

Например, для чисел 12, 18, 24 имеем:

Пример:

Найти наименьшее четырехзначное число, кратное 27.

Решение:

1000 — наименьшее четырехзначное число. Разделим его на 27: 1000: 27 = 37 (ост. 1).

27 • 38 = 1026 — наименьшее четырехзначное число, кратное 27.

Пример:

Шаг отца равен 72 см, а шаг сына — 54 см. Найти наименьшее расстояние, которое нужно пройти как отцу, так и сыну, чтобы каждый из них сделал при этом целое число шагов.

Решение:

Искомое расстояние в сантиметрах должно выражаться таким наименьшим числом, которое делится на 72 и на 54. Таким числом являемся наименьшее общее кратное этих чисел. Найдем НОК(54; 72):

Итак, искомое расстояние равно 216 см. На таком расстоянии отец сделает 216 : 72 = 3 шага, а сын — 216 : 54 = 4 шага.

Пример:

Найти наименьшее общее кратное чисел 15 и 12.

Решение:

Находим кратные большего из чисел и проверяем, делятся ли они на меньшее число: 15 не делится на 12; 15 • 2 = 30 — не делится на 12; 15 • 3 = 45 не делится на 12; 15 • 4 = 60 — делится на 12. Итак, НОК( 15; 12) = 60.

Памятка:

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Источник