Метка: арифметика

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

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

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

Существование. Пусть $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.

М1653. Часы

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

Условие

На столе лежат $ 5 $ часов со стрелками. Разрешается любые из них перевести вперед. Для каждых часов время, на которое при этом их перевели, назовем временем перевода. Требуется все часы установить так, чтобы они показывали одинаковое время. За какое наименьшее суммарное время перевода это можно гарантированно сделать?

Решение

Ответ: за $ 24 $ часа.

Отметим на циферблате положения часов стрелок всех пяти часов (см. рисунок). Циферблат разобьется на пять секторов. Занумеруем их по кругу. Пусть часовая стрелка проходит секторы за $ x_1, x_2, x_3, x_4, x_5 $ часов соответственно. (Некоторые из этих чисел, нулевые; сумма $ x_1 + x_2 + x_3 + x_4 + x_5 $ равна $ 12 $ часам.)

Чтобы перевести все часы на начало первого сектора, необходимо затратить \begin{align*} & S_1 = (x_2 + x_3 + x_4 + x_5) + (x_3 + x_4 + x_5) + \\ & + (x_4 + x_5) + x_5 = x_2 + 2x_3 + 3x_4 + 4x_5 \end{align*} часов. Аналогично можно посчитать величины $ S_2, S_3, S_4 $ и $ S_5 $, где $ S_i $ — время, необходимое для установки всех часов на начало $ i $-го сектора. Следовательно, \begin{align*} & S_1 + S_2 + S_3 + S_4 + S_5 = (1 + 2 + 3 + 4) \times \\ & \times (x_1 + x_2 + x_3 + x_4 + x_5) = 10 \cdot 12 = 120 \end{align*} часов; наименьшая из величин $ S_i $ не превосходит $ 120 : 5 = 24 $ часа.

С другой стороны, если $ x_1 = x_2 = x_3 = x_4 = x_5 $ (например, если часы показывают $12$ ч, $2$ ч $24$ мин, $4$ ч $48$ мин, $7$ ч $12$ мин и $9$ ч $36$ мин), то все $ S_i $ равны $24$ часам. Менее чем $24$ часами в такой ситуацией не обойтись.

О.Подлипский