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

Основная теорема арифметики

Начало последовательности простых чисел:

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,…

С ростом натуральных чисел в ряду простые числа встречаются всё реже:

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

Основная теорема арифметики

Процесс разложения числа на простые сомножители называют факторизацией.

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

$$ n = p_1^{a_1} p_2^{a_2} … p_m^{a_m} $$

где $a_i \ge 1$ - степени каждого из простых сомножителей.

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

Входные данные: число $n \gt 1$, список простых чисел $P = \{p_i \}$ в диапазоне $2 \le p_i \le \sqrt n$

Шаг 1. В списке P найти минимальное простое число $p_k$ – делитель n, $n ⋮ p_k$

Шаг 2. Найти частное $n_k = n/p_k$.

Шаг 3. Если $n_k = 1$, перейти на шаг 4; если нет, $n = n_k$, перейти на шаг 1.

Шаг 4. Конец работы.

Данный алгоритм называется «перебором простых делителей». Он относится к «наивным» и годится для небольших чисел $n \le 2^16$. Поскольку всё современное шифрование данных построено на сложности факторизации, существуют десятки хитрых алгоритмов, ускоряющих поиск сомножителей.

Например: факторизовать число 140400

$140400 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 13 = 2^4 \cdot 3^3 \cdot 5^2 \cdot 13$

70200

35100

17550

8775

2925

975

325

65

13

1

НОД и НОК

Свойства НОД

1. НОД(a,b) = НОД(b,a)

2. НОД(-a,b) = НОД(a,b)

3. НОД(a,0) = |a|

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

$$ a = p_1^{a_1} p_2^{a_2} … p_k^{a_k}, b = p_1^{b_1} p_2^{b_2} … p_m^{b_m} $$

Пусть для определённости $k \ge m$.

Тогда для «сборки» НОД нужно выбирать каждый простой сомножитель с минимальной степенью (включая 0-ю степень):

$$ НОД(a,b) = p_1^{min_{a_1,b_1}} p_2^{min_{a_2,b_2}} … p_k^{min_{a_3 b_3}} $$

А для «сборки» НОК нужно выбирать максимальные степени:

$$ НОK(a,b) = p_1^{max⁡_{a_1,b_1}} p_2^{max_{a_2,b_2}} … p_k^{max_{a_3 b_3}} $$

Например: a = 1188, b = 1176

$1188 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 11 = 2^2 \cdot 3^3 \cdot 11$

594

297

99

33

11

1

НОД (a,b) = $ 2^2 \cdot 3 = 12,$

1176 = $2 \cdot 2 \cdot 2 \cdot 3 \cdot 7 \cdot 7 = 2^3 \cdot 3 \cdot 7^2$

588

294

147

49

7

1

НОК (a,b) =$ 2^3 \cdot 3^3 \cdot 7^2 \cdot 11 = 116424$

Заметим, что если рассматривать все сомножители каждого из чисел как множества:

A = {2;2;3;3;3;11}, B = {2;2;2;3;7;7}

то для НОД нужно найти пересечение $A \cap B$ и перемножить его элементы:

$$ A \cap B = {2;2;3}, НОД(a,b) = 12$$

а для НОК нужно найти объединение $A \cup B$ и перемножить его элементы:

$ A \cup B = {2;2;2;3;3;3;7;11}, НОК(a,b) = 116424 $

Примеры

Пример 1. Найдите НОД и НОК данных пар чисел, сделайте проверку:

а) 81 и 51

$$ 81 = 3^4, 51 = 3 \cdot 17 $$

$$ НОД(81;51) = 3, НОК(81;51) = 3^4 \cdot 17 = 1377 $$

$$ ab = 81 \cdot 51 = 4131, НОД \cdot НОК = 3 \cdot 1377 = 4131 $$

ab = НОД $\cdot$ НОК - расчёты правильные

б) 312 и 132

$$ 312 = 2^3 \cdot 3 \cdot 13, 132 = 2^2 \cdot 3 \cdot 11 $$

$$ НОД(312;132) = 2^2 \cdot 3 = 12, НОК(312;132) = 2^3 \cdot 3 \cdot 11 \cdot 13 = 3432 $$

$$ ab = 312 \cdot 132 = 41184, НОД \cdot НОК = 12 \cdot 3432 = 41184 $$

ab = НОД $\cdot$ НОК - расчёты правильные

в) 718 и 72

$$ 718 = 2 \cdot 359, 72 = 2^3 \cdot 3^2 $$

$$ НОД(718;72) = 2, НОК(718;72) = 359 \cdot 2^3 \cdot 3^2 = 25848 $$

$$ ab = 718 \cdot 72 = 51696, НОД \cdot НОК = 2 \cdot 25848 = 51696 $$

ab = НОД $\cdot$ НОК - расчёты правильные

г) 99 и 272

$$ 99 = 3^2 \cdot 11, 272 = 2^4 \cdot 17 $$

$$ НОД(99;272) = 1, НОК(99;272) = 3^2 \cdot 11 \cdot 2^4 \cdot 17 = 26928 $$

ab = 99 $\cdot$ 272 = 26928, НОД $\cdot$ НОК = 1 $\cdot$ 26928 = 26928

ab = НОД $\cdot$ НОК - расчёты правильные

Пример 2. Когда солдаты строились в колонну по 4, по 5 или по 6, каждый раз один оставался лишним, а когда построились в колонну по 7, лишних не осталось. Сколько было солдат (укажите наименьшее из возможных решений)?

Число солдат при делении на наименьшее общее кратное НОК(4;5;6) даст в остатке 1.

$$ НОК(4;5;6) = 2^2 \cdot 5 \cdot 3 = 60 $$

Получаем:

$${\left\{ \begin{array}{c} n = 60m+1 \\ \frac{n}{7} = k \end{array} \right.} \Rightarrow 60m+1 = 7k \Rightarrow \frac{60m+1}{7} = k$$

Наименьшие m и k: ${\left\{ \begin{array}{c} m = 5 \\ k = 43 \end{array} \right.} \Rightarrow n = 301$

Ответ: 301 человек

Пример 3. Числа 100 и 90 разделили на одно и то же число. В первом случае получили в остатке 4, а в другом – 18. Какое число было делителем?

Пусть делитель равен n. По условию:

$$ {\left\{ \begin{array}{c} \frac{100-4}{n} = m \\ \frac{90-18}{n} = k \end{array} \right.} \Rightarrow {\left\{ \begin{array}{c} \frac{96}{n} = m \\ \frac{72}{n} = k \end{array} \right.} $$

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

$$ 96 = 2^5 \cdot 3, 72 = 2^3 \cdot 3^2 $$

$$ НОД(96;72) = 2^3 \cdot 3 = 24 $$

Другие общие делители: 2;4;8;6;12

По условию один из остатков 18, значит, делитель $n \gt 18$.

Остаётся одно решение: n = 24.

Ответ: 24

Пример 4. Космический пират Шутзем разработал отличный план не совсем честного присвоения золотых запасов корпорации Думзем. Забрать золото несложно, но на обратном пути его наверняка будет поджидать конкурент Киллзем со своими головорезами. Их семеро, они отберут у него добычу и поделят между собой. Нужно было что-то придумать.

По роду деятельности Шутзем неплохо разбирался в навигации, криптографии и знал толк в алгебре, и у него появилась идея…

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

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

Снова пришлось пожертвовать одним из пиратов.

Так продолжалось до тех пор, пока в живых не остался только Киллзем.

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

Сколько монет забрал у корпорации Шутзем, чтобы осуществить свой коварный план, если известно, что их было чуть больше пяти тысяч?

Общее количество монет делится на 2,3…7 с остатком 1.

Найдём НОД:

$$ НОД(2;3;4;5;6;7) = 4 \cdot 5 \cdot 6 \cdot 7 = 840 $$

Количество монет, которые будут делиться между 2,3,…7 пиратами нацело:

N = 840k

Количество монет, которые при дележе всегда будут давать в остатке 1:

N = 840k+1

По условию:

$$ 5000 \le 840k + 1 ≤ 5300 \Rightarrow k = 6 $$

N = 840 $\cdot$ 6+1 = 5041

Ответ: 5041 монета