Processing math: 100%

Алгоритм Евклида

Алгоритм Евклида — это эффективный алгоритм для нахождения НОД. Для натуральных чисел, таких как 9 и 6, достаточно было просто перебирать числа для нахождения НОД. Если же перебирать числа для более сложных примеров, как, например, 52152 и 9875, то процесс нахождение НОД будет слишком долгим. Поэтому, вместо того чтобы перебирать числа, можно просто выполнить ряд простых действий.

Определение. Даны числа A,BZ+, где AB и rk,qkZ+, при k=1,2,3n, где rkостаток, а qkчастное. Находим ряд равенств: A=Bq1+r1 B=r1q2+r2 r1=r2q3+r3 rn1=rnqn+1+0, где rn и будет НОД целых чисел A и B. Все ранее написанное и называется алгоритмом Евклида.

Другими словами, мы представляем деление A на B, как A=Bq+r и пока остаток r0 мы делим делитель на остаток от деления. А так как остаток всегда меньше делителя двух целых чисел (r1<B или rn<rn1), то рано или поздно остаток будет равен нулю. А НОД двух чисел будет последний делитель.

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


Спойлер

НОД двух многочленов

Как и с большими целыми числами, алгоритм Евклида очень удобен для поиска НОД двух многочленов.

Теорема. Наибольший общий делитель двух многочленов существует.

Пусть даны два многочлена f(x),g(x)P[x], где deg(f(x))deg(g(x)). Находим ряд равенств: f(x)=g(x)q1(x)+r1(x) g(x)=r1(x)q2(x)+r2(x) r1(x)=r2(x)q3(x)+r3(x) rn1(x)=rn(x)qn+1(x)+0, где rk,qkP[x] при k=1,2,3,,n, где rk — остаток, а qk — частное. В случае с целыми числами, остатки в алгоритме убывают, при многочленах же убывают степени остатка (deg(rn(x))<deg(rn1(x))<deg(rn2(x))<), это означает, что наступит момент деления без остатка. Поэтому НОД двух многочленов, по алгоритму Евклида, будет последний отличный от нуля остаток(в нашем случае rn).

В доказательстве мы явно описали принцип работы алгоритма Евклида для нахождения НОД двух многочленов над одним полем.

Запишем тот же алгоритм делением в столбик.

Примеры решения задач

Решим пару простых задач, где используется алгоритм Евклида. Рекомендую решить задания самостоятельно, а потом смотреть решение.

  1. Найти НОД 784 и 552 используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: 784=552×1+232 552=232×2+88 232=88×2+56 88=56×1+32 56=32×1+24 32=24×1+8 24=8×3+0, где число 8 — НОД 784 и 552, так как это последний делитель.

  2. Найти НОД 868 и 923 используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: 923=868×1+55 868=55×15+43 55=43×1+12 43=12×3+7 12=7×1+5 12=7×1+5 7=5×1+2 5=2×2+1 2=1×2+0, где число 1 — НОД 868 и 923, так как это последний делитель.

  3. Найти НОД 52800 и 54108 используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: 54108=52800×1+1308 52800=1308×480+480 1308=480×2+348 480=348×1+132 348=132×2+84 132=84×1+48 84=48×1+36 48=36×1+12 36=12×3+0, где 12 — НОД 52800 и 54108.

  4. Найти НОД x510x320x215x4 и x46x28x3 используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: x510x320x215x4=x(x46x28x3)4x312x212x4 x46x28x3=(4x312x212x4)(x4)3x39x2x9x3 4x312x212x4=(3x39x2x29x3)(43)+0, где 3x39x29x3 — НОД многочленов x510x320x215x4 и x46x28x3, так как это последний делитель в алгоритме.

Проверка на освоение материала «Алгоритм Евклида».

Смотрите также

  1. Конспект Г.С.Белозерова. Глава 3 — 15с. — С. 3-5.
  2. Д.К. Фаддеев. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука, 1984. — 416 с. — С. 7-11.
  3. И.М. Виноградов. Основы теории чисел. — Москва, 1952. — 181 с. — С. 8-12.

M1815. О перпендикулярах в неплоском четырехугольнике

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

Условие

Общие перпендикуляры к противоположным сторонам неплоского четырехугольника ABCD взаимно перпендикулярны.

Докажите, что они пересекаются.

Решение

Инструментом решения является теорема Менелая для пространственного четырехугольника, утверждающая, что точки X, U, Y, V, взятые на сторонах четырехугольника AB, BC, CD, DA или их продолжениях, лежат в одной плоскости тогда и только тогда, когда AXXBBUUCCYYDDVVA=1.

Для доказательства теоремы Менелая продолжим прямые XU и YV до пересечения с AC. Точки X, U, Y, V лежат в одной плоскости тогда и только тогда, когда все три прямые пересекаются в одной точке P либо параллельны (рис. 1).

Рис. 1

Но в этом случае, применяя теорему Менелая к треугольникам ABC и ACD, получаем AXXBBUUCCPPA=1 и CYYDDVVAAPPC=1. Перемножая эти равенства, получим требуемое соотношение.

Пусть теперь XY – перпендикуляр к сторонам AB и CD, UV – перпендикуляр к AD и BC. При ортогональной проекции на плоскость, параллельную XY и UV, прямой угол между прямыми AB и XY остается прямым. Поэтому четырехугольник ABCD проецируется в прямоугольник ABCD, а прямые XY и UV – в параллельные его сторонам прямые XY и UV (рис. 2). Очевидно, что AXXBBUUCCYYDDVVA=1.

Рис. 2

Следовательно, AXXBBUUCCYYDDVVA=1, и по теореме Менелая точки X, Y, U, V лежат в одной плоскости. Отсюда сразу следует утверждение задачи.

А.Заславский

4.1 Непрерывные функции. Определение и примеры

Определение. Пусть функция f определена на интервале (a,b) и точка x0(a,b). Говорят, что функция f непрерывна в точке x0, если limxx0f(x)=f(x0).

Замечание. В отличие от определения предела функции f в точке x0, здесь мы требуем, чтобы функция f была определена не только в проколотой окрестности точки x0, а в целой окрестности точки x0. Кроме того, limxx0f(x) не просто существует, а равен определенному значению, а именно, f(x0).

Используя определение предела функции в смысле Коши, определение непрерывности функции f в точке x0 в кванторах можно записать следующим образом: ε>0δ=δ(ε)>0:x(a,b):|xx0|<δ|f(x)f(x0)|<ε.

В этом определении можно не требовать выполнения условия |xx0|>0, т. к. при |xx0|=0 неравенство |f(x)f(x0)|<ε, очевидно, выполнено.

Так как величина limxx0f(x) зависит лишь от тех значений, которые функция f принимает в сколь угодно малой окрестности точки x0, то непрерывность – это локальное свойство функции.

В терминах окрестностей определение непрерывности выглядит следующим образом.

Определение. Функция f называется непрерывной в точке x0, если для любой окрестности V точки f(x0) найдется такая окрестность U точки x0, что для всех xU значение f(x)V, т. е. f(U(a,b))V.

Применяя определение предела функции в смысле Гейне, определение непрерывности можно сформулировать так.

Определение. Функция f, определенная на интервале (a,b), называется непрерывной в точке x0(a,b), если любая последовательность аргументов {xn} (xn(a,b),xnx0) порождает последовательность значений функции {f(xn)}, стремящуюся к f(x0).

Применяя понятие, одностороннего предела (т. е. предела слева и справа) в точке x0, можно дать определения непрерывности слева (справа) в точке x0. Именно, функция f называется непрерывной слева (справа) в точке x0, если limxx00f(x)=f(x0) (limxx0+0f(x)=f(x0)). При этом в определении непрерывности слева достаточно считать, что функция f определена лишь в левой полуокрестности точки x0, т. е. на (a,x0], а для
непрерывности справа – на [x0,b).

Легко видеть, что справедливо следующее

Утверждение. Для того чтобы функция f была непрерывной в точке x0, необходимо и достаточно, чтобы f была непрерывной слева и справа в точке x0.

Определение. Функция f, определенная на интервале (a,b), называется разрывной в точке x0(a,b), если f не является непрерывной в этой точке.

Итак, функция f является разрывной в точке x0, если выполнено одно из двух следующих условий.

  1. Либо не существует limxx0f(x).
  2. Либо предел limxx0f(x) существует, но он не равен f(x0).

Пример 1. f(x)C=Const. Эта функция непрерывна в каждой точке x0R, т. к. для любого xR |f(x)f(x0)|=0.

Пример 2. f(x)=x2, <x<+, x0R. Зададим ε>0. Тогда из неравенства |x2x02|(|x|+|x0|)|xx0| следует, что при |xx0|<δ=min(1,ε2|x0|+1) справедливо неравенство |x2x02|<ε, т. е. limxx0x2=x02, а значит, функция f(x)=x2 непрерывна в любой точке x0R.

Пример 3. f(x)=x, 0x+ Если x0(0,+), то |xx0|=|xx0|x+x01x0|xx0|<ε если только |xx0|<δx0ε. Таким образом, функция f(x)=x непрерывна в каждой точке x0>0. В точке x0=0 можно ставить вопрос о непрерывности справа. Имеем |x0|=x<ε, если только 0x<δε2. Итак, limx0+x=0=0, т. е. функция f(x)=x непрерывна справа в точке 0.

Пример 4. f(x)=sinx, <x<+. Пусть x0R. Тогда |sinxsinx0|=|2cosx+x02sinxx02|2|sinxx02||xx0|, где последнее неравенство в этой цепочке следует из доказанного выше неравенства |sint||t| (0<|t|<π2). Можем считать, что |xx0|<π. Тогда при |xx0|<δmin(π,ε) справедливо |sinxsinx0|<ε, т. е. функция f(x)=sinx непрерывна в каждой точке x0R. Аналогично доказываем, что функция f(x)=cosx непрерывна в каждой точке x0R.

Пример 5. f(x)=xsin1x при x0 и f(0)=0. Покажем, что функция f непрерывна в точке x0=0. Имеем f(0)=0 и limx0f(x)=limx0xsin1x=0 (т. к. |f(x)0|=|xsin1x||x|<ε, если только |x0|=|x|<δε). Итак, limxx0f(x)=f(0), так что f непрерывна в точке 0.

Пример 6. f(x)=signx, xR. Если x00, то функция f постоянна в некоторой окрестности точки x0 и, следовательно, непрерывна в этой точке. Если же x0=0, то не существует предела функции f при x0. Значит, функция f разрывна в точке 0. Более того,limx0+signx=1, limxx0f(x)signx=1, sign0=0, так что функция signx разрывна в точке 0 как слева, так и справа.

Пример 7. Рассмотрим функцию Дирихле D(x)={1,если xQ;0,если xRQ. Пусть x0R. Покажем, что не существует предела функции D при xx0. Для этого выберем последовательность {x} отличных от x0 рациональных чисел, стремящуюся к x0. Тогда D(xn)=1 и, значит, limn+D(xn)=1. Если же взять последовательность xn отличных от x0 иррациональных чисел, стремящуюся к x0, то получим, что D(xn)=0 и limn+D(xn)=0. В силу определения предела функции по Гейне получаем, что функция D не имеет предела в точке x0. Так как x0R – произвольная точка, то это означает, что функция Дирихле разрывна в каждой точке.

Пример 8. f(x)=xD(x), xR. Функция f разрывна в каждой точке x00. В самом деле, если {xn} и {xn} соответственно последовательности рациональных и иррациональных отличных от x0 чисел, стремящиеся к x0, то limnf(xn)=x0 и limnf(xn)=0, так что, в силу определения предела функции по Гейне, функция f не имеет предела в точке x0. Если же x0=0, то limn0f(x)=0=f(0). Действительно, |f(x)|=|xD(x)||x|<ε, если только |x0|=|x|<δε. Это означает, что данная функция непрерывна в единственной точке x0=0.

Пример 9. Дана функция f(x)={sinxx,если x0;1,если x=0. Проверить на непрерывность в точке x0=0.

Решение

limxx00sinxx=limx0+0sinxx=1=f(x0) Отсюда следует, что f(x) непрерывна в точке x0, т. к. для того чтобы функция f была непрерывной в точке x0, необходимо и достаточно, чтобы f была непрерывной слева и справа в точке x0.

Пример 10. Покажите, что функция f(x)=x+3x2 разрывна в точке x0=2.

Решение

Для этого достаточно показать, что предел данной функции при xx0 либо не равен значению функции в точке x0, либо не существует. limx20x+3x2= limx2+0x+3x2=+ Т. к. левосторонний и правосторонний пределы f(x) не совпадают, то предела функция в точке x0 не имеет, следовательно она разрывна в этой точке.

Литература

Непрерывные функции. Определение и примеры

Тест по теме: «Непрерывные функции. Определение и примеры.»


Таблица лучших: Непрерывные функции. Определение и примеры

максимум из 5 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

M683. О расположении разноцветных кружков

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

Условие

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

Доказательство

Доказательство возможности требуемой раскраски проведем индукцией по числу кружков n. При n4 утверждение очевидно. Предположим, что оно справедливо для любого расположения k кружков. Пусть на столе лежит k+1 кружков. Зафиксируем на плоскости произвольную точку M и рассмотрим кружок, центр O которого находится на наибольшем расстоянии от M (если таких кружков несколько, возьмем любой из них). Нетрудно убедиться, что выбранного кружка касается не более двух других (центры всех кружков лежат в круге (M,|OM|) — рис. 1). Отбросим кружок с центром O и раскрасим нужным образом в четыре цвета оставшиеся k кружков (по предположению индукции это можно сделать). Вернем теперь кружок с центром O на место. Поскольку он касается не более трех из уже покрашенных кружков, его можно раскрасить в тот цвет, который не был использован при раскраске касающихся его соседей.

Утверждение доказано.

Рисунок 1.

На рисунке 2 изображены 11 кружков, для нужной раскраски которых трех цветов недостаточно. Действительно, предположив, что эти кружки можно раскрасить тремя цветами, получим, что кружки A,B,C,D,E должны быть окрашены одинаково. Но это невозможно, поскольку кружки A и E касаются.

Рисунок 2.

M610. Об «интересных» наборах чисел

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

Условие

Фиксируем kN.
а) Рассмотрим множество всех наборов целых чисел a1,,ak таких, что 0a1a2akk; обозначим число таких наборов через N. Рассмотрим среди них те, для которых ak=k; пусть их число равно M. Докажите, что N=2M.
б) Наложим на рассматриваемые наборы дополнительное ограничение: сумма a1++ak делится на k. Пусть соответствующие числа равны N и M. Докажите, что N=2M (Из рисунка 1 видно, что при k=3 эти числа равны M=10, N=20; M=4, N=8.)

Рис. 1.

Решение

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

Нам нужно доказать, что наборов, в которых ak=k ровно половина. Поэтому попробуем установить взаимно однозначное соответствие между этими наборами и оставшимися, теми, у которых ak<k.

Сопоставить набору (a1,a2,,ak) набор (ak,ak1,,a1) нельзя, так как новый набор — невозрастающий. Можно попробовать сопоставить набору (a1,,ak) набор kak,kak1,,ka1): он уже — неубывающий, но… ka1 не обязательно быть меньше k. Поэтому это соответствие не решает задачу.

Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.

Рис. 2

Что это такое, проще всего объяснить на примере: набору (0,0,2,3,5) соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.

Дополним диаграмму Юнга до квадрата (рис. 3). Тогда становится ясно, что наша первоначальная идея заключалась в том, что отсчитывать диаграмму не из красных, а из белых квадратиков (и, соответственно, не слева-снизу, а справа-сверху).

Рис. 3

Попытаемся теперь дополнить рисунок 3 вертикальной диаграммой — как на рисунке 4. Отсчитывая эту диаграмму снизу-слева, получим набор (2,2,3,4,4). Назовем этот набор дополнительным к набору (0,0,2,3,5). Еще один пример изображен на рисунке 5.

Ясно, что если исходный набор (a1,,ak), а дополнительный — (b1,,bk), то (ak=k) тогда и только тогда, когда bk<k. В самом деле, ak=k, если верхняя правая клетка входит в основную диаграмму Юнга, и ak<k, если она входит в дополнительную.

Рис. 4

Установленное нами соответствие между наборами, у которых ak=k, и наборами, у которых ak<k, очевидно, взаимно однозначно. Тем самым мы решили a). Кроме того, сумма чисел исходного и дополнительного наборов равна k2 (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на k тогда и только тогда, когда делится на k сумма чисел исходного набора. Это решает б).

Рис. 5

Замечание. Задача a) имеет и другое решение: можно непосредственно посчитать числа N и M.

Лемма. Число наборов целых чисел a1,,am таких, что 0a1amk равно Cmk+m.

Доказательство. Рассмотрим набор (b1,,bm) где bi=ai+i:b1=a1+1,b2=a2+2 и т. д. Тогда, очевидно, 1<b1<b2<<bmk+m, то есть (b1,,bm) — произвольный возрастающий набор m целых чисел их первых k+m чисел. Число таких наборов равно Cmkm.

Поэтому число наборов, в которых akk, по лемме равно Ck2k. Если же ak=k, то нам остается выбрать числа a1,,ak1 так, что 0a1ak1k; их число равно Ck12k1. Остается посчитать, что 2Ck12k1 равно Ck2k.

А. Толпыго