Автор: Артем Рогулин

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

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

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

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

М1818. Доказать неравенство с тремя параметрами

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

Условие

Докажите неравенство $$\sqrt{\cfrac{a}{b+c}}+\sqrt{\cfrac{b}{c+a}}+\sqrt{\cfrac{c}{a+b}}>2,$$где $a>0, b>0, c>0$.

С.Нестеров

Решение

Рассмотрим функцию $$f(x,y,z)=\sqrt{\cfrac{x}{y+z}}+\sqrt{\cfrac{y}{z+x}}+\sqrt{\cfrac{z}{x+y}},$$ где $x>0, y>0, z>0$. Считая, без ограничения общности, $x\leqslant y \leqslant z$, докажем вначале неравенство $$f(x,y,z)\leqslant f(x,\cfrac{y+z}{2}, \cfrac{y+z}{2}). \tag{1}$$ Обозначив $\cfrac{z+y}{2}=\alpha, \cfrac{z-y}{2}=t$, перепишем $(1)$ в виде $$\phi (t)\geqslant \phi (0),\tag{2}$$ где $$\phi (t)=\sqrt{\cfrac{\alpha + t}{\alpha + x — t}}+\sqrt{\cfrac{\alpha — t}{\alpha + x + t}}.$$

Здесь $0\leqslant t \leqslant \alpha, \alpha \geqslant x$.

Докажем $(2)$. Имеем $$\phi^{\prime}(t)=(x+2a)\left (\cfrac{1}{(\alpha + t)^{\frac{1}{2} }(x+\alpha-t)^{\frac{3}{2}}} — \cfrac{1}{(\alpha — t)^{\frac{1}{2}}(x+\alpha +t)^{\frac{3}{2}}}\right ).$$ Очевидно, знак $\phi^{\prime}(t)$ совпадает со знаком функции $$\psi (t)=(\alpha — t)(x + \alpha + t)^{3}-(\alpha + t)(x+\alpha -t)^{3},$$ и любой нуль функции $\phi^{\prime} (t)$ также является нулем функции $\psi (t)$. Исследуем $\psi (t)$. Имеем: $\psi (t)$ — отличный от константы нечетный многочлен, степень которого не выше $3$. Следовательно, $\psi (t)$ имеет на положительной полуоси не более одного корня.

Получили: $\phi (t)$ может иметь внутри отрезка $[0,\alpha]$ не более одного экстремума. Но и этот экстремум не может быть минимумом, поскольку $\psi (\alpha)<0$.

Итак, $\phi (t) \geqslant min\{ \phi (0), \phi(\alpha)\} $. Но, поскольку $\alpha \geqslant x$, имеем $$\phi(0)=2\sqrt{\cfrac{\alpha}{\alpha + x}}\leqslant \sqrt{\cfrac{2\alpha}{x}}=\phi (\alpha).$$ Неравенство $(1)$ доказано.

(Выше мы ограничились необходимой нам информацией о производной; легко получить и полную информацию о ней. Именно, $\psi (t)$ — многочлен третьей степени; $\psi (t) = 0$, при $t = 0$ и при $$t^{2}=\cfrac{(x+\alpha)^{2}(2\alpha — x)}{3x+2\alpha}.$$ При этом $t^{2}<\alpha^{2}$ при $x>0, \alpha>0$. Значит исследуемая функция при любом $x, x < 0 < \alpha$, имеет экстремум на интервале $(0;\alpha)$.)

Вследствие $(1)$ для решения задачи достаточно доказать, что $$f_{1}(x)=\sqrt{\cfrac{x}{2\alpha}}+2\sqrt{\cfrac{\alpha}{x+\alpha}}> 2 \tag{3}$$ при $0<x\leqslant \alpha$.

Исследуем $f_{1}(x)$ на отрезке $[0;\alpha]$. Во внутренних точках этого отрезка знак $f^{\prime}_1(x)$ совпадает со знаком многочлена $P(x)=(x+\alpha)^{3}-8\alpha^{2}x$. Кроме того, любой нуль функции $f^{\prime}_{1}(x)$ является также нулем многочлена $P(x)$. Заметим что $P(\alpha)=0;$ помимо этого, $P(x)$ имеет корень на отрицательной полуоси. Следовательно, если $P(x_0)=0$ при $0<x_0<\alpha$, то при переходе через $x_0$ многочлен $P(x)$ меняет знак с $«+»$ на $«-»$. Поэтому $x_0$ — точка максимума функции $f_1(x)$.

Получили: $$f_{1}(x)>min\{f_{1}(0),f_{1}(\alpha)\}$$ при $0<x<\alpha$. Но $$f_{1}(\alpha)=\cfrac{3}{\sqrt{2}}>2=f_{1}(0).$$ Неравенство $(3)$ доказано.

(Легко видеть, что $P(x)=0$ при $x=\alpha$ и при $x=\alpha(-2\pm \sqrt{5})$. Значит исследуемая функция имеет экстремум на интервале $(0;\alpha)$.)

А.Ковальджи, С.Нестеров, В.Сендеров

М1345. Задача об окружности пересекающей гиперболу и правильном треугольнике

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

Условие

На гиперболе $y =\displaystyle \frac{1}{x}$ взяты две точки $M(x_0;y_0)$ и $N(-x_0;-y_0)$, симметричные относительно начала координат. Окружность с центром $M$, проходящая через точку $N$, пересекает гиперболу ещё в трех точках. Докажите, что эти точки лежат в вершинах правильного треугольника.

Решение

Для решения данной задачи вам потребуется следующая

Лемма. Пусть точки $A, B, C$ лежат на окружности с центром $M$. Тогда треугольник $ABC$ является правильным тогда и только тогда, когда $\overrightarrow{\mkern -3mu OA\mkern 3mu}+\overrightarrow{\mkern -3mu OB\mkern 3mu}+\overrightarrow{\mkern -3mu OC\mkern 3mu}=3 \mkern 3mu \overrightarrow{\mkern -3mu OM\mkern 3mu}.$

Из данного равенства сразу следует, что $\overrightarrow{\mkern -3mu MA\mkern 3mu}+\overrightarrow{\mkern -3mu MB\mkern 3mu}+\overrightarrow{\mkern -3mu MC\mkern 3mu}=\overrightarrow{0}$, но это означает, что точка $M$ совпадает с центром тяжести треугольника $ABC$, т.е. с точкой пересечения его медиан (убедитесь в этом). Таким образом, длины всех всех медиан треугольника $ABC$ равны. Отсюда следует что треугольник правильный. (Обратное утверждение очевидно.)

Теперь приступим к решению задачи. Пусть координаты точек $A, B, C$ и $M$ равны соответственно $(x_A;y_A), (x_B;y_B), (x_C;y_C)$ и $(x_M;y_M)$. По условию,$$  \begin{cases}xy=1,\\(x-x_0)^{2}+(y-y_0)^{2}=4({x_0}^2+{y_0}^2).\end{cases}  $$Подставив $y=\displaystyle \frac{1}{x}$ из первого уравнения системы во второе, после несложных преобразований получаем уравнение для $x$:$$x^{4}-2{x_0}^3+\dots=0$$

Мы выписали только два старших члена, поскольку остальные слагаемые нас не интересуют. По теореме Виета сумма всех корней этого уравнения, включая корень $(-x_0)$, равна $2x_0$. Поэтому $x_{A}+x_{B}+x_{C}=3x_0$. Аналогично $y_{A}+y_{B}+y_{C}=3y_0$.

Последние равенства означают, что $$\overrightarrow{\mkern -3mu OA\mkern 3mu}+\overrightarrow{\mkern -3mu OB\mkern 3mu}+\overrightarrow{\mkern -3mu OC\mkern 3mu}=3 \mkern 3mu \overrightarrow{\mkern -3mu OM\mkern 3mu},$$ где $O$ начало координат. Осталось воспользоваться доказанной нами леммой.

В.Сендеров