Блог Хеллера's Journal
 
 [Most Recent Entries] [Calendar View]

Friday, November 8th, 2013

    Time Event
    9:19a
    Антиспам

    В последние дни начался какой-то адовый завал спама. В блоге стоит премодерация, обычно спам сразу попадает в соответствующую папку, но с начала недели появилась куча спама, которая пропускается фильтром. «Куча» — это реально много, примерно 2000 сообщений в день. Мне их всех приходилось отклонять руками, поэтому естественно, что я не читал каждое сообщение и мог вместо спама отклонить ценные сообщения. Если ваше сообщение не прошло - то это я не со зла.

    Сейчас прикрутил к блоку новый модуль борьбы со спамом, пока вроде всё блокирует, но есть ощущение, что он может блокировать в том числе и вполне себе нормальных читателей по ошибке. Если ваш комментарий будет не проходить — пишите мне на почту, будем лечить.

    2:22p
    Делимость

    Очередной параграф учебника. Здесь много о делимости — начиная определениями чётных/нечётных чисел и заканчивая основной теоремой арифметики и алгоритмом Евклида. Одним выстрелом убил много зайцев сразу. Теперь заметки параграфов учебника буду прятать под кат, поскольку страница блога получается без этого слишком длинной, а формулы к тому же долго парсятся и в некоторых случаях даже способны на какое-то время повесить систему, что не хорошо.

    См. так же pdf и GitHub.

    В этом параграфе мы одним махом рассмотрим все базовые свойства делимости и связанные с этим понятия. Напомню, что мы ввели обозначение a|b для обозначения делимости b на a (равносильно a делит b). Формально это значит, что b=ka для некоторого k.

    Теорема. Если в сумме \sum_{i=0}^na_i все слагаемые делятся на b, то и вся сумма делится на b.

    Доказательство. По условию теоремы a_i = k_i b. Тогда
    \sum_{i=0}^na_i = \sum_{i=0}^n bk_i = b\sum_{i=0}^n k_i
    Последнее выражение как раз и означает, что первоначальная сумма делится на b, поскольку мы смогли из всей суммы вынести этот множитель за скобки. \square

    Теорема. Если в сумме \sum_{i=0}^na_i все слагаемые кроме одного делятся на b, то сумма не делится на b.

    Доказательство. Поскольку мы можем переставлять слагаемые как нам вздумается, будем считать, что на b не делится слагаемое a_0, а остальные слагаемые делятся. Это значит, что a_0 = k_0 b + r, r>0 и для всех i>0 имеем a_i=k_i b. Тогда мы можем записать сумму в следующем виде:
    \sum_{i=0}^na_i = k_0 b + r + \sum_{i=1}^n b k_i = b\sum_{i=0}^n k_i + r
    Последнее есть ни что иное как деление с остатком суммы на b, где остаток r>0. Это ровно то, что требовалось доказать. \square

    Упражнение. В теореме 3.14 принципиально то, что не делится на b лишь одно из слагаемых, но не больше. Покажите, что если в сумме не делится на b ровно два слагаемых, то сама сумма на b всё же может делиться.

    Упражнение. Докажите, что для того, чтобы произведение \prod_{i=0}^n a_i делилось на b, достаточно, чтобы хотя бы один из множителей a_i делился на b. Это условие не является необходимым: покажите так же, что возможна ситуация, когда ни один из множителей не делится на b, но само произведение на b делится.

    Определение. Число называется чётным, если оно делится на 2, и нечётным в противном случае.

    Любое чётное число может быть представлено в виде 2k, а нечетное в виде 2k+1.

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

    Понятие чётности/нечётности вроде на первый взгляд совершенно тривиально, однако оно постоянно возникает в математике. Например, в прошлом параграфе оно нам уже встречалось, хотя мы тогда не обратили на него внимания. С новой терминологией мы можем переформулировать алгоритм возведения в степень так: если b — чётное, то a^b = (a^{b/2})^2, а если нечётное, то a^b = (a^{(b-1)/2})^2 a. Мелочь, но подобная терминология в математике и её приложениях встречается сплошь и рядом, это довольно удобно.

    Используя теоремы выше мы можем легко вывести школьные «признаки делимости».

    Пример. Для того, чтобы число делилось на 4, необходимо и достаточно, чтобы число, составленное из двух младших разрядов делилось на 4. Действительно:
    \sum_{i=0}^\infty a_i 10^i = 100 \sum_{i = 2}^\infty a_i 10^{i-2} + (10a_1 + a_0)
    В последнем выражении сумма слева делится на 4, поэтому для делимости всего числа на 4 по теоремам 3.13-14 необходимо и достаточно, чтобы делилось на 4 выражение 10a_1 + a_0, а это и есть две последние цифры. Так, число 4133 не делится на 4, так как 33 не делится на 4, а число 12344 делится на четыре, так как 44 делится на 4.

    Упражнение. Докажите, что для того, чтобы число было четным, необходимо и достаточно, чтобы младший разряд числа был чётным.

    Упражнение. Докажите, что для того, чтобы число делилось на 5, необходимо и достаточно, чтобы младший разряд был равен 0 либо 5.

    Пример. Для того, чтобы число делилось на 3, необходимо и достаточно, чтобы сумма его цифр делилась на 3. Дейстивительно:
    \begin{align*}
    \sum_{i=0}^\infty a_i 10^i &= a_0 + (9+1)a_1 + (99+1)a_2 + \ldots\\
    &= \sum_{i=0}^\infty a_i + 9a_1 + 99a_2 + 999a_3 +\ldots \\
    &= \sum_{i=0}^\infty a_i + 3(3a_1 + 33a_2 +\ldots)
    \end{align*}
    Второе слагаемое всегда делится на три, поэтому для делимости всей суммы необходимо и достаточно, чтобы делилась на три сумма \sum_{i\in\mathbb{N}} a_i.

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

    Пример. Можно придумать еще множество критериев подобным образом, а так же сочетая существующие критерии. Например, для того, чтобы число делилось на 6, необходимо и достаточно, чтобы оно одновременно делилось на 2 и на 3. Придумайте еще подобные критерии.

    Как мы уже отмечали в первом параграфе, отношение делимости задаёт частичный порядок на \mathbb{N}. Напомню, что в § 2.2 мы ввели понятие точных нижних и точных верхних граней для частично упорядоченных множеств и обозначили это как \inf и \sup соответственно. Эти понятия можно применить и к отношению делимости:

    Определение. Наибольшим общим делителем (НОД) чисел множества S называется \inf S, а наименьшим общим кратным (НОК) \sup S.

    Это определение требует, видимо, расшифровки. Для простоты будем считать, что множество S состоит из двух чисел x и y, хотя всё сказанное легко обобщается на случай произвольного конечного количества чисел.

    Величина d называется общим делителем чисел x и y, если одновременно d делит и x и y. Множество всех нижних граней множества \{x, y\} есть на самом деле множество общих делителей этих чисел. Самый большой элемент этого множества является наибольшим общим делителем чисел x и y, а это и есть определение точной нижней грани.

    Аналогично число d называется общим кратным чисел x и y, если оно делится одновременно и на x и на y. Наименьшее из таких чисел — это наименьшее общее кратное, а по совместительству точная нижняя грань из всех общих кратных.

    Часто в учебниках принято обозначать НОД как \gcd (greatest common divisor), а НОК как \operatorname{lcm} (least common multiplier). Нам НОК будет требоваться довольно редко, а вот для НОД мы примем другое обозначение: вместо \gcd(x, y) будем писать просто (x, y). На данный момент это может показаться странным и бессмысленным, но на это есть глубокая причина, которую читатель увидит в следующей главе.

    Определение. Число называется простым, если оно имеет в точности два делителя.

    Два делителя — это само число и единица. Можно было бы сказать «не имеет делителей, кроме себя и единицы», это было бы понятнее, но тогда такое определение распространялось бы и на саму единицу, которая в соответствии с данным определением простым числом не является. Может возникнуть вопрос: а почему не считать единицу за простое число? Быстрый ответ таков, что это просто удобнее в большинстве случаев. Более глубокий ответ будет дан в следующей главе.

    Определение. Числа x и y называются взаимопростыми, если (x, y) = 1.

    Любое число, если оно не простое, можно представить в виде произведения некоторых других чисел. Эти числа, если они не простые, опять же можно представить в виде какого-то произведения. Например,
    120 = 10 \cdot 12 = 2\cdot 5 \cdot 2 \cdot 6 = 2\cdot 5 \cdot 2 \cdot 2 \cdot 3
    Таким образом, любое натуральное число мы можем представить в виде произведения простых чисел и простые числа оказываются в некотором смысле строительными блоками для всех остальных натуральных чисел. Возникает естественный вопрос: а сколько простых чисел всего? Или хотя бы их конечное число, или бесконечное? Ответ даёт следующая теорема.
    Теорема Евклида. Простых чисел бесконечно много.
    Доказательство. Пойдём от противного и предположим, что это не так. Пусть простых чисел всего N штук. Обозначим их как {p_i}. Тогда число 1 + \prod_{i=1}^N p_i не делится ни на одно из p_i, и соответственно само является простым. Это противоречит тому, что простых чисел всего N штук, откуда следует что простых чисел бесконечно много. \square

    Касательно разложения чисел на простые множители остаётся еще такой вопрос: а однозначное ли это разложение? То есть понятно, что оно не однозначно с точки зрения порядка сомножителей, однако сами эти эти сомножители будут ли всегда одними и теми же, или могут отличаться? Так сходу это уже не докажешь, потребуется некоторая подготовка.

    Займем из далека и начнем с быстрого способа нахождения НОД, который так же носит имя Евклида. Пусть нам надо найти величину (x, y). Вначале поделим с остатком x на y:

    x = q_0 y + r_0
    Теперь поделим с остатком y на r_0:
    y = q_1 r_0 + r_1.
    И будем продолжать этот нехитрый процесс:
    r_0 = q_2 r_1 + r_2
    r_1 = q_3 r_2 + r_3
    \dots
    Последовательность \{r_i\} строго убывающая, поэтому в какой-то момент у нас эти числа поделятся без остатка:
    r_{n-2} = q_n r_{n-1} + r_n
    r_{n-1} = q_{n+1} r_n
    Давайте покажем, что r_n является НОД чисел a и b. Из последней строчки видно, что r_n | r_{n-1}. Перепишем теперь предпоследнюю строчку таким образом:
    r_{n - 2} - q_n r_{n - 1} = r_n
    Здесь и r_n и r_{n-1} делятся на r_n, стало быть и r_{n-2} обязана делиться на r_n. Поднимаясь еще на строчку выше, получим аналогично, что r_n|r_{n-3}. Продолжая процесс нужное количество шагов, мы придём в результате к тому, что r_n|x и r_n|y.

    Это доказывает, что r_n является общим делителем, но не доказывает, что это делитель наибольший. Пусть d = (x, y). Из первой строчки алгоритма Евклида видно, что d|r_0. Из второй строчки теперь можно увидеть, что d|r_1. Спускаясь ниже, получаем, что d|r_n, но r_n и сам является делителем x и y. Это доказывает, что действительно r_n = (x, y).

    Сам по себе этот алгоритм хоть и быстр, но нам бесполезен: мы не собираемся искать НОД чисел. Что нам интересно, так это следствия из этого алгоритма.

    Перепишем предпоследний шаг алгоритма Евклида как r_n = r_{n-2} - q_n r_{n-1}. Поднимемся на строчку выше, и из r_{n-3} = q_{n-1} r_{n-2} + r_{n-1} подставим значение r_{n-1}:
    r_n = r_{n-2} - q_n(r_{n-3} - q_{n-1}r_{n-2}) = (1+q_n q_{n-1})r_{n-2} - q_n r_{n-3}
    Поднимаясь на строчку выше, мы можем выразить r_{n-2} через r_{n-3} и r_{n-4}, после чего мы получим следующее выражение:
    r_n = \alpha r_{n-3} + \beta r_{n-4}
    Здесь \alpha и \beta — это некоторые коэффициенты, выражающиеся через значения q_i. Их можно найти строго, но они нас не волнуют. На самом деле возможно тут будет и не сумма, а разность, например, \alpha r_{n-3} - \beta r_{n-4} или наоборот \beta r_{n-4} - \alpha r_{n-3}. Мы будем считать, что один из коэффициентов может идти со знаком минус (в следующей главе мы введём отрицательные числа и нам не надо будет делать таких оговорок, но пока будем считать так).

    Продолжая процесс построчно вверх по алгоритму Евклида, мы в конечном счете приходим к такому выражению:

    Соотношение Безу. (x, y) = \lambda x + \mu y для любых x и y, где \lambda и \mu могут содержать знак минус.
    Следствие. Если числа x и y взаимопросты, то найдутся такие \lambda и \mu, что
    \lambda x + \mu y = 1
    Следствие. Если числа x и y взаимопросты, то любое число n может быть представлено как
    n = \lambda x + \mu y
    Доказательство. Первое следствие элементарно, поскольку оно фуктически дублирует определение взаимной простоты (x, y) = 1. Второе следствие получается из первого, если умножить обе части на n:
    (n\lambda) x + (n\mu) y = 1

    Лемма Евклида. Пусть a и b произвольные числа и p — простое число такое, что p|ab. Тогда либо p|a, либо p|b.
    Доказательство. Предположим, что p не делит a. В этом предположении докажем, что оно обязано тогда делить b. Если p не делит b, то рассуждения будут симметричны, но в отношении a. \square

    Поскольку p простое и не делит a, это значит, что оно взаимопросто с a. По соотношению Безу
    \lambda p + \mu a = 1
    Умножим это на b:
    \lambda bp + \mu ab = b
    В левой части оба слагаемых делятся на p. Значит, правая часть так же должна делиться на p. \square

    Вот теперь мы готовы к финальному шагу.

    Основная теорема арифметики. Любое натуральное число однозначно раскладывается на простые множители с точностью до порядка сомножителей.
    Доказательство. Предположим, что это не так и некотор

    << Previous Day 2013/11/08
    [Calendar]     		Next Day >>

Блог Хеллера   About LJ.Rossia.org