Below are the 3 most recent journal entries recorded in maria_v's LiveJournal:

Tuesday, July 1st, 2008
4:06 am	Замечания к вводной лекции -- 2 Замечание второе -- о простых числах. Простое число -- это целое число, которое делится только на себя и на 1, с точностью до знака. Если ограничиться только натуральными (целыми положительными) числами, то простое число делится только на себя и на 1. Как уже говорилось, Пифагор не любил таких чисел. Евклид относился к ним либеральнее. В его книге есть доказательство, что простых чисел в натуральном ряду бесконечно много. Сформулируем сначала Основную теорему арифметики: любое натуральное число, кроме 0 (напоминание: некоторые начинают отсчет натуральных чисел с 0, а другие -- с 1), единственным образом разлагается на простые множители. То есть, если натуральное число n = p1p2... pk можно представить также в виде n = q1q2... ql, то k=l, а q1, q2..., qk суть не что иное, как перестановка из чисел p1, p2, ..., pk. Здесь мы наметим примерный ход доказательства. З2.1 Пусть натуральные числа a и b взаимно просты (это означает, что у них нет общих делителей, кроме 1). Пусть, кроме того, произведение ab делится на p, где p -- простое число. Доказать, что в этом случае a делится на p или b делится на p. (Указание: если a не делится на p, то его можно представить в виде a = pk + r, где r < p, r, k -- натуральные. Если b не делится на p, то и b можно представить в аналогичном виде: b = pl + s, s < p, l, s -- натуральные.) После того, как это утверждение доказано, нужно взять произвольное n и рассмотреть два его разложения на простые множители: n = p1p2... pk = q1q2... ql Пусть сначала n таково, что все эти сомножители различны. Возьмем, например, q1 и рассмотрим произведение двух чисел p1(p2... pk). По доказанному, одно из этих двух чисел делится на q1. Если p1 делится на q1, то p1 = q1, потому что p1, как простое, делится только на себя и на 1. Если же p1 не делится на q1, то (p2... pk) делится на q1. После этого можно повторить процесс, отщепив от произведения уже p2. В какой-то момент нам придется либо прийти к противоречию, либо обнаружить pi, совпадающее с q1. После этого в двух разложениях числа n можно сократить на общий множитель справа и слева и продолжать процедуру. Еще короче было бы договориться сразу сократить на все общие сомножители, а потом рассуждать от противного. З2.2 Предположить, что в равенстве p1p2... pk = q1q2... ql все сомножители -- строго различные простые натуральные числа, и на все общие сомножители мы уже сократили, и прийти к противоречию. То, что в разложении натурального числа n одно и то же число может встречаться несколько раз, например, 24 = 2x2x2x3 = 23x3, несколько загромождает рассуждения в общем случае, но в принципе они те же. Нужно только уточнить, что З2.3 Если pk делится на q, p и q просты, то p = q. Как уже упоминалось, единственность разложения на простые множители -- довольно нетривиальное свойство кольца целых чисел (надо оговорить, конечно, что -6 = (-2)x3 = 2x(-3), то есть, в случае целых чисел единственность имеет место лишь с точностью до знака). В свое время будет приведен пример очень похожей конструкции, в которой, однако, единственность разложения на простые множители не будет иметь места. Следуя рекомендации пользователя phantom, приведем здесь евклидово доказательство бесконечности ряда простых чисел. Предположим, что количество простых чисел конечно и равно N. Выпишем их все в порядке возрастания: p1, p2, ..., pN. Рассмотрим число M = p1p2 ... pN + 1. Оно раскладывается (да еще и единственным образом) на простые множители. Заметим, что среди простых делителей числа M не может быть ни одного числа из нашего списка. З2. 4 Почему M = p1p2 ... pN + 1 не делится ни на одно из чисел p1, p2, ..., pN? После того, как ответ на вопрос 32.4 найден, мы приходим к выводу о существовании еще по крайней мере одного простого числа, большего pN. Итак, мы предположили, что простых чисел всего N -- конечное число, и пришли к противоречию. Наконец, в порядке практикума по Алгоритму Евклида (см. вводную лекцию), З2.5 Один фальшивомонетчик задолжал другому 13 фальшивых рублей. Как им рассчитаться, если у них на руках есть только купюры в 26 и в 37 рублей? (Ответ должен иметь вид: должник отдает заимодавцу столько-то (число) таких-то купюр, получает сдачу столько-то (число) таких-то купюр.) (66 Comments |Comment on this)
Saturday, June 28th, 2008
4:20 am	Замечания к вводной лекции -- 1 Замечание первое -- о комбинаторике. Лингвисты говорят, что слово "вероятность" в разных языках исходно имело не тот смысл, в котором оно употребляется в математике. Вероятность в языке связана со степенью человеческого доверия, то есть, ближе к "правдоподобности". Допустим, некто имеет полную информацию о том или ином объекте или событии; он может соврать, говоря о нем, или скрыть часть информации. А слушатель судит о том, насколько вероятен его рассказ -- иногда по признакам, мало относящимся к событию или даже к рассказу. Если же некто бросает кости -- он не знает заранее, что получится, и рассказать ему об этом некому. Из хорошо перетасованной колоды карт, если она не крапленая, вероятность вытащить пиковую даму, по-видимому, равна 1/52. А вероятность вытащить сперва пиковую, а потом бубновую? З1.1 Какова вероятность вытащить сначала пиковую, а потом сразу бубновую даму из хорошо перетасованной колоды карт? 31.2 Изменим задачу. Пусть некто хорошо перетасовал колоду, вынул из нее пиковую даму, внимательно ее рассмотрел, вернул в колоду, потянул карту и вытащил бубнобую даму. Какова вероятность этого гипотетического события -- всего в целом? Возьмем теперь две шестигранные кости, на гранях которых написаны цифры 1, 2, 3, 4, 5, 6. Пусть некто бросает две кости. Интуитивно ясно, что вероятность выбросить две шестерки, получив в сумме 12 очков, меньше, чем вероятность выбросить, к примеру, 7 очков. На каждой кости все исходы (1, 2, 3, 4, 5, 6) равновероятны, но 12 будет только если выпало 6 и 6, а сумму 7 можно получить разными способами: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1, то есть, вероятность выпадения суммы 7, по-видимому, в 6 раз больше, чем вероятность выпадения суммы 12. Чтобы определить вероятность выпадения той или иной суммы, нужно сперва описать пространство всех возможных (если нам повезет, равновероятных) исходов. А потом сосчитать, сколько из них предоставляют данную сумму. Разделить число нужных нам исходов на число всех возможных исходов -- вот и будет искомая вероятность. Конечно, если исходы, составляющие пространство, сами равновероятны. З1.3 Для двух шестигранных костей (пространство исходов -- множество упорядоченных пар (m,n), где числа m и n целые и меняются от 1 до 6) определить: (а) сколько всего равновероятных исходов; (б) какова вероятность набрать сумму 4; (в) какова вероятность набрать сумму 9. Давайте временно отложим теорию азартных игр и будем раскладывать шары по ячейкам. С этого физики часто начинают разговор о статистике. Пусть имеется n пронумерованных ячеек и шары, тоже пронумерованные. Сколькими способами можно разместить какой-нибудь один выбранный нами шар по n ячейкам? Ясно, что таких способов всего n. А два шара -- например, шары 1 и 2? Первый шар можно положить в любую из n ячеек. Для второго остается n-1 незанятых мест. На каждое из n возможных размещений первого шара приходится n-1 способов разместить второй. n раз по n-1 дает всего n(n-1) способов разместить два пронумерованных шара по n ячейкам. З1.4 Сколько существует способов разместить m пронумерованных шаров по n ячейкам, m <= n? А что будет, если стереть с шаров номера? З1.5 Сколькими способами можно разместить m одинаковых шаров по n ячейкам? В задаче З1.5 мы как бы просто помечаем ячейки: выбрали мы ее под шар или нет. То есть, это способ пометить m ячеек из n возможных -- иными словами, мы считали число m-элементных подмножеств n-элементного множества. А вот вопрос, важный в теории кодирования: З1.6 Над казино горят пять лампочек: 1,2,3,4,5. Штирлиц договорился с сообщником передавать ему сигналы, стреляя в лампочки из рогатки. Если все горят -- один сигнал, если первая не горит, а остальные горят -- другой,..., если горят только 3 и 5 -- еще какой-то сигнал, и так далее. Может и все разбить. Сколько всего сигналов может передать Штирлиц? Еще важнее этот вопрос в теории множеств, а также для наших целей, в разговоре о числах. (149 Comments |Comment on this)
Monday, June 23rd, 2008
4:45 am	натуральные и целые числа Что такое число? Пифагор жил две с половиной тысячи лет назад и думал, что число -- это бог. Числа имеют сакральный смысл во всех известных религиях: никого не удивляет, что четные числа, по Пифагору, женские, а нечетные -- мужские (у креационистов обычно "2" -- женское число и число Дьявола сразу). Пифагор, однако, полагал, что все вещи суть числа, и поэтому знал о них еще больше. Правда, о самом Пифагоре и пифагорейцах мало что известно с достоверностью. Говорят, что число 9 у пифагорейцев было символом постоянства, потому что сумма цифр числа, кратного 9, тоже делится на 9. (Вот число 81 делится на 9, и сумма его цифр 8+1 = 9 тоже делится на 9.) Упражнение 1 Доказать, что число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. (То же верно и для числа 3.) Говорят также, что число 8 в пифагорейском сообществе считалось числом смерти, потому что кратные восьми имеют уменьшающуюся сумму цифр. В ряду 8, 16, 24, 32, 40 суммы цифр равны, соответственно, 8, 7, 6, 5, 4 -- а дальше они опять увеличиваются. Однако, давайте обозначим сумму цифр числа x через S(x), и применим эту операцию к числам 48, 56, 64 дважды. Получим S(48) = 12, но S(S(48)) = S(12) = 3, S(S(56)) = S(11) = 2, S(S(64)) = S(10) = 1, так что теперь ряд продолжился почти до самого торжества смерти, и скрытое стремление к ней в числах, кратных 8, проступило наружу. Упражнение 2 Постараться понять, почему с числом 8 так получилось. На самом деле, указанные свойства чисел 8 и 9 имеют смысл лишь в десятеричной системе исчисления. До сих пор речь шла только о натуральных числах: 1, 2, 3, 4, 5, ... Множество натуральных чисел можно задать аксиоматически. Соответствующий набор аксиом называется --- аксиомы Пеано. В них постулируется, что 1 --- натуральное число; что если a --- натуральное число, то a + 1 -- тоже натуральное число; что если a и b --- натуральные числа, и a не равно b, то a + 1 не равно b + 1; что у числа "1" нет "предыдущего" (такого натурального c, что c + 1 = 1) --- иногда, правда, отсчет натуральных чисел начинают с 0, и тогда у "1" есть предыдущее число "0", а у "0" предыдущего нет. Еще аксиомы Пеано постулируют принцип математической индукции: если натуральное число 1 обладает некоторым свойством, и для любого натурального числа a, обладающего этим свойством, верно, что следующее за ним число a + 1 тоже им обладает, тогда все натуральные числа обладают этим же свойством. Пронаблюдаем принцип математической индукции в действии. Докажем, например, следующее утверждение про зрителей в кинотеатре. Пусть в кинотеатре имеется n пронумерованных кресел, и для просмотра фильма в зал приведено n зрителей. Сколькими способами можно рассадить их по местам? Утверждается, что это число равно n! = 1 x 2 x 3 x...x n. (Обозначение n! читается "n факториал". По определению полагают 0! = 1 -- это может выглядеть странно, но это удобно.) Доказательство по индукции 1) Если n = 1, то речь идет об одном зрителе в одноместном зале. Он может занять это место ровно 1! = 1 способом, так что для n = 1 утверждение верно. 2) Пусть для n = k предположение индукции справедливо, то есть, в k-местном зале k зрителей можно разместить k! различными способами. Посмотрим, что это влечет за собой для n = (k+1) зрителя в (k+1)-местном зале. Принесем в k-местный зал еще одно кресло и приведем еще одного зрителя. Любого из (k+1) имеющихся теперь зрителей можно посадить в новое кресло. После того, как это сделано, оставшихся k зрителей, согласно предположению индукции, можно рассадить по старым k креслам k! различными способами. Значит, на каждое из (k+1) возможных вариантов для нового кресла приходится k! способов заполнения остальных кресел, причем, все эти варианты различны. Итак, способов заполнить весь зал получается (k+1) x k! = (k+1)! Итак, согласно последней аксиоме Пеано, это означает, что исходное утверждение о количестве способов рассадить n зрителей по n местам верно для любого натурального n; это количество равно n! В советское время принцип математической индукции обычно формулировали так: если первая в очереди --- женщина, и за каждой женщиной стоит женщина, то все в очереди --- женщины. Упражнение 3 Доказать методом мат. индукции, что для любого натурального n выполняется равенство 1 + 2 + 3 + ... + n = n(n+1)/2. Определение Арифметической прогрессией называется такая последовательность чисел a1, a2, a3, ..., an, ..., что для любого натурального n справедливо соотношение an+1 = an + d, где d --- некоторое число, называемое разностью арифметической прогрессии. Упражнение 3а Получить формулу суммы первых n членов арифметической прогрессии Sn = a1 + a2 + a3 + ... + an (через a1 и d) и доказать ее. Упражнение 4 Докажите методом математической индукции, что для любого натурального n 1 + 2 + 22 + 23 + ... + 2n = 2n+1 - 1 Определение Последовательность чисел a1, a2, a3, ..., an, ..., называется геометрической прогрессией, если для любого натурального n верно an+1 = an x q, где q --- некоторое заданное число, называемое знаменателем геометрической прогрессии. Упражнение 4а Получите формулу для суммы первых n членов геометрической прогрессии (через a1 и q) и докажите ее. Упражнение 5 Пусть имеется n пронумерованных карточек с портретами красавиц, строго различных. Красавицы лежат в ящике. Некто не глядя достает из ящика m < n красавиц и поочередно выкладывает на стол. Сколько вариантов различных наборов по m красавиц возможны в этом случае? Наборы считаются различными, если: (а) порядок важен: наборы 123 и 213 считаются различными (вопрос о числе упорядоченных наборов Anm); (b) порядок неважен: наборы 123 и 213 считаются одинаковыми (вопрос о числе подмножеств длины m у множества из n элементов Cnm). Упражнение 6 Пусть Cnm --- число m-элементных подмножеств n-элементного множества из упражнения 5б. Доказать, что (a + b)n = an + Cn1an-1b + ... + Cnman-mbm + ... + bn (бином Ньютона) Упражнение 7 По определению Cn0 = 1 (в теории множеств есть пустое множество, которое считается подмножеством любого множества, так что число 0-элементных подмножеств n-элементного множества равно 1). Доказать, что Cn0 + Cn1 + ... + Cnm + ... + + Cnn-1 + Cnn = 2n Натуральные числа вместе с операциями над ними можно целиком задать аксиоматически, а потом из свойств операций умножения и сложения выводить, например, возможность сократить на число --- т. е. строго доказывать, что если a + b = c + b, то a = c, но мы этого делать не будем. Это, кстати, действительно трудно: труднее всего доказывать очевидное. Вместо этого, помимо множества натуральных чисел N, рассмотрим множество целых чисел Z (добавим к 1, 2, ... еще 0 и отрицательные числа). Греки ни нуля, ни отрицательных чисел не знали, что породило огромный раздел в средневековой схоластике: все доказательства бытия Божьего, опирающиеся на самоочевидность "первопричины", или "перводвигателя", подразумевали, что числовой ряд, у которого нет начального элемента, помыслить невозможно. А мы его сейчас помыслим. Это ряд ... -2, -1, 0, 1, 2, ... В терминах операций сложения и умножения, обладающих, как известно, свойствами ассоциативности: (a + b) + c = a + (b + c) (ab)c = a(bc) дистрибутивности: (a + b)c = ac + bc а также коммутативности: a + b = b + a ab = ba, мы помыслили о разрешимости такого вот уравнения: x + a = b. Что касается множества натуральных чисел N, в нем это уравнение разрешимо не всегда. Например, уравнение x + 3 = 1 не имеет решения в натуральных числах. А вот для целых чисел оно всегда разрешимо: если x + a = b, причем a, b --- целые, то x = b - a --- вполне определенное целое число. Число 0 есть решение уравнения a + x = a (или x + a = a, что то же в силу коммутативности сложения). В терминах операции сложения, число (-a) является обратным к числу a: a + (-a) = 0, а операция вычитания обратна к операции сложения. Сделаем небольшое отступление о бесконечности. Задача. Имеется гостиница с бесконечным числом номеров: 1, 2, ... Все номера в ней заняты. К метрдотелю является посетитель и просит поселить его в гостиницу. Как быть? Ведь все номера заняты. В гостинице с конечным числом номеров, пусть даже очень большим, посетителю пришлось бы отказать. Иное дело бесконечноместная гостиница. Решение: метрдотель попросит гостя из первого номера переселиться во второй, из второго в третий, из номера k --- в номер k+1 и так далее. Таким образом ни один постоялец не останется без места, а первый номер освободится. Упражнение 8 Пусть имеются две гостиницы A и B, в каждой бесконечное число номеров. Гостиница B сгорела, но ее постояльцы, к счастью, не пострадали. Теперь их нужно разместить в гостинице A так, чтобы не пришлось никого выселять из нее. Как это сделать? (Все номера в гостинице A заняты; так же обстояли дела и в гостинице B до пожара.) После выполнения этого упражнения станет ясно, что во множестве целых чисел Z и во множестве натуральных чисел N, по сути, одинаковое число элементов. Не потому, что бесконечное, а потому, что между тем и другим существует взаимно-однозначное соответствие. Поговорим теперь об операции умножения. Обратной к ней была бы операция деления. Чтобы разрешить уравнение ax = b (в случае ненулевого a), целых чисел уже не хватит: нам придется вводить рациональные. Но перед тем попробуем рассмотреть операцию деления на множестве целых чисел. Делителем целого числа n называется такое число k, что уравнение n = kx имеет решение в целых числах. Разумеется, n всегда делится на 1, на (-1), на n и на (-n); обычно говорят, что n и (-n) --- это несобственные делители числа n. Но бывают и другие случаи, например, все четные числа делятся на 2. Ненависть к числу 13, по-видимому, происходит от Пифагора: это число не имеет несобственных делителей, кроме 1 и (-1) (простое), да еще окружено такими хорошими числами, как 12 и 14 (и не стыдится). Число 13, как и 17, у пифагорейцев считалось очень плохим. Из-за любви к составным числам пифагорейцы не страдали обычной для греков мизогинией, зато оказались сторонниками копирайта (это проявилось в истории иррациональных чисел, до которых мы еще не дошли). Итак, целые числа бывают простые и составные; простые делятся только на себя и на 1 (с точностью до знака), а составные имеют делители помимо этого. Простые числа, кроме 2, все нечетны. Считается, что "0" делится на любое целое число, кроме "0". (А число "1" --- наоборот, ни на что, кроме себя, не делится, поэтому оно ни простое, ни составное.) Разделить целое m на целое n с остатком значит найти такое целое k, что m = nk + r, где r < |n|, r неотрицательно. Говорят, что целое число d есть общий делитель целых чисел m и n, если m делится на d и n тоже делится на d. Наибольший из общих делителей m и n обозначается НОД(m,n). Упражнение 9 Доказать, что если d --- общий делитель чисел m и n, то НОД(m,n) делится на d. Общим кратным целых чисел m и n называется целое число k такое, что k делится на m и k делится на n. Наименьшее положительное (то есть, большее нуля) общее кратное чисел m, n обозначается НОК(m,n). Упражнение 10 Доказать, что если k --- общее кратное чисел m, n, то k делится на НОК(m,n). Последнее, о чем мы поговорим в этот раз --- так называемый Алгоритм Евклида. Пусть m, n --- неотрицательные целые числа, m > n. Рассмотрим переход от пары чисел (m, n) к паре чисел (n, r), где r есть остаток от деления m на n. По определению r < n. Упражнение 11 Доказать, что если m делится на d и n делится на d, то r также делится на d. Алгоритм Евклида заключается в применении операции (m, n) --> (n, r) --> (r, r_1) --> ... (r_1 есть снова остаток при делении n на r) до тех пор, пока на некотором шаге не приходят к паре (d,0), где слева стоит d > 0, а справа 0, как видно из записи. Упражнение 12 Доказать, что Алгоритм Евклида завершится (именно парой вида (d,0)) для любых целых неотрицательных m, n. Упражнение 13 Доказать, что d из последней пары (результат применения Алгоритма Евклида) есть НОД(m, n). Из уважения к Пифагору, Упражнение 14 Рассмотрим уравнение mx + ny = 1, где m, n --- заданные целые числа, а x, y --- неизвестные, но тоже целые. Доказать, что это уравнение имеет решения в целых числах тогда и только тогда, когда НОД(m,n) = 1. (В этом случае говорят, что m и n взаимно просты.) (216 Comments |Comment on this)