Применение разложения на простые множители
Разложение на простые множители превращает число в произведение простых степеней. По такому представлению удобно находить все делители, количество делителей, наименьшее общее кратное, наибольший общий делитель и проверять взаимную простоту чисел.
Зачем раскладывать число на простые множители
Основная теорема арифметики утверждает: каждое натуральное число, большее 1, единственным образом представляется в виде произведения простых чисел, если не учитывать порядок множителей. Например, \(60=2\cdot2\cdot3\cdot5=2^2\cdot3\cdot5\).
Разложение натурального числа на простые множители — это запись числа в виде произведения простых чисел или их степеней. Число 1 простым множителем не является: \(1\) не раскладывают.
Обычно начинают с наименьшего возможного простого делителя: \(2\), затем проверяют \(3\), \(5\), \(7\) и так далее. Деление продолжают, пока частное не станет равным 1. Если число заканчивается на чётную цифру, оно делится на 2; признаки делимости помогают быстро находить следующие множители. Например, для 180: \(180=2\cdot90=2^2\cdot45=2^2\cdot3^2\cdot5\).
В разложении \(n=2^3\cdot3^2\cdot7\) число 2 встречается три раза, число 3 — два раза, а число 7 — один раз. Показатели степеней называют показателями простых множителей.
Делители числа по его разложению
Если \(n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\), то любой положительный делитель числа \(n\) составляется выбором степени каждого простого множителя: от нулевой до максимальной. Нулевая степень даёт множитель 1, поэтому она обязательно учитывается.
Например, для \(72=2^3\cdot3^2\) делитель имеет вид \(2^a3^b\), где \(a\in\{0,1,2,3\}\) и \(b\in\{0,1,2\}\). Чтобы получить все делители, перебирают эти значения и не забывают числа 1 и само число 72.
Эта формула даёт количество положительных делителей. Для \(72=2^3\cdot3^2\) получаем \(\tau(72)=(3+1)(2+1)=12\). Если в условии требуется количество делителей, сначала нужно привести число к простому разложению, а затем увеличить каждый показатель на 1.
Делители натурального числа удобно объединять в пары: если \(d\) делит \(n\), то вместе с ним есть делитель \(n/d\). Например, для 36 пары таковы: \((1,36)\), \((2,18)\), \((3,12)\), \((4,9)\), \((6,6)\). Это помогает не пропустить или не повторить делители.
Сколько положительных делителей имеет число \(84=2^2\cdot3\cdot7\)?
НОД, НОК и взаимная простота
Разложение особенно удобно для нахождения взаимно простых чисел, количества делителей и общих кратных. Для двух чисел выписывают простые множители и сравнивают показатели при каждом простом числе.
Чтобы найти НОД, берут общие простые множители с наименьшими показателями. Чтобы найти НОК, берут все простые множители, встречающиеся хотя бы в одном числе, с наибольшими показателями.
Если общих простых множителей нет, то НОД равен 1, а числа называются взаимно простыми. Важно: взаимная простота не означает, что оба числа простые. Например, 8 и 15 взаимно просты, хотя оба составные.
Для кратных чисел действует простой критерий: \(a\) кратно \(b\), если существует натуральное или целое число \(q\), такое что \(a=bq\). В разложении это означает, что каждый простой множитель \(b\) присутствует в \(a\) с не меньшим показателем.
Разобранный пример экзаменационного типа
Найдите наименьшее натуральное число, которое делится на 18 и 40, но не делится на 12.
Сначала найдём НОК чисел 18 и 40. Затем проверим дополнительное условие. Это типичный алгоритм задач на кратные и общие делители.
Следовательно, такого натурального числа не существует. Главное наблюдение: если НОК уже делится на запрещённое число, то все его кратные тоже будут на него делиться.
Если требуется число, кратное \(a\) и \(b\), но не кратное \(c\), сначала найдите \(L=\operatorname{НОК}(a,b)\). Если \(c\mid L\), то \(c\) делит любое число \(Lk\), и условие невыполнимо.
Ещё один полезный приём: произведение и НОД
Для натуральных чисел \(a\) и \(b\) произведение связано с НОД и НОК. Это позволяет быстро находить один показатель, если известны два других.
Например, если \(a=12\), \(b=18\), то \(\operatorname{НОД}(a,b)=6\), а \(\operatorname{НОК}(a,b)=36\). Проверка: \(12\cdot18=216\) и \(6\cdot36=216\).
1. Считают простым множителем число 1. Это неверно. 2. В формуле количества делителей используют показатели без прибавления единицы. 3. Для НОД берут наибольшие показатели, хотя нужно брать наименьшие; для НОК — наоборот. 4. При проверке взаимной простоты смотрят только на один общий множитель и забывают остальные. 5. Путают «делится на» и «кратно»: запись \(b\mid a\) означает, что \(a\) делится на \(b\).
Алгоритм решения задач
- Разложите все данные числа на простые множители.
- Соберите одинаковые простые множители и запишите степени.
- Для делителей перебирайте показатели от 0 до исходного показателя.
- Для НОД выбирайте минимальные показатели, для НОК — максимальные.
- Для взаимной простоты проверьте отсутствие общих простых множителей.
- После вычислений выполните обратную проверку: умножьте найденные множители или проверьте делимость.
В задачах, связанных с признаками делимости на 6 и 12, разложение помогает увидеть структуру числа, но быстрый признак иногда короче. При работе с большими степенями полезно также помнить правила нулевой степени: \(p^0=1\) для любого ненулевого \(p\).
Проверь себя
Главное
- Разложение на простые множители единственно и записывается как произведение простых степеней.
- Делитель получается выбором показателей от 0 до соответствующих показателей исходного числа.
- Количество делителей числа \(p_1^{\alpha_1}\cdots p_k^{\alpha_k}\) равно \((\alpha_1+1)\cdots(\alpha_k+1)\).
- Для НОД берут минимальные показатели, для НОК — максимальные.
- Числа взаимно просты тогда и только тогда, когда их НОД равен 1.
- Если НОК нескольких чисел делится на некоторое число, то любое их общее кратное также делится на него.