alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
 Скачать 2 Mb.
|
|
оно составляет один день в 3323 года. Рассмотрите прямоугольник со сторонами и воспользуйтесь геометрической интерпретацией алгоритма Евклида из задачи. В Юлианском стиле ошибка в одни сутки накапливается залет. [365; 4, 7, 1] = 365 8 33 . Омар Альхайями ввел цикл из 33 лет, в котором семь раз високосный год считался четвертый, а восьмой раз високосный год был не четвертый, а пятый. Таким образом, здесь имеется лишних суток в 33 года. Ошибка в одни сутки в этом календаре набегает примерно залет. Точнее сказать нельзя, потому что сама продолжительность астрономического года меняется из-за замедления вращения Земли вокруг своей оси. Этот эффект задается приближенной формулой Саймона Ньюкома: 1 год = (365,24219879 − 0,0000000614 · (n − 1900)) суток, где n — номер года. а) √ 33 ; б) √ 34 ; в) (1 + √ 17)/2 3.161 . а = [1; 2] ; б = [1; 1, 2] ; в) 1/2 + √ 7 = [3; 6, 1, 6, 5] 3.163 . 97/56. 3.164 . Докажем сначала, что всякая чисто периодическая цепная дробь = [a 0 ; a 1 , . . . , a k−1 , задает квадратичную иррациональность. При решении задачи 3.149 а) была получена формула ( 13.4 ), которая выражает зависимость подходящей дроби от последнего неполного частного. Заменяя в этой формуле a k на α, приходим к равенству = αp k−1 + p k−2 αq k−1 + q которое дает квадратное уравнение для α: α 2 q k−1 + α(q k−2 − p k−1 ) − p k−2 = Таким образом, α — квадратичная иррациональность. Осталось заметить, что если = [b 0 ; b 1 , . . . , b m , то β также является квадратичной иррациональностью Ответы, указания, решения 3.166 . Проверьте, что последовательность p n = (1 + √ 2) n+1 − (1 − √ 2) n+1 удовлетворяет начальным условиями рекуррентному уравнению p n+2 = 2p n+1 + p n , а последовательность q n = (1 + √ 2) n − (1 − √ 2) n 2 √ 2 — начальным условиями рекуррентному уравнению q n+2 = 2q n+1 + q n . Отсюда будет следовать, что p n /q n — я подходящая дробь к числу [2] = 1 + √ 2 3.167 . Предположим сначала, что α — число иррациональное и p n /q n — подходящие дроби кВ этом случае последовательность знаменателей стремится в бесконечность, значит для некоторого n будут выполнены неравенства q n 6 q 6 q n+1 . При таком выборе n дробь p/q может совпасть только с й подходящей дробью. Покажем, что другие варианты невозможны. Действительно, если это не так, то число p/q попадает в один из трех интервалов (− ∞; p n /q n ) , (p n /q n ; p n+1 /q n+1 ) , (p n+1 /q n+1 ; ∞) (будем считать, что p n /q n < p n+1 /q n+1 ). В первом случае из неравенств 2q 2 > p q − α > p q − p n q n > 1 qq следует оценка q n > 2q , которая противоречит выбору n. Во втором случае имеем n q n+1 = p n+1 q n+1 − p n q n = p n+1 q n+1 − p q + p q − p n q n > 1 q q n+1 + 1 q q откуда q > q n + q n+1 , что также противоречит выбору n. В третьем случае из неравенств 2q 2 > p q − α > p q − p n+1 q n+1 > 1 q q n+1 , 1 qq n 6 p n q n − p q 6 p n q n − α + α − p q 6 1 q n q n+1 + 1 получаем оценки q n+1 > 2q и 1 6 q q n+1 + q n 2q . Отсюда 1 < q 2q + q 2q = Таким образом, ни один из этих трех случаев невозможен, и p q = p n q В случае рационального α = a следует воспользоваться тем, что при p q 6= a b a b − p q > 1 bq Ответы, указания, решения. Предположим, что для некоторой дроби p/q выполняется неравенство − p q < 1 Согласно задаче, число p/q является подходящей дробью к √ 2 Пусть p/q = P n /Q n . Тогда − p q = lim k →∞ P n+k Q n+k − P n Q n = lim k →∞ |P n+k Q n − Рассмотрим последовательность чисел a n = |P n+k Q n − P n Q n+k |. Она удовлетворяет начальным условиями рекуррентному соотношению a k = 2a k−1 + a k−2 (k > 2). Поэтому числа a совпадают со знаменателями подходящих дробей кто есть d Чтобы получить противоречие с исходным предположением, достаточно доказать неравенство Свойства чисел Q n похожи на свойства чисел Фибоначчи. В частности, для них можно доказать равенство, аналогичное соотношению из задачи Q k−1 Q n+1 − Отсюда Q k−2 Q n = 1 Q n+1 /Q n + Остается заметить, что и 6 1 2 3.170 . Примените алгоритм Евклида к многочленами. Число α = [a 0 ; . . . , a является корнем многочлена f(x) = = q n x 2 + (q n−1 − p n )x − p n−1 . Вторым корнем будет сопряженная иррациональность. Так как f(0) = −p n−1 < и f(−1) = p n − p n−1 > 0 , то второй корень принадлежит интервалу (−1; 0). Ответы, указания, решения 191 Глава 4 4.3 . Если a и b — нечетные числа, то равенство a 2 + b 2 = невозможно, поскольку не может давать остаток 2 при делении на 4. 4.5 . Каждая кость домино накрывает одну черную и одну белую клетки доски. Но из шахматной доски вырезаны две черные клетки. Ответ: нет. Рассмотрите множества четных и нечетных чисел. Проследите за четностью числа стаканов, которые стоят вверх дном. Не обращайте внимания на угловые и центральные клетки. Воспользуйтесь тем, что при любых слияниях амеб, четность суммарного количества амеб типов A и B не меняется. Тоже самое можно сказать про типы A, C и B, C. Ответ останется амеба типа B. 4.21 . Расставьте амеб сначала как на рисунке 1 Рис. Рис. Если вначале игры снята фишка с центральной клетки, то, рассуждая как в задаче, получаем, что последняя фишка может остаться только на клетке, помеченной буквой A. Но амеб с самого начала можно расположить и по-другому (смотрите рис. Клеток, которые оба раза оказываются помечены буквой A оказывается 5 и это именно те клетки, которые указаны в условии задачи. В расширенной таблице сумма элементов в любом столбце ив любой строке четная. Если изменить один из элементов, то изменятся суммы для одной строки и одного столбца (станут нечетными. Чтобы исправить такую ошибку, надо будет изменить тот элемент таблицы, который находится на пересечении строки и столбца с нечетными суммами. Минимальное число ошибок, которые нельзя обнаружить — Например, можно изменить все четыре цифры в сообщении 0111. При этом суммы во всех строках и столбцах останутся четными. p 2 − 1 = (p − 1)(p + 1) . Четные числа p − 1 и p + 1 отличаются на 2, поэтому одно из них делится на 4. 4.24 . Такое число делится на 111 = 3 · 37. Ответы, указания, решения. а) 8 делителей можно найти среди чисел вида 11 . . . 1 (n единиц) выбирая n = 1, 2, 3, 6, 331, 662, б) Воспользуйтесь равенством 111 = 1001 · 111 = 3 · 7 · 11 · 13 · 37. 4.26 . 2 3k + 1 ... 2 k + 1 , 2 3k − 1 ... 2 3 − 1 4.28 1 k + 1 p − k = p k(p − k) 4.29 . m/n = 5/2. 4.30 . Подставьте c = 6k − a − b или рассмотрите остатки отделения на 2 и на 3. 4.31 . Проследите затем, как меняется предпоследняя цифра у чисел вида 11 n 4.32 . Пусть b и c — длины второго катета и гипотенузы. Возможны следующие варианты (b, c) = (8, 17), (35, 40), (36, 39) и (112, Ответа, б) Представьте уравнение в виде (1 + x)(1 + x 2 ) = 2 y . Ответ (x, y) = (0, 0), (1, 2). 4.34 . k 1999 + (17 − k) 1999 ... 17 4.35 . Разобьем номера всех счастливых билетов на две группы. В первую группу отнесем номера, которые состоят из двух равных трехзначных чисел (например, 765765). Все остальные номера отнесем ко второй группе. Поскольку abcabc = abc · 1001 = abc · 7 · 11 · то каждый номер из первой группы делится на 13, а, значит, делится на 13 и сумма всех номеров из первой группы. Рассмотрим номер abcdef из второй группы (abc 6= def). Вместе с этим номером во второй группе находится и номер defabc. Таким образом, все номера из второй группы разбиваются на пары. Сумма номеров в каждой паре делится на 13, так как abcdef + defabc = (abc + def) · 1001 = (abc + def) · 7 · 11 · Поэтому делится на 13 и сумма всех номеров из второй группы. Рассмотрите остаток, который такое число будет давать при делении на 9. 4.39 . а) Не может, так как 2004 · 4 не делится наб) Может. Можно взять 401 пару квадратов с таким расположением чисел (1, 2, 3, 4) и (4, 3, 2, 1). 4.42 . C k p = p! k!(p − k)! . Если 0 < k < p, то (k!(p − k)!, p) = 1, поэтому число p в числителе сократиться не может Ответы, указания, решения 4.43 . Пусть n составное число и p — один из его простых делителей. Представим n в виде n = p α m , где (m, p) = 1. По формуле Лежандра (см. задачу) находим, что p входит в разложение C p в степени − 1 , поэтому n - C p n 4.45 . Воспользуйтесь результатом задачи 4.46 . Нет. Например, если мы на первом шаге объединяем две первых кучки, то дальше в любой из получающихся кучек количество камней будет кратно 5. 4.47 . Воспользуйтесь тем, что среди чисел a 1 , a 1 +a 2 , . . . , a 1 +a 2 +. . . . . . + a либо одно делится на n, либо два дают равные остатки при делении на n. 4.48 . Покажем, что среди 10 последовательных чисел найдется такое, которое не делится на числа 2, 3, 5, 7. Оно и будет удовлетворять условию задачи. Действительно, среди этих чисел 5 делятся на 2. Среди оставшихся чисел не более 2 делятся на 3, и не более одного — на 5 и Таким образом исключается не более 9 чисел. Среди чисел 1, 2, . . . , 99 есть 50 нечетных и 49 четных. Это значит, что на одной из карточек на обеих сторонах будут написаны нечетные числа. а) Ничего. б) Это соотношение справедливо для всех целых a и b. 4.51 . Воспользуйтесь равенствами (a + c) − (b + d) = (a − c) + (b − d), ac − bd = c(a − b) + b(c − d) 4.52 . Согласно определению, класс ¯ a состоит из таких чисел b, что b ≡ a (mod m) или b − a = mt. Таким образом, каждое число из ¯ a должно иметь вид mt + a. 4.53 . Пусть ¯ a = ¯ b . Рассмотрим элемент c, принадлежащий обоим этим классам. Согласно предыдущей задаче, для некоторых целых и будут выполняться равенства c = a + mt 1 , b = a + mt 2 . Отсюда a − b = m(t 2 − t 1 ) , то есть b ≡ a (mod m). 4.54 . По принципу Дирихле такие числа попадают по одному в каждый из классов по модулю m. 4.55 . При (a, m) = 1. 4.57 . При (m, c) = 1. 4.59 . Первый игрок должен следить затем, чтобы количество камней, оставшихся после его хода, давало остаток 1 при делении 6. 4.62 . Если одна фирма приобрела x килограммов яблок, то вторая, поэтому масса приобретенных яблок должна делится на 3. 4.64 . Дискриминант дает остаток 5 при делении на 8, и поэтому не может быть полным квадратом Ответы, указания, решения. От числа b · 10 5 + a делается переход к числу 10a + b. При делении на 7 эти числа дают остатки 5b + a и 3a + b. Утверждение задачи следует из сравнения 5b + a ≡ 5(3a + b) (mod 7). 4.69 . Среди этих чисел всегда есть одно, которое делится на 3. Поэтому. Если p 6= 3, то 8p 2 + 1 ... 3 4.71 . Здесь, как ив задачах, нужно рассмотреть остатки отделения на 3. 4.72 . Среди любых пяти последовательных членов такой арифметической прогрессии один обязательно делится на 5. Если это не 5, то простых чисел, идущих подряд, будет не более 4. Ответ 5, 11, 17, 23, 29. 4.73 . 3. 4.74 . Так как числа при делении надают остатки либо 0, либо то указанное число целым быть не может. Сравнение a 2 + b 2 ≡ 0 (mod 3) возможно только если оба числа a и b делятся на 3. Аналогичные рассуждения проходят и для модуля m = 7 4.78 . Остаток равен 2 4 ≡ −1 (mod 17). 4.79 . Нет. Рассмотрите числа Евклида e по модулю 5. 4.80 . Перейдите от равенства a 2 + b 2 = к сравнению по соответствующему модулю. а) m + 1 ≡ 3 (mod 4). б) m − 1 ≡ 2 (mod 3). 4.82 . a n ... при n = 2 + 3k; a n ... при n = 2k (k ∈ Z). 4.83 . а, б, гни при каких в) при n = 3 + 11k (k ∈ Z). 4.84 . а) n = −8 + 17k (k ∈ Z); б) ни при каких. x = 17 + 7 3 k (k ∈ Z). 4.91 . Докажите, что при всех целых x будет выполняться сравнение 1 (mod 2). Из него будет следовать, что значения P(x) не могут быть нулевыми. а) x ≡ 2 (mod б) x ≡ 24 (mod в) x ≡ 5 (mod г) x ≡ 15 (mod 169). 4.94 . 1652 и 6125. 4.96 . a ≡ ±1 (mod p). 4.97 . Все числа от 2 до p − 2 можно разбить на пары взаимно обратных по умножению чисел, то есть для каждого a из этого интервала найдется b (отличное от a по задаче) такое, что ab ≡ 1 (mod Поэтому (p − 1)! ≡ p − 1 (mod p). 4.98 . Пусть n — составное число. Если p — некоторый простой делитель числа n (p < n), то (n−1)! ≡ 0 (mod p), что противоречит условию − 1)! ≡ −1 (mod p). 4.99 . (p − 1)! + 1 = (p − 2)!(p − 1) + 1 = (p − 2)!p − ((p − 2)! − 1). Ответы, указания, решения 4.100 . Число p — простое тогда и только тогда, когда 4((p − 1)! + 1) + + p ≡ 0 (mod p). Остается доказать, что p + 2 — простое тогда и только тогда, когда 4((p − 1)! + 1) + p ≡ 0 (mod p + 2). С этой целью умножим обе части очевидного сравнения p ≡ −2 (mod p + 2) на p + 1. Получаем p(p + 1) ≡ −2(p + 1) = −2((p + 2) − 1) ≡ 2 ( mod p + Части полученного сравнения умножим на 2(p − 1)! : 2(p + 1)! ≡ 4 (p − 1)! ( mod p + К обеим частям полученного сравнения прибавим по p + 4: 2((p + 1)! + 1) + (p + 2) ≡ 4((p − 1)! + 1) + p ( mod p + По теореме Вильсона p + 2 — число простое тогда и только тогда, когда + 1)! + 1 ≡ 0 (mod p + 2) и, следовательно, 2((p + 1)! + 1) + (p + 2) ≡ ≡ 0 (mod p + 2), откуда 4((p − 1)! + 1) + p ≡ 0 (mod p + 2). 4.101 . Из условия задачи следует, что a 1 a 2 + a 2 a 3 + . . . + a n−1 a n + + a n a 1 ≡ 0 (mod 4). Это сравнение остается справедливым при замене знака у любого из чисел a j (j = 1, . . . , n). Заменив все числа на +приходим к сравнению n ≡ 0 (mod 4). 4.102 . Докажите неразрешимость по модулю m, где а) m = б) m = в) m = где ж) m = з) m = 13. 4.103 . Сумма пяти последовательных целых чисел всегда делится на 5: (n − 2) 2 + (n − 1) 2 + n 2 + (n + 1) 2 + (n + 2) 2 = 5(n 2 + Но число n 2 + не может делится на 5, поэтому 5(n 2 + полным квадратом не является. Выберите среди чисел 1, 2, . . . , n то, которое делится на максимальную степень двойки. Такое число будет ровно одно. Поэтому после приведения к общему знаменателю числитель будет нечетным. Для решения задачи нужно рассмотреть последние цифры указанных чисел, или, что тоже самое, перейти к сравнению по модулю 4.106 . x = 1, y = 0. 4.107 . Воспользуйтесь задачей 4.108 . Во всех случаях ответ 6. 4.111 . Воспользуйтесь соотношением 10 p−1 −1 = 99 . . . 9 ≡ 0 (mod p). 4.115 . При a = 0 утверждение очевидно. Предположим, что оно доказано для некоторого a > 0. Из результата задачи 4.42 следует Ответы, указания, решения соотношение (a+1) p ≡ a p +1 ( mod p). Далее, применяя предположение индукции, приходим к нужному сравнению. Существует a одноцветных раскрасок и a p − a раскрасок, в которых участвует не менее двух цветов. Ответа) б) 9. 4.119 . Данное число делится на 31. 4.120 . Данное число делится на 1093. 4.122 . Пусть q — простой делитель числа 2 p − 1 . Тогда выполняются сравнения 2 p − 1 ≡ 0 (mod q) и 2 q−1 − 1 ≡ 0 (mod q) (второе из них малая теорем Ферма. Далее следует воспользоваться результатом задачи а. Воспользуйтесь равенством n 16 − 1 = (n 8 − 1)(n 8 + 1) 4.129 . Применяя формулу из задачи, находим, что F p ≡ 5 (p−1)/2 ( mod p), 2F p+1 ≡ 1 + 5 (p−1)/2 ( mod p). Кроме того, 5 (p−1)/2 ≡ 1 (mod при = 10k ± 1 и 5 (p−1)/2 ≡ −1 (mod p) при = 10k ± 3. 4.130 . Число x 6= 1 удовлетворяет условиями. Далее следует применить результат задачи 4.131 . Используйте условия x p−1 −1 ≡ 0 (mod p) и x 5 −1 ≡ 0 (mod p). 4.132 . а) б) p − в) p(p − г) При подсчете нужно будет отбрасывать все числа, делящиеся на p. Таких чисел на отрезке от 1 добудет. Поэтому ϕ(p α ) = p α−1 (p − 1) 4.133 . p α 4.134 . Числа, взаимно простые с b, находятся в ϕ(b) столбцах. В каждом из них ϕ(a) чисел, взаимно простых с a. (См. задачу. ϕ(m). 4.136 . (a, m) = 1 и b делится на все простые числа из разложения m. 4.139 . а) x = 3, 4, б) x = 15, 30, 20, 24, в) гнет решений. Необходимо, чтобы ϕ(m) = 2. Но 1 ≡ 5 (mod 4), поэтому ответом служат только числа 3 и 5. 4.141 . а) x = б) x = 2 α 1 3 α 2 (α 1 , α 2 > 1); в) нет решений. а) При простом б) при четном в) при любом n. 4.143 . а) x = б) x = в) x = 2, y = 3. 4.144 . Каждому простому числу p, являющемуся делителем как m таки, в числе ϕ(m · n) соответствует множитель 1 − 1/p, а в числе ϕ(n) — множитель (1 − 1/p) 2 . Так как (1 − 1/p) < 1, то прибудет выполняться неравенство ϕ(m · n) > ϕ(m) · ϕ(n). 4.145 . 8, 12. Ответы, указания, решения 4.146 . Все такие дроби можно разбить на пары k/n, (n − k)/n. Числа в такой паре совпадать не могут. Из равенства k/n = (n − k)/n следует, что n — четное, k = n/2 и дробь k/n можно сократить на n/2. 4.147 . Пусть S(n) — искомая сумма. Очевидно, что S(1) = 1. При n > 1 X (d,n)=1 16d6n d n = 1 2 X (d,n)=1 16d6n d n + n − d n = 1 2 X (d,n)=1 16d6n 1 Ответ S(1) = 1, S(n) = ϕ(n)/2 при n > 1. 4.148 . ϕ(d). 4.149 . Рассмотрим ряд чисел из задачи. С одной стороны, он состоит из n дробей. С другой стороны, все числа разбиваются на группы дробей с равным знаменателем d, каждая из которых состоит из ϕ(d) чисел. 4.150 . ϕ(n)/2. 4.151 . а) Из мультипликативности функции Эйлера следует, что формулу достаточно доказать в случае, когда числа m и n суть степени одного итого же простого числа. Пусть m = p |