Метка: простые числа

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

Теорема. Любое натуральное число больше единицы может быть разложено в виде простых множителей и это разложение единственно (если не учитывать порядок множителей).

Докажем существование такого разложения и то, что оно единственно.

Существование. Пусть $n \in N, n > 1$ и мы имеем два варианта.Если $n$ простое, и тогда разложение уже получено, либо $n$ составное, а значит может быть представлено в виде $n=p_{0}a_{0}$, где $p_0$ — наименьший делитель $n$. Допустим $a_{0}>1$, а значит у нас снова два варианта. Либо $a_{0}$ — простое, либо оно составное и может быть представлено как $a_{0}=p_{1}a_{1}$, где $p_1$ — наименьший делитель $a_{0}$. Таким образом мы дойдем до $a_{m-1}=p_{m}a_{m}$, где $a_{m}=1$. Тогда $n=p_{0}p_{1}p_{2}\ldots p_{m}$, где $p_{i}, i=\overline{0, m}$ является простым по лемме (1) о простоте наименьшего делителя.

Единственность. Пусть существуют два разложения числа $n\in N, n > 1$ на простые множители. Тогда $p_{1}p_{2}\ldots p_{n}=q_{1}q_{2}\ldots q_{m}$. Так как $p_{1}p_{2}\ldots p_{n}$ разложение $n$, а значит является его делителем, то $p_{1} \mid q_{1}q_{2}\ldots q_{m}$. Если точнее, оно делит $q_{j}, j= \overline{1, m}$.Но так как $q_{j}$ и $p_{1}$ — простые, то это возможно только в том случае, если $p_{1}=q_{i}$. Так как порядок множителей не имеет значения, пусть это будет $q_{1}$. И тогда мы можем сократить равенство на $p_{1}$ и получим $p_{2}\ldots p_{n}=q_{2}\ldots q_{m}$. Повторяя рассуждения, мы придем к тому, что кончатся множители одного разложения (предположим что $n < m$) и мы получим такое равенство $1= q_{n}q_{n+1} \ldots q_{m}$. Однако, так как все множители — простые, а значит (по определению простого числа) найдено противоречие. Это доказывает единственность.

Так как в разложении целого числа могут оказаться одинаковые множители, то можно обозначить количество вхождений множителя его степенью : $$n=p^{a_{1}}_{1}p^{a_{2}}_{2}\ldots p^{a_{n}}_{n}, $$ где $p_{i} \neq p_{j}$ при $i, j = \overline{1, n}, i \neq j$. Это называется каноническим разложением числа.

Примеры
  1. Каноническим разложением числа $100$ будет $2^{2} \cdot 5^{2}$.
  2. Каноническим разложением числа $255$ будет $3^{1} \cdot 5^{1} \cdot 17^{1}$.
  3. Каноническим разложением числа $53$ будет $53^{1}$.

Тест на канонические разложения

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

Литература

  1. Электронный конспект по алгебре. Автор Белозеров.Г.С.
  2. И.М.Виноградов. Основы теории чисел. 6-ое издание, 1952 год. стр.20-22.
  3. Д.К.Фадеев. Лекции по алгебре. 1984 год. стр. 14-15.

Простые числа. Решето Эратосфена

Очень интересными с математической (и не только) точки зрения считаются простые числа. Для начала сформулируем несколько определений для дальнейшей работы.

Определение. Простое число — это натуральное число больше единицы и которое делится нацело только на единицу и на само себя. Таким образом, $p$ считается простым, если $$p \in N, p > 1, \forall a \in N, a \neq 1, a \neq p, p \mbox{ mod } a \neq 0 .$$

Определение. Натуральное число не являющиеся простым и больше $1$ называется составным.

Примеры

  1. $3, 5, 7, 23$ — простые числа, что можно с легкостью проверить мысленно перебрав возможные делители для этих чисел. $177539$ — тоже простое число, однако проверить это устным перебором делителей будет значительно сложнее.
  2. Любое четное число кроме $2$ — составное, так как имеет как минимум один делитель помимо $1$ и самого себя — $2$.

Леммы

Сформулируем и докажем несколько лемм. Далее, если это потребуется, будем упоминать их как лемму и её номер в списке. Лемма (2), к примеру.

  1. Лемма. Пусть $p$ и является наименьшим делителем (не считая $1$) $ n \in N, n > 1$. Тогда $p$ — простое число.
    Спойлер

    Докажем от обратного. Предположим что $p$, наименьший делитель для $n$ из условия, составное число. В таком случае, его можно представить как $p=p_{1}p_{2}$. Отсюда $n=pb$ можно представить как $n=p_{1}p_{2}b$, где $p_{1}, p_{2} < p$. Если $n \vdots p$, то оно делится и на $p_{1}, p_{2}$. А так как они оба меньше $p$, то $p$ не может быть наименьшим делителем $n$. Таким образом, составное число не может быть наименьшим делителем числа, так как его всегда можно разложить на множители, которые в свою очередь тоже будут делителями $n$.

    [свернуть]
  2. Лемма. Пусть $p$ — наименьший (не считая $1$) натуральный делитель составного числа $n$. Тогда $p\leqslant \sqrt{n}$.
    Спойлер

    Пусть, по условию леммы, $p$ — наименьший отличный от нуля делитель $n$. Тогда $n = pb$, где $b\in N$ и $b\mid n$. Очевидно, что в таком случае $p \leqslant b < n$ и отсюда $p^{2} \leqslant n$, что доказывает неравенство данное в условии.

    [свернуть]

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

Алгоритм. Способ нахождения простых чисел до определенного $n$. Метод подразумевает фильтрацию чисел до $n$, отсеивая составные числа. Является псевдополиномиальным алгоритмом. Алгоритм заключается в следующем:

  1. Требуется выписать все числа от $2$ до $n$.
  2. Изначально $p=2$.
  3. Далее вычеркнем все числа представимые в виде $2p, 3p, 4p, \ldots$ до $n$.
  4. Присвоим $p$ следующее не вычеркнутое число. Будем повторять $3$ и $4$ шаги до тех пор, пока $p \leqslant \sqrt{n}$ (по лемме (2)).
  5. Таким образом, все составные числа будут вычеркнуты и останутся только простые.

Замечание

Если внимательно взглянуть на алгоритм, можно заметить что мы начинаем вычеркивать с $p^{2}$. Пусть $k \in N, k > 1$ и $k$ очередное простое (а значит не вычеркнутое) число в списке. А значит, что перед тем как $p=k$, мы вычеркнули (при условии что $k>2$) $2k$, ведь на первом шаге мы вычеркнули все делящиеся на $2$ числа. Если $k>3$, то и все делящиеся на $3$ числа были уже вычеркнуты. То есть $3k$ уже вычеркнуто. Таким образом, все составные числа имеющие нетривиальные делители до $k(k-1)$ включительно уже вычеркнуты, поэтому искать число чтобы вычеркнуть стоит начиная от $p^{2}$. Подробнее с модфикациями алгоритма можно ознакомится на википедии и e-max.

Пример

Найдем все простые числа до $20$ с помощью решета Эратосфена. Для начала выпишем все числа. $$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$

Положим $p=2$ и уберем все числа от $p^{2}$ до $20$. Останется $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} 9,\phantom{10,} 11, \phantom{12,} 13,\phantom{14,} 15,\phantom{16,} 17,\phantom{18,} 19 \phantom{,20}$$

Далее $p=3$, и мы снова убираем ненужные нам числа. $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} \phantom{9,10,} 11, \phantom{12,} 13,\phantom{14, 15, 16,} 17,\phantom{18,} 19 \phantom{,20}$$

Брать следующее $p$ не смысла, так как это будет $5$, а $5^{2}>20$. Таким образом мы нашли все простые числа до $20$.

Тест на простые числа и решето Эратосфена

У вас есть возможность проверить то, как вы усвоили материал.

Литература

  1. Электронный конспект по алгебре. Автор Белозеров.Г.С.
  2. И.М.Виноградов. Основы теории чисел. 6-ое издание, 1952 год. стр.18-20.

М1762. Две тысячи делителей

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров