Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
Какие из следующих утверждений верны? а) Любое положительное четное число раскладывается в произведение четнопростых чисел. б) Разложение положительного четного числа в произведение чет- нопростых чисел единственно с точностью до порядка сомножителей. Укажите, какие из следующих чисел совершенные: а) б) в) г) Указания и решения. а) Пусть нелюбое натуральное число является произведением простых чисел. Тогда возьмем наименьшее натуральное число n, не являющееся произведением простых. Оно непростое, значит, составное. Тогда n = ab для некоторых неравных единице чисел a и b. Так как n > a и n > b, то ввиду минимальности n числа a и b являются произведениями простых. Значит, n является произведением простых. Мы пришли к противоречию с предположением. б) По задаче а любое натуральное число n представляется в виде n = p 1 · p 2 · . . . · p m , где все числа p 1 , p 2 , . . . , p m — простые. Далее, многократно применяем следующую операцию если нам месте в этом произведении стоит число, равное числу p 1 , а нам месте стоит число, неравное, то мы их меняем местами. В конце концов, все множители в произведении, равные p 1 , окажутся слева. Получим, где все числа p i j неравны Тоже можно сделать с остальными множителями и получить искомый вид. в) Пусть утверждение задачи неверно. Возьмем наименьшее число имеющее два канонических разложения = p a 1 1 · p a 2 2 · . . . · p a m m = q b 1 1 · q b 2 2 · . . . · q b k k Линейные диофантовы уравнения 77 В силу минимальности n, любое число p неравно любому числу q иначе можно было бы поделить обе части равенства на них и получить меньшее число, имеющее два различных канонических разложения. Лемма. Пусть p|ab. Тогда p|a или Доказательство. Будем доказывать лемму в эквивалентной формулировке если для фиксированного числа a число b — наименьшее положительное, такое что p|ab и b не делится на p, то Ясно, что если p|ab, то p|a(b − p). Поэтому, ввиду минимальности b, получаем b < p. Так как p|ab, то ab > p. Рассмотрим числа b, 2b, . . . . . . , (a − 1)b, ab. Тогда найдется такое число i, что (i − 1)b < p 6 ib. Если ib = p, то b = 1, откуда p|ab = a. Имеем тогда ib > Заметим, что ib − p < b и p|a(ib − p). Число b — наименьшее положительное число, такое что p|ab и b не делится на p. Поэтому число ib − p равно нулю. Номы получали, что ib > p — противоречие. Значит, b = и Возьмем какое-нибудь число p из левой части равенства. Тогда p i |p a 1 1 · p a 2 2 · . . . · p a m m = q b 1 1 · q b 2 2 · . . . · q b k Значит, по лемме p i |q b 1 1 · q b 2 2 · . . . · q или p i |q b k k . Отщепляя множители далее, получим, что число p делит одно из чисел q b j j , те. одно из чисел q j . Так как q простое, то q j = p i . Противоречие. (а) 1995 = 5 · 399 = 5 · 3 · 133 = 5 · 3 · 7 · 19 (= 5 · 7 · б) Подсчитаем показатель при степени двойки, входящей в каноническое разложение 17! = 1 · 2 · 3 · . . . · 17. Каждое второе число в этом произведении делится на 2. Поэтому можно вынести 2 8 . Каждое четвертое число делится нате. можно вынести еще 2 4 . Аналогично можно еще вынести 2 и 2 1 . Оставшиеся множители нечетные. Поэтому искомая степень двойки — это 2 8+4+2+1 = 2 15 . Рассуждая аналогично, получаем = 2 15 · 3[ 17 3 ] + [ 17 9 ] · 5[ 17 5 ] · 7 2 · 11 · 13 · 17 = 2 15 · 3 6 · 5 3 · 7 2 · 11 · 13 · в) Аналогично пункту б) имеем = 2[ 11 2 ] + [ 11 4 ] + [ 11 8 ] · 3[ 11 3 ] + [ 11 9 ] · 5[ 11 5 ] · 7 · 11 = 2 8 · 3 4 · 5 2 · 7 · 11, 22! = 2[ 22 2 ] + [ 22 4 ] + [ 22 8 ] + [ 22 16 ] · 3[ 22 3 ] + [ 22 9 ] · 5[ 22 5 ] · 7[ 22 7 ] · 11 2 · 13 · 17 · Поэтому 22 = 22! 11! · 11! = 2 19−16 · 3 9−8 · 5 4−4 · 7 3−2 · 13 · 17 · 19 = 2 3 · 3 · 7 · 13 · 17 · 19. 5. в) Ответ [a, b, c] = a · b · c · (a, b, c) (a, b) · (b, c) · (c, a) Гл. 3. Миникурс по теории чисел Линейные диофантовы уравнения (8–9) 1. а) Кузнечик передвигается вдоль прямой прыжками по 6 см и 10 см (в обе стороны. В какие точки он сможет попасть? б) На острове Утопия в каждой неделе 7 дней, а в каждом месяце день. Томас Мор прожил там 365 дней. Докажите, что среди них был понедельник го числа. в) Миша прибавил к дню своего рождения, умноженному на 12, месяц своего рождения, умноженный на 31. Получилось 670. Когда у Миши день рождения (найдите всевозможные решения)? г) Решите уравнение в целых числах nx + (2n − 1)y = 3 (n — параметра) Любую сумму, большую 23 пиастров, можно разменять монетами пои пиастров. б)* Найдите наименьшее m, такое что любую сумму, большую m пиастров, можно разменять монетами пои пиастров. а) Для любого n число n 5 − n делится наб) Если число a делится на 2, на 3 и на 5, то a делится на 30 (докажите по определению делимости, не используя основной теоремы арифметики, ибо обычно при доказательстве основной теоремы арифметики используется результат, близкий к тому, который нужно доказать. а) Для любого неотрицательного n число 20 2n + 16 2n − 3 2n − делится наб) Если число a делится на 17 и на 19, то a делится на 323 (см. замечание ка. а) Уравнение 19x + 17y = 1 имеет решение (здесь и далее — в целых числах). б) Для любых чисел a, b и c уравнение ax + by = c имеет решение тогда и только тогда, когда c делится на (a, в) Пусть пара (x 0 , y 0 ) — решение уравнения ax + by = c. Тогда множество решений этого уравнения есть n x = x 0 + b (a, b) t, y = y 0 − a (a, b) t t ∈ Z o 6. а) Лемма о представлении НОД. Для любых чисел a и b существуют такие числа x и y, чтоб) Если (c, b) = 1 и b|ac, тов) Если p простое и p|ab, то p|a или г) Если (b, c) = 1, b|a и c|a, то bc|a. 7. Алгоритмом Евклида называется процесс построения изданной пары a 0 , последовательности пар a k , b последующему правилу Линейные диофантовы уравнения 79 если b k 6= 0, то a k+1 = b и b равно остатку отделения на b если b k = 0, то следующие пары не строят, а говорят, что алгоритм завершил работу за k шагов. а) (a, b) = (a − b, б) (a, b) = (b, r), где r — остаток отделения на в) Докажите, что для любых чисел a и b 6= 0 существует такое что алгоритм Евклида завершает работу за n шагов те. Для этого n выполнено a n = (a, г) Укажите способ нахождения хотя бы одного решения (x 0 , y 0 ) уравнения (любой метод Эйлера, по алгоритму Евклида или через разложение в цепную дробь). д)* Составьте блок-схему алгоритма решения уравнения ax + by = c. 8. а) Найдите (2 32 + 1, 2 16 + б) Найдите (2 91 − 1, 2 63 − в) Для каких чисел a, b, n число n a + 1 делится на n b − 1? 9. Из угла бильярдного поля под углом выпускают шарик. Собьет ли он кеглю, стоящую в (2; 1), если размеры доски а) 12 × 18; б) 17 × 18? 10. а) Решите системы сравнений ≡ −1 (7), x ≡ 15 (5), x ≡ 6 (12), x ≡ 8 (20), x ≡ 7 (8), x ≡ 18 (25), 6x ≡ 2 (7). б) Китайская теорема об остатках. Если числа m 1 , . . . , m попарно взаимно просты, то для любых a 1 , . . . , a существует такое x, что x ≡ a i (m i ) для любого i = 1, . . . , в) Придумайте алгоритм нахождения такого г) Найдутся 1000 идущих подряд чисел, ни одно из которых не является степенью простого. Линейные диофантовы уравнения с несколькими переменными. а) На какие клетки может попасть шахматная фигура тя- нитолкай, которая может совершать следующие передвижения по бесконечной клетчатой доске: на 2 клетки вверх и на 5 вправо; на 2 клетки вниз и на 5 влево; на 3 клетки вверх и на 8 вправо; на 3 клетки вниз и на 8 влево? б) Как изменится ответ для конечной доски n × n клеток? 2) Определение сравнимости см. с. 84. Гл. 3. Миникурс по теории чисел в Придумайте алгоритм решения в целых числах уравнения a 1 x 1 + . . . + a n x n = Контрольные вопросы. Кузнечик передвигается вдоль прямой прыжками по 6 см и 10 см (в обе стороны. Сможет ли он попасть в точку, находящуюся от начальной на расстоянии а) 3,5 см; б) 7 см; в) 14 см. Сколько решений в целых числах имеет уравнение ax + by = = (a, b) для данных ненулевых a и а) Ни одного; б) одно; в) бесконечно много; г) зависит от конкретных чисел a и Указания и решения. а) Ответ кузнечик сможет попасть в клетки, находящиеся начетном расстоянии от начала. Решение. Кузнечик прыгает начетное расстояние, поэтому он может отдалиться от начальной точки только начетное расстояние. Докажем теперь, что он может попасть в точку на расстоянии 2n справа от начала. Ему достаточно сделать 2n прыжков вправо на и n прыжков влево на 10: 6(2n) − 10n = 2n. Для точки слева от начала рассуждения аналогичны. б) Возьмем 7 подряд идущих полных месяцев, в течение которых Томас Мор был на острове. Занумеруем их числами от одного до семи в порядке следования. Также занумеруем дни недели. Нужно показать, что одно из тринадцатых чисел будет первым днем недели. Число дней водном месяце имеет остаток 3 отделения на 7. Значит, если тринадцатое число го месяца — этой день недели, то тринадцатое число + го месяца — этой день недели по модулю 7. Пусть тринадцатое число первого выбранного месяца й день недели. Тогда дни недели тринадцатых чисел выбранных месяцев это k, k + 3, k + 6, k + 2, k + 5, k + 1, k + 4. Среди них встречаются все дни недели. Значит, один из них — понедельника) Сумму в n пиастров, где 24 6 n < 29, можно разменять монетами в пять и семь пиастров 24 = 2 · 5 + 2 · 7, 25 = 5 · 5, 26 = 5 + 3 · 7, 27 = 4 · 5 + 7, 28 = 4 · Пусть у нас n пиастров, где n > 24. Докажем утверждение задачи по индукции. Для n < 29 мы все выяснили. А если n > 29, то n − 5 пиастров можно разменять по предположению индукции Целые точки под прямой 3. б) Указание. 3a − 2a = a, поэтому a делится на 6. 6a − 5a = поэтому a делится на Решение. По условию 2|a, 3|a и 5|a. Поэтому 6|3a и 6|2a. Значит − 2a = a. Аналогично 30|6a и 30|5a. Значит, 30|6a − 5a = а) Разложим число n 5 − n на множители n = n(n − 1)(n + 1)(n 2 + Число n(n − 1) делится на 2. Число (n − 1)n(n + 1) делится на 3. Если ни одно из чисел n, (n − 1), (n + 1) не делится на 5, то остаток отделения числа n на 5 равен 2 или 3. Тогда n 2 + 1 делится на Имеем n 5 − n делится на 2, на 3 и на 5. По пункту б) получаем, что n 5 − n делится на 30. 4. а) Указание. 19a − 17a = 2a, поэтому 2a делится на 323; 17a − − 8 · 2a = a, поэтому a делится на Решение. По условию 17|a и 19|a. Поэтому 17 · 19|17a и 19 · Значит, 17 · 19|(19a − 17a) = 2a. Имеем 17 · 19|(17a − 8 · 2a) = б) Так как a n − b n = (a − b)(a n−1 + a n−2 b + . . . + b n−1 ), то a n − b делится на a − b. Поэтому 2n − 1 + 16 2n − 3 2n = (20 2n − 3 2n ) − ((16 2 ) n − делится на 17. Аналогично 2n − 1 + 16 2n − 3 2n = (20 2n − 1) + ((16 2 ) n − (3 делится на 19. По пункту а) получаем, что 20 2n − 3 2n + 16 2n − 1 делится на 30. 5. а) Если 19x + 17y = 1, то 17|(19x − 1). А также 17|(2x − 1). Значит, можно взять x = 9. Подставляем x = 9 в равенство и получаем = 1 − 19 · 9 = −170, откуда y = б) Указание. Можно считать, что a > b > 0 и тогда доказывать индукцией по a + b. 6. а) См. 5 б). б) Указание. Докажите индукцией по c. В шаге индукции поделите b нас остатком. Другое указание. Выведите из а. а) Указание. Докажите, что (n a − 1, n b − 1) = n (a,b) − 1. 10. а) Ответы x ≡ 10 (35), ∅, x ≡ 943 (г) Например, 10 7 ! + 2, 10 7 ! + 3, . . . , 10 7 ! + 1001. Вместо 10 7 ! можно взять число, которое находится по китайской теореме об остатках Гл. 3. Миникурс по теории чисел Целые точки под прямой (Эти задачи подводят школьника к алгоритму вычисления суммы f α (n) = n P k=1 [αk], те. количества целых точек под прямой y = αx». Через и {x} обозначаются целая и дробная части числа x соответственно. Алгоритм строится в задачах 2 а)–в), задача 1 полезна для разогрева. Найдите f α (n) для а) целого б) целого в) целого г) α = a/n для данных целых a и д) Найдите lim те, кто не знают, что это такое, могут пропустить эту задачу. а) f α (n) = f {α} (n) + 1 2 [α]n(n + б) f α (n) + f 1/α ([nα]) − [n/q] = n[nα], где q — знаменатель несократимой дроби, представляющей число α, если α рационально, и q = те, если α иррационально. в) Найдите алгоритм вычисления суммы г) Найдите алгоритм вычисления суммы Контрольные вопросы. Найдите [−2, а) б) в) −3. II. Найдите а) б) б) 14. III. Существуют ли такие различные α и β, чтобы при любом n выполнялось равенство f α (n) = а) Существуют; б) не существуют. Указания и решения. а) Ответ α · n(n + Решение. Сначала вычислим сумму 1 + 2 + . . . + n. Заметим, что i + (n + 1 − i) = n + 1. В данной сумме сгруппируем е и (n + 1 − е слагаемые в пары для всех i = 1, 2, . . . , h n 2 i . Получаем n P k=1 k = n · (n + 1) 2 Целые точки под прямой 83 Поэтому n X k=1 [αk] = α n X k=1 k = α · n(n + б) Ответ α · n(n + 1) 2 − h n + 1 2 i . Возможны другие формы записи ответа, например, [α] n(n + 1) 2 + {α} n 2 + (Решение. Если α — целое, то по задаче 1 а = α · n(n + Теперь для произвольного полуцелого (ноне целого) α: [α] + [2α] + [3α] + . . . + [nα] = α − 1 2 + 2α + 3α − 1 2 + . . . = = α · n(n + 1) 2 − h n + 1 2 i в) Ответ Для целого α см. выше. Для нецелого α имеем f α(n) = α · n(n + 1) 2 − h n + 1 3 i при n 6= 3k + 1, α · n(n + 1) 2 − h n 3 i − {α} при n = 3k + Указание. Для нецелого α имеем + [2α] + [3α] = α + 2α + 3α − 1 3 − 2 3 = 6α − 1. 2. б) Указание. Посчитайте количество целых точек в прямоугольнике в) Указание) = n h 2n 3 i + h n 3 i − f 3/2 h 2n 3 i ; f 3/2 h 2n 3 i = 1 2 h 2n 3 ih 2n 3 i + 1 + f 1/2 h 2n 3 i ; f 1/2 h 2n 3 i = h 2n 3 ih n 3 i + h n 3 i − f 2 h поскольку h [x] n i = h x n для целого n > 0 и, значит n 3 i ; f 2 h n 3 i = h n 3 ih n 3 i + 1 Гл. 3. Миникурс по теории чисел Замечания Частный случай равенства 2 б) (на котором основан предлагаемый алгоритм) для положительных нечетных взаимно простых чисел p < q, α = p/q и n = (q − 1)/2 (тогда [nα] = (p − 1)/2) появляется при доказательстве квадратичного закона взаимности доказательство общего случая аналогично. Сумма из 2 г) вычислена (более громоздким способом, чем предложенный здесь) в статье Добровольская В. Н. Неполные суммы дробных долей // Чебыш¨евский сборник. 2004. Т. 5, № 2 (С. Малая теорема Ферма (Пусть m— натуральное число. Числа a и b называются сравнимыми по модулю m 6= 0, если a − b делится на m (или a и b имеют одинаковые остатки отделения на m). Обозначение a ≡ b mod m или a ≡ b mod Сравнимость a ≡ b (m) равносильно тому, что a и b имеют одинаковый остаток при делении на Сравнимость сохраняется при почленном сложении, вычитании, умножении, возведении в степень, делении на число, взаимно простое с модулем. Сравнение является отношением эквивалентности. Пример 16 = (3 2 ) 8 = 9 8 = (9 2 ) 4 = 81 4 ≡ 12 4 = (12 2 ) 2 ≡ 6 2 ≡ 13 mod 23. 1. Последовательность остатков отделения) на b 6= периодична начиная с некоторого места. а) Обозначим Z 97 = {0, 1, . . . , 96}. Рассмотрим отображение f : Z 97 → Z 97 , заданное так f (a) равно остатку отделения числа 14a на 97. Тогда f — взаимно однозначное соответствие. Указание. Достаточно доказать, что f сюръективно. Иногда как раз доказывают, что f инъективно, но необходимая для этого основная лемма арифметики обычно доказывается через разрешимость уравнения + 14y = 1, из которой сразу вытекает сюръективность отображения б) (14 · 1) · (14 · 2) · . . . · (14 · 96) ≡ 96! mod в) 14 96 ≡ 1 mod 97. г) Малая теорема Ферма. Если p простое, то n p − n делится на p для любого целого n. д) Малая теорема Ферма (alio modo). Если p простое и n не делится на p, то n p−1 ≡ 1 mod p. 3) Виноградов И. М. Основы теории чисел. Вопрос б к гл. II и V.2.l. Малая теорема Ферма 85 е) Докажите, что для простого p число C k делится на p для k = = 1, 2, . . . , p − 1, и получите из этого иное доказательство малой теоремы Ферма. 3. Найдите остаток отделения а) 2 наб на в) 8 наг над на е) 2 60 + 6 на 143. 4. а) Если p простое и p > 2, то 7 p − 5 p − 2 делится наб) Число 11 . . . 1 | {z делится на в) Если p и q — различные простые числа, тог) Число 30 239 + 239 30 составное. Далее буквами p, q, p 1 , . . . , p обозначаются различные простые числа. а) p − 1 делится на наименьшее k > 0, для которого a k ≡ 1 mod б) Длина периода десятичной дроби 1/p делит p − в) Если p > 2 и 2 p − 1 делится на d, то d − 1 делится на 2p. Иными словами, любой простой делитель числа 2 p − 1 имеет вид 2kp + г Используя равенство 641 = 5 4 + 2 4 = 1 + 5 · 2 7 , докажите, что число 2 2 5 + 1 составное. д)* Верно ли, что если n p − n делится на p для любого целого n, то p простое (То есть верна ли теорема, обратная к малой теореме Ферма в некоторой формулировке последней. а) Если p 6= q и n не делится ни на p, ни на q, то n (p−1)(q−1) − делится наб) Если n не делится на p, то n p α (p−1) − 1 делится на p α+1 в) Теорема Эйлера. Если n взаимно просто сито n ϕ(m) − 1 делится наг) равно количеству чисел от 1 до m, взаимно простых се) Известно, что n — нечетное число от 3 доне делящееся на Как быстро вычислять неизвестное n по известному n 7 mod 50? (Эта задача показывает, почему для шифрования так важно знать разложение числа на простые множители.) Зачетные задачи 2 г 3 б)–е); 4 а в 5 а)–в); 6 а в. Из них письменное а 5 а 6 б). Контрольные вопросы. Найдите остаток отделения на а) б) в) г) 4. Гл. 3. Миникурс по теории чисел. Найдите остаток отделения на а) б) в) г) 4. III. Какие из следующих утверждений верны для любых a, b, а) a ≡ a mod б) a ≡ b mod m ⇐⇒ b ≡ a mod в) если a ≡ b mod m итог) если a ≡ b mod m и c ≡ d mod m, то a + c ≡ b + d mod д) если a ≡ b mod m и c ≡ d mod m, то ac ≡ bd mod е) если a ≡ b mod m, то для любого c 6= 0 ac ≡ bc mod ж) a ≡ −a mod з) любое число сравнимо с суммой своих цифр по модулю 9 и по модулю Указания и решения. а) 14 · 7k ≡ k mod б) (14 · 1) · (14 · 2) · . . . · (14 · 96) ≡ f(1) · f(2) · . . . · f(96) = 96! mod в) Сократите равенство изб) на 96!. 3. Ответы а) 1; б) 9; в) 7; где) Квадратичные вычеты (Цель этого цикла задач — мотивировать проблему разрешимости сравнения x 2 ≡ a mod p и наметить ее решение для простого p. Я старался показать, как был придуман квадратичный закон взаимности (другой способ придумать его сообщил мне А. Я. Канель-Белов). 1. а) Выясните, какие остатки могут быть у квадратов (целых) чисел при делении наб) Если a 2 + делится на 3 (на 7), то a и b делятся на 3 (на в) Число вида 4k + 3 не представимо в виде суммы двух квадратов. г) Число, имеющее простой делитель видав нечетной степени, не представимо в виде суммы двух квадратов. д)* Остальные целые числа представимы в виде суммы двух квад- ратов. е) Существуют сколь угодно большие тройки последовательных чисел, ни одно из которых не является точным квадратом. ж) Существует бесконечно много чисел, не представимых в виде суммы трех квадратов. Через p обозначается нечетное простое число. Латинские буквы обозначают целые числа или вычеты по модулю p (что именно — видно из контекста Квадратичные вычеты 2. Решите уравнения в целых числах (а)—ж)). а) В нечетных числах x 2 1 + x 2 2 + x 2 3 + x 2 4 + x 2 5 = б) 3x = 5y 2 + 4y − в) x 2 + y 2 = где ж) x 2 + 1 = py, где p = 4k + з) Если p = 4k + 3 делит a 2 + b 2 , то p|a и p|b. 3. Сведите уравнение py = at 2 + bt + c к сравнению x 2 ≡ a mod Остаток a 6= 0 называется квадратичным вычетом (квадратичным невычетом) по модулю p, если сравнение x 2 ≡ a mod p разрешимо (неразрешимо). Слова по модулю p» далее опускаются. а) Для некоторых a и p оба числа a и −a являются квадратичными вычетами. б) Сравнение x 2 ≡ a 2 mod p имеет ровно два решения для a, не делящегося на в) Число квадратичных вычетов равно числу квадратичных невы- четов и равно p − 1 2 5. а) Для любого a 6= 0 существует и единственно b, такое что ab ≡ 1 mod p. Обозначение b = б) Решите сравнение x ≡ x −1 mod p. в) Теорема Вильсона. (p − 1)! + 1 делится на p. 6. а) Если a 6= 0 — квадратичный вычет, то тоже квадратичный вычет. б) Число квадратичных вычетов четно тогда и только тогда, когда является квадратичным вычетом. в) Уравнение x 2 + 1 = py разрешимо в целых числах при p ≡ 1 mod и неразрешимо при p ≡ 3 mod 4). 7. а) Произведение двух квадратичных вычетов является квадратичным вычетом. б) Произведение квадратичного вычета и квадратичного невычета является квадратичным невычетом. в) Произведение двух квадратичных невычетов является квадратичным вычетом. Если число p = 8k + 5 простое, то а) 2 4k+2 ≡ −1 mod б) уравнение x 2 − 2 = py неразрешимо в целых числах Гл. 3. Миникурс по теории чисел. Если число p = 8k + 1 простое, то а) 2 4k ≡ 1 mod б) уравнение x 2 − 2 = py разрешимо в целых числах. а) Если число p = 8k ± 1 простое, то 2 (p−1)/2 ≡ 1 mod б) Если число p = 8k ± 3 простое, тов) Для каких простых чисел p разрешимо в целых числах уравнение x 2 |