Processing math: 100%

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

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

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

Существование. Пусть nN,n>1 и мы имеем два варианта.Если n простое, и тогда разложение уже получено, либо n составное, а значит может быть представлено в виде n=p0a0, где p0 — наименьший делитель n. Допустим a0>1, а значит у нас снова два варианта. Либо a0 — простое, либо оно составное и может быть представлено как a0=p1a1, где p1 — наименьший делитель a0. Таким образом мы дойдем до am1=pmam, где am=1. Тогда n=p0p1p2pm, где pi,i=¯0,m является простым по лемме (1) о простоте наименьшего делителя.

Единственность. Пусть существуют два разложения числа nN,n>1 на простые множители. Тогда p1p2pn=q1q2qm. Так как p1p2pn разложение n, а значит является его делителем, то p1q1q2qm. Если точнее, оно делит qj,j=¯1,m.Но так как qj и p1 — простые, то это возможно только в том случае, если p1=qi. Так как порядок множителей не имеет значения, пусть это будет q1. И тогда мы можем сократить равенство на p1 и получим p2pn=q2qm. Повторяя рассуждения, мы придем к тому, что кончатся множители одного разложения (предположим что n<m) и мы получим такое равенство 1=qnqn+1qm. Однако, так как все множители — простые, а значит (по определению простого числа) найдено противоречие. Это доказывает единственность.

Так как в разложении целого числа могут оказаться одинаковые множители, то можно обозначить количество вхождений множителя его степенью : n=pa11pa22pann, где pipj при i,j=¯1,n,ij. Это называется каноническим разложением числа.

Примеры
  1. Каноническим разложением числа 100 будет 2252.
  2. Каноническим разложением числа 255 будет 3151171.
  3. Каноническим разложением числа 53 будет 531.

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

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

Литература

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

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

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

Определение. Простое число — это натуральное число больше единицы и которое делится нацело только на единицу и на само себя. Таким образом, p считается простым, если pN,p>1,aN,a1,ap,p mod a0.

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

Примеры

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

Леммы

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

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

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

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

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

Замечание

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

Пример

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

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

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

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

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

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

Литература

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

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

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

Условие

Докажите неравенство ab+c+bc+a+ca+b>2,где a>0,b>0,c>0.

С.Нестеров

Решение

Рассмотрим функцию f(x,y,z)=xy+z+yz+x+zx+y, где x>0,y>0,z>0. Считая, без ограничения общности, xyz, докажем вначале неравенство f(x,y,z)f(x,y+z2,y+z2). Обозначив z+y2=α,zy2=t, перепишем (1) в виде ϕ(t)ϕ(0), где ϕ(t)=α+tα+xt+αtα+x+t.

Здесь 0tα,αx.

Докажем (2). Имеем ϕ(t)=(x+2a)(1(α+t)12(x+αt)321(αt)12(x+α+t)32). Очевидно, знак ϕ(t) совпадает со знаком функции ψ(t)=(αt)(x+α+t)3(α+t)(x+αt)3, и любой нуль функции ϕ(t) также является нулем функции ψ(t). Исследуем ψ(t). Имеем: ψ(t) — отличный от константы нечетный многочлен, степень которого не выше 3. Следовательно, ψ(t) имеет на положительной полуоси не более одного корня.

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

Итак, ϕ(t)min{ϕ(0),ϕ(α)}. Но, поскольку αx, имеем ϕ(0)=2αα+x2αx=ϕ(α). Неравенство (1) доказано.

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

Вследствие (1) для решения задачи достаточно доказать, что f1(x)=x2α+2αx+α>2 при 0<xα.

Исследуем f1(x) на отрезке [0;α]. Во внутренних точках этого отрезка знак f1(x) совпадает со знаком многочлена P(x)=(x+α)38α2x. Кроме того, любой нуль функции f1(x) является также нулем многочлена P(x). Заметим что P(α)=0; помимо этого, P(x) имеет корень на отрицательной полуоси. Следовательно, если P(x0)=0 при 0<x0<α, то при переходе через x0 многочлен P(x) меняет знак с «+» на «». Поэтому x0 — точка максимума функции f1(x).

Получили: f1(x)>min{f1(0),f1(α)} при 0<x<α. Но f1(α)=32>2=f1(0). Неравенство (3) доказано.

(Легко видеть, что P(x)=0 при x=α и при x=α(2±5). Значит исследуемая функция имеет экстремум на интервале (0;α).)

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

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

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

Условие

На гиперболе y=1x взяты две точки M(x0;y0) и N(x0;y0), симметричные относительно начала координат. Окружность с центром M, проходящая через точку N, пересекает гиперболу ещё в трех точках. Докажите, что эти точки лежат в вершинах правильного треугольника.

Решение

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

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

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

Теперь приступим к решению задачи. Пусть координаты точек A,B,C и M равны соответственно (xA;yA),(xB;yB),(xC;yC) и (xM;yM). По условию,{xy=1,(xx0)2+(yy0)2=4(x02+y02).Подставив y=1x из первого уравнения системы во второе, после несложных преобразований получаем уравнение для x:x42x03+=0

Мы выписали только два старших члена, поскольку остальные слагаемые нас не интересуют. По теореме Виета сумма всех корней этого уравнения, включая корень (x0), равна 2x0. Поэтому xA+xB+xC=3x0. Аналогично yA+yB+yC=3y0.

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

В.Сендеров