Простые множители что это

Разложение чисел на простые множители, способы и примеры разложения.

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

Навигация по странице.

Что значит разложить число на простые множители?

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

А что же значит разложить число на простые множители?

Возникает следующий вопрос: «А какие вообще числа можно разложить на простые множители»?

Но все ли целые числа, превосходящие единицу, раскладываются на простые множители?

Каноническое разложение числа на простые множители

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

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

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

Заметим, что в общем случае для разложения на простые множители числа a нам потребуется таблица простых чисел до числа, не меньшего, чем . К этой таблице нам придется обращаться на каждом шаге, так что ее нужно иметь под рукой. Например, для разложения на простые множители числа 95 нам будет достаточно таблицы простых чисел до 10 (так как 10 больше, чем ). А для разложения числа 846 653 уже будет нужна таблица простых чисел до 1 000 (так как 1 000 больше, чем ).

Теперь мы обладаем достаточными сведениями, чтобы записать алгоритм разложения числа на простые множители. Алгоритм разложения числа a таков:

Осталось лишь рассмотреть несколько примеров применения полученного алгоритма для разложения чисел на простые множители.

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

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

Источник

Разложение числа на множители онлайн

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

Что такое разложение числа на множители?

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

Простым числом называют натуральное число , делящееся только на себя и на единицу. Составным числом называют число, имеющее больше двух различных делителей (любое натуральное число не равное имеет как минимум два делителя: и ). Например, числа – простые, а числа – составные.

Как разложить число на множители?

В школе на уроках математики разложение числа на множители обычно записывают столбиком в две колонки. Делается это так: в левую колонку выписываем исходное число, затем

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

Чтобы лучше понять алгоритм, разберём несколько примеров.

Решение. Записываем число 84 в левую колонку:

Берём первое простое число — два и проверяем, делится ли 84 на 2. Так как 84 оканчивается на 4, а 4 делится на 2, то и 84 делится на 2 по признаку делимости. Записываем 2 в правую колонку. 84:2 = 42, число 42 записываем в левую колонку. Получили вот что:

Теперь работаем уже с числом 42. Число 42 делится на 2, поэтому записываем 2 в правую колонку, 42:2 = 21, число 21 записываем в левую колонку.

Число 21 на 2 не делится, поэтому проверяем его делимость на следующее простое число — 3. Число 21 делится на 3, 21:3 = 7. Записали 3 в правую колонку, 7 — в левую. Получили

Число 7 — простое число, поэтому в правой колонке записываем 7, в левую пишем 1. В итоге получили:

Всё, число разложено!

В результате в правой колонке оказались записаны все простые множители числа 84. То есть 84=2∙2∙3∙7.

О калькуляторе

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

Источник

Теория чисел

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

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

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

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

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

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

\[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\) :

Источник

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

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

Термины и понятия

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

Из слова «множители» можно понять, что в превращении используется умножение. Зная, как разложить полином на простые числа, можно быстро решать задачи на действия с корнями и сложными дробями. Например, выражение (3*h*y + 9*y — 8*h — 24) * (3*h — 8) после упрощения примет вид: h + 3 — и быстро решается в уме.

В математике все алгебраические выражения могут быть:

Числа часто записывают в так называемом стандартном виде. Например, 296,8 = 2,968 * 102. То есть используется формула приведения: a * 10r, где 1≤а Простое разложение

На уроках математики ученикам предлагают разложить на простые множители числа с помощью столбика (двух колонок). Делается это по следующему алгоритму. Исходное число проверяют на возможность деления без остатка на два. Если делится, то рисуют две колонки, в правую вписывают двойку, а в левую число, получившееся после деления на него исходного. В обратном случае вместо двойки используют цифру три. Далее действия повторяют для числа, находящегося уже в правой колонке. Выполняют деление до тех пор, пока в левой колонке не останется единица. Например, число 1176 можно разложить следующим образом:

1176 | 2 (1176 / 2 = 588).

588 | 2 (588 / 2 = 294).

294 | 2 (294 / 2 = 147).

1176 = 2 * 2 * 2 * 3 * 7 * 7 = 23 * 3 * 72.

Для того чтобы понять алгоритм, лучше рассмотреть ещё несколько интересных примеров:

Используя метод, можно представить любое число как произведение простых множителей, но с условием, что изначально оно будет кратным двум или трём. В ином же случае простые множители подобрать не получится, как, например, для числа 247, которое можно заменить произведением чисел 13 и 19.

Вынесение коэффициента

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

Чтобы выделить общий множитель, следует выполнить:

Например, пусть дано выражение: 3у2 — 3y + 6 r*y. Согласно правилу, необходимо найти число, на которое без остатка можно разделить каждый из трёх коэффициентов многочлена. Для рассматриваемого примера это будет цифра 3.

Затем определить буквенный множитель, имеющийся в каждом члене выражения. Найденную цифру и повторяющееся неизвестное с наименьшей степенью записать за скобкой. Теперь нужно каждый одночлен разделить на вынесенное значение, а полученный результат записать в скобках: 3y * (y — 1 + 2r). Для проверки правильности действий нужно просто раскрыть скобки путём умножения каждого члена на вынесенный множитель.

Формулы умножения

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

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

Метод группировки

Пожалуй, самый распространённый способ разложения на множители. Его удобно применять для упрощения квадратных уравнений без поиска корней. Разложение этим методом выполняют в следующей последовательности действий:

Выполнять группировку можно по-разному, но в итоге обязательно должен остаться общий многочлен. Например, выражение 48 * h * e 2 + 32 * h * q — 15 * e 2 — 10 * q2 возможно решить двумя способами.

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

Выделение квадрата

По сути, выделение общего квадрата соответствует преобразованию, при котором трёхчлен представляют в виде (k + e)2 или (k — e)2. Метод используется для решения биквадратных уравнений. Для выделения полного квадрата при разложении многочлена на множители применяют две формулы:

Например, нужно упростить дробь: (k4 + 4 * e4) / (k4 + 2 * e2 + 2 * k * e). Необходимо разложить числитель, используя формулы для полного квадрата: (k4 + 4 * e4) = (k4 + 4 * e2 * k2 + 4 * e 4). Значит, если отнять от многочлена 4 * k2 * e2, то получится уравнение: (k2 + 2 * e2) * 2 − 4 * k2 * e2. Используя формулу умножения квадратов, верно будет записать: (k2 + 2 e 2 − 2 * k * e) * (k2 + 2 e 2 + 2 * k * e).

Заменив полученным выражением числитель, можно будет его часть взаимно сократить со знаменателем. В итоге получится простое выражение: h2 + 2 * e2 − 2 * h * e.

Неприводимые множители

Решая различные задачи, можно столкнуться со сложными выражениями, которые, как кажется, разложить нельзя. Например, (2 * p2 — 5 * p — 3)/(3 * p — 9). В числителе дроби находится квадратный трёхчлен, который на самом деле можно разложить. Для того чтобы его можно было упростить, используется формула: ar2 + br + p = a (r — r1) * (r — r2), где r1 и r2 корни выражения.

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

Теперь вместо числителя нужно подставить полученное разложение: (2*p2 — 5*p — 3)/(3*p — 9) = 2*(p — 3) * (p + ½)/3 * (p — 3) = (2 *p + 1)/3.

Использование онлайн-калькуляторов

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

Расчёт обычно занимает менее 30 секунд. Приложений для упрощений уравнений достаточно много. Написаны они на Паскале или javascript. Появление ошибки при вычислении невозможно. Нередко на этих сайтах ещё и содержится информация о способах упрощения полиномов.

Для того чтобы получить ответ, необходимо будет с помощью браузера зайти на сайт онлайн-калькулятора и заполнить предлагаемые им поля. После того как упрощаемое выражение будет вписано, следует нажать кнопку «Рассчитать» или «Упростить выражение» и получить ответ с пошаговым решением.

Источник