alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике

• Название: Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
• Дата: 27.01.2020
• Размер: 2 Mb.
• Имя файла: alfutova(алгебра и теория чисел).pdf
• Тип: Сборник задач; #106051
• страница: 16 из 23

α
, n = p
β
(α > β >
> 0). Тогда нужное тождество следует из равенств [m, n] = m = p
α
,
(m, n) = n = б) Если воспользоваться мультипликативностью функции Эйлера,
то задача сводится к проверке равенства) ϕ(p
β
) = ϕ(p
α
) ϕ(p
β
) Оно, в свою очередь, следует из соотношения ϕ(p
α
) = p
α
(p−1)
. (См. задачу. Делимость на 2 и на 3 проверяется непосредственно. Делимость наследует из малой теоремы Ферма. −a
ϕ(m)−1
b
4.158
. В качестве n можно взять, например, ϕ(m).
4.159
. Пусть n = p
α
1 1
. . . p
α
s s
. Достаточно доказать, что 2
n!
− 1 ... p
α
j при j = 1, . . . , s. Для этого нужно применить теорему Эйлера к каждому из чисел m j
= p
α
j j
4.160
. Так как 561 = 3·11·17, то достаточно доказать справедливость сравнений a
560
≡ 1 (mod p), где p принимает значения p = 3, 11, Каждое такое сравнение выполняется по малой теореме Ферма. Очевидно, что решением задачи могут быть только те a, для которых (a, 10) = 1. Так как ϕ(10) = 4, то сравнение a
10
+ 1
≡ 0
(
mod 10) равносильно сравнению a
2
+1
≡ 0 (mod 10). Перебирая случаи

Ответы, указания, решения a =
±1, a = ±3, находим, что a ≡ ±3 (mod 10). Ответ a ≡ ±3
(
mod 10).
4.162
. Покажите, что при (a, m) = 1 выполняется соотношение a
λ(m)
≡ 1
(
mod p
α
j j
)
(j = 1, . . . , s).
4.166
. 3993, 3597, 6797.
4.167
. Примените признаки делимости на 8, 9 и 11. Ответ 1 380 456.
4.169
. Нет. Для доказательства можно находить не сумму цифра просуммировать арифметическую прогрессию 1 + 2 + . . . + 500.
4.170
. Для проверки делимости на 9 и 11 можно рассмотреть сумму данного числа с числом 8079 . . . 2019.
4.173
. 11 111 111 100.
4.175
. 9.
4.179
. Примените признак делимости на 11.
4.180
. Примените признак делимости на 3.
4.181
. Нет. Рассмотрите остатки отделения на 9.
4.182
. Сравнения 10a + b ≡ 0 (mod 19) и a + 2b ≡ 0 (mod 19) равносильны. Число xxyy всегда делится на 11. Если оно полный квадрат,
то и число x0y должно делится на 11. Ответ 88 2
= 7744 4.185
. Число получается из суммы своих цифр умножением назначит, оно кратно 3. Согласно признаку делимости на 3, сумма цифр также делится на 3. Поэтому само число должно делится на 9. Кроме того оно делится на 4. Следовательно нужно искать среди чисел, которые делятся на 36. Поскольку сумма цифр трехзначного числа не превосходит, то само число может быть не больше 27·12 = 324. Перебор можно еще сократить, если заметить, что сумма цифр может быть не больше
18
(она делится на 9 и меньше 27). Поэтому само число не больше 12 = 216. Осталось перебрать числа 108, 144, 180, 216. Ответа) Стратегия второго писать цифру так, чтобы сумма предыдущей цифры и его равнялась б) Стратегия первого сначала нужно написать 1, а потом писать цифру так, чтобы сумма предыдущей цифры и его равнялась 6. В этом случае перед последним ходом второго игрока сумма цифр будет равна, ион не сможет добиться своей цели. Рассмотрите остатки отделения на 9.
4.189
. Так как a j
10
j
≡ a j
r j
(
mod m), то M ≡ N (mod m). Поэтому числа M и N могут делиться на m только одновременно. Сравнение a
n q
n
+ . . . + a
1
q + a
0
≡ a n
+ . . . + a
1
+ a
0
(
mod m)

Ответы, указания, решения
199
равносильно сравнению a
n
(q n
− 1) + . . . + a
1
(q − 1)
≡ 0
(
mod которое имеет место независимо от a тогда и только тогда, когда q − 1
≡ 0 (mod m). В частности, для m = 2 годится система счисления с любым нечетным основанием. Ответ q = 1 + mk (k > 1).
4.192
. 21.
4.194
. Исследуйте отдельно делимость на 5 и на 11. Ответа) Обозначим остаток отделения на 66 через r. Из сравнений, следует, что r
≡ 1 (mod 2), r ≡ 1 (mod 3), r ≡ (−2)
10
(
mod 11). По малой теореме
Ферма, (−2)
10
≡ 1 (mod 11). Отсюда r = б) в) г) 36.
4.197
. Воспользуйтесь теоремой Эйлера. x = a
1
x
1
+ . . . + a n
x n
, где x j
=

m
1
. . . m n
m j

ϕ(m j
)
(j = 1, . . . , n).
4.200
. а) x = 58 + 85k (k ∈ Z); б) x = 78 + 13 · 19k (k ∈ Z).
4.201
. 2 · 3 · 5 · 7 − 1.
4.203
. 2 · 10 249 4.204
. 15803.
4.207
. Пусть n = 2. Равенство c
m
1
· m
2
=
a m
1
+
b можно переписать в виде c = a · m
1
+ b
· m
2
. Для того, чтобы решить это уравнение, рассмотрите сравнение c ≡ a · m
1
+ b
· m
2
(
mod m
1
· и воспользуйтесь задачей. Для произвольного n нужно применить индукцию. 45486.
4.209
. 2 15
· 3 10
· 5 6
4.210
. а) Данное сравнение равносильно выполнению двух условий x(x − 1)
≡ 0 (mod 2 и x(x − 1) ≡ 0 (mod 5 4
)
. Отсюда x ≡ 0, 1 (mod 2 и x ≡ 0, 1 (mod 5 4
)
. Поэтому по модулю 10 исходному сравнению будут удовлетворять 4 числа, из которых два — это числа x = 0 и x = 1. Два других решения — это x = 0625 и x = 9376, из которых четырехзначным является только второе. Ответ x = б) Докажите утверждение по индукции. Если процесс нахождения таких чисел не остановить, то кроме 0 и 1 получатся два бесконечных
«числа»
x
1
= . . . 8212890625,
x
2
= . . . 1787109376.
4.211
. Примените китайскую теорему об остатках с m
1
= p
2 1
, . . .
. . . , m
37
= p
2 37
, где p
1
, . . . , p
37
— различные простые числа

Ответы, указания, решения − 1)! − (p − 1)
p
=
(p − 1)! + 1
p
− Глава 5.1
. а) 1/7 = б) 2/7 = в) 1/14 = г) 1/17 = 0,(0588235294117647).
5.2
. a = 0, b = 0 или a = 1, b = 3.
5.3
. 1/49 = 0,(020408163265306122448979591836734693877551). Если просуммировать геометрическую прогрессию 2/10 2
+ 4/10 4
+ . . .
, то получается в точности 1/49.
5.4
. 1/243 = 0,(004115226337448559670781893).
5.5
. а) 15926/111111 = б) 4/27 = в) 14/99 =
= 0,(14)
5.7
. n = 2
α
· 5
β
5.9
. Рассмотрите отдельно те цифры, которые встречаются конечное число разите, которые встречаются бесконечно много раз. n = 2
α
1
· 5
β
1
, n + 1 = 2
α
2
· 5
β
2
. Отсюда n = 1 или n = 4.
5.12
. Среди указанных чисел бесконечно много четных. а) нет.
б)
√
2 + (−
√
2) = в) Определим число α равенством (
√
3)
α
= 2
. Если α =
p q
, то получаем невозможное равенство 3
p
= Другой пример можно построить при помощи числа β Если оно рационально, то задача решена. Если оно иррационально, то и искомой парой чисел будут β и 5.17
. Подставляя в уравнение x = 1 +
√
3
, приходим к равенству + a + b) + (a + 2)
√
3 = Так как иррациональное число, то такое равенство возможно лишь когда 4 + a + b = 0 и a + 2 = 0. Ответ a = −2, b = 2.
5.18
. Если числа являются членами одной арифметической прогрессии, то для некоторых целых p и q будет выполняться равенство q(
√
b −
√
a) = p(
√
c или + q) = p
√
c + После возведения последнего равенства в квадрат получаем, что
√
ac
—
рациональное число. Но это невозможно, поскольку a и c — различные простые числа +
√
6 5.21
. а) 9 =
√
100 − б) в) −10.
5.22
. а) б) в) 6.
5.23
√
2 +
√
3 +
√
5 5.24
. Возведите равенство в квадрат

Ответы, указания, решения 5.25
. Для решения этой задачи удобнее доказать более общее утверждение если b
1
, . . . , b n
— ненулевые целые числа, a
1
, . . . , a n
— различные натуральные числа, свободные от квадратов, то b
1
√
a
1
+ . . . + b n
√
a n
6= Выбирая здесь a
1
= 1
, получаем иррациональность суммы радикалов+ . . . +
√
a n
. Для доказательства соотношения
13.5
проведите индукцию по числу простых p
1
, . . . , p m
, входящих в разложения чисел a
1
, . . . , a на множители. Только если a и b являются степенями одного итого же числа,
то есть a = d и b = d для некоторых натуральных d, m и n.
5.28
. Тангенс угла между стороной треугольника и любой из координатных осей рационален. Углы треугольника являются суммами или разностями таких углов и, следовательно, также имеют рациональные тангенсы. Воспользуйтесь тем, что прямая, проходящая через целые точки, имеет рациональный тангенс наклона, а tg 60
◦
=
√
3 /
∈ Q.
5.31
. Пусть на окружности лежат две точки (x; y) и (u; v). Тогда −
√
2)
2
+ (y −
√
3)
2
= (u −
√
2)
2
+ (v −
√
3)
2
,
2(u − x)
√
2 + 2(v − y)
√
3 = u
2
+ v
2
− x
2
− Невозможность последнего равенства доказывается возведением в квадрат. ж) Смотрите задачу
6.82
г).
5.33
. При четных n.
5.36
. Как ив задаче, идея решения основана на принципе Дирихле. При k = 1 утверждение задачи очевидно. Далее применим индукцию. Предположим, что утверждение задачи доказано для k − 1, и докажем его для k. Рассмотрим произвольную изданных точек. Из нее выходит по крайней мере N
1
=
l
N − 1
k отрезков, окрашенных в один и тот же цвет, где dxe — минимальное целое число n такое, что x
6 n. Для справедлива оценка e]
k m
>
h
[k! e]
k i
=
h k! e k
i
= [(k − 1)! См. задачу) Если концы каких-либо двух из этих отрезков соединены отрезком того же цвета, то нужный треугольник найден.
В противном случае, концы соединяются отрезками, окрашенными в k − цветов. Так как N
1
> [(k − 1)! e]
, то, согласно предположению

Ответы, указания, решения индукции, можно найти треугольник одного цвета с вершинами в этих точках. По формуле для суммы геометрической прогрессии. . . a n
) =
a
1
a
2
. . . a n
10
n
− Отсюда, если a
1
a
2
. . . a n
=
10
n
− 1
m
, то 0,(a
1
a
2
. . . a n
)
5.39
. По теореме Эйлера 10
kϕ(m)
− 1
≡ 0 (mod m) при любом k > Поэтому 9 · E
kϕ(m)
≡ 0 (mod m). Если m не делится на 3, то E
kϕ(m)
≡ 0
(
mod m). Если же m делится на 3 или на 9, тона будут делится числа
E
3kϕ(m)
и соответственно. Если p
q
= 0,a
1
a
2
. . . a k
a k+1
, то p
q
= 0,a k+1 5.41
. Пусть r
0
= 1
, r
1
= 10 − m[10/m]
. . . — остатки, которые возникают при делении 1 на m столбиком. Тогда r k
≡ 10
k
(
mod m), так как приписывание нуля равносильно умножению на 10. Если (m, 10) = то 10
ϕ(m)
≡ 1 (mod m), то есть r
ϕ(m)
= r
0
= 1
. Отсюда следует, что у дроби отсутствует предпериод, и что длина периода делит ϕ(m).
5.42
. 11, 33 и 99 — делители числа 99, не делящие 9.
5.43
. Если 10
t
≡ 1 (mod n), то остатки и r см. задачу
5.38
)
совпадают, так как r
0
= m и r t
≡ 10
t m (
mod n). Значит период дроби m/n делит t. Наоборот, если T — длина периода, то r
T
= дробь чисто периодическая согласно задаче) и r
0 10
T
≡ r
0
(
mod n). Так как r
0
= m и (m, n) = 1, то полученное сравнение можно сократить на r
0
. Следовательно, 10
T
≡ 1 (mod n).
5.45
. Воспользуйтесь результатом задачи 5.46
. Пусть t = 2n — длина периода. Согласно задаче, выполняется сравнение 10
t
≡ 1 (mod q). Отсюда 10
n
≡ −1 (mod и p
q
+
10
n p
q
= Нов десятичной системе эти дроби имеют вид p
q
= 0,N
1
N
2
,
10
n p
q
= поэтому N
1
+ N
2
= 99 . . . 9
| {z }
n
5.47
. При разложении 1/7 в десятичную дробь последовательность остатков устроена следующим образом 1,
r
1
= 3,
r
2
= 2,
r
3
= 6,
r
4
= 4,
r
5
= 5,
r
6
= Первое свойство объясняется равенствами 7
=
r
2 7
,
3
·
r
0 7
=
r
1 7
,
4
·
r
0 7
=
r
4 7
,

Ответы, указания, решения
203
Объяснение второго свойства получается, если в равенстве 1/7 +
+ 2/7 + 4/7 = перейти к десятичной записи.
Чтобы объяснить последнее свойство, запишем N в виде N =
= (10 6
− 1)/7
. Отсюда N
2
= (10 6
− 1)
2
/49
. Число, которое получается сложением половинок числа N
2
, будет периодом дроби 10 6k
= N
2 1
10 6
− 1
=
10 6
− 1 49
=
142857 Так как 7
=
1 7
= то из половинок числа получится число N.
5.48
. См. решение задачи 5.51
. Пусть abcdef = 3 · fabcde. Рассмотрим число α, которое разлагается в периодическую десятичную дробь с периодом abcdef:
α = 0,(fabcde) =
1 3
· Тогда α = f,(abcdef) = f + 3 · Отсюда α =
f
7
. Остается перебрать различные значения f.
5.52
. Рассмотрите десятичные дроби, у которых искомое число является периодом. 81 + 9 + 1 = 61 + 27 + 3 5.57
. Да. Причем меньшим числом взвешиваний обойтись нельзя. 2
n
− 1 5.59
. а) 2 4
− 1 = б) (3 4
− 1)/2 = 40 5.60
. 1, 3, 9 и 27 кг. а) Первую веревку следует поджечь с двух концов, а вторую с одного. После догорания первой веревки второй останется гореть минут. Чтобы сократить этот промежуток вдвое, следует поджечь и второй конец оставшейся веревки.
б) 2 4
− 1 5.62
. а) Лампочка может находится в трех состояниях — включенном,
выключенном ив нагретом. б) 9.
5.63
. б) Если n = 2
k
1
+ 2
k
2
+ . . . + 2
k m
(k
1
> k
2
> . . . > k m
> 0), то наименьшее число операций равно k
1
+ m
5.65
. b(15) = 6, но l(15) = 5:
x
1
= x
2
, x
2
= x
1
· x = x
3
, x
3
= x
1
· x
2
= x
5
, x
4
= x
2 3
= x
10
, x
5
= x
3
· x
4
= Аналогично l(63) = 8 < 10 = b(63).

Ответы, указания, решения. Для нахождения числа нужно сложить первые числа с выбранных карточек. Например, если загадано число 23, то потребуется сложить числа 1, 2, 4 и 16.
5.67
. Загаданная карта всегда оказывается в центре колоды. Если A четно, то представление числа A получается из представления меньшего числа m = A/2 сдвигом на один разряд. Если же A нечетно, то a
0
=
±1 и число должно равняться нулю поэтому число A − делится на 4 и представление числа A получается из представления меньшего числа m = (A − сдвигом на два разряда и добавлением цифры a
0
. В обоих случаях единственность представления числа A следует из единственности представления числа m.
5.72
. Числа от 0 до 1 удобно рассматривать как бесконечные троичные дроби из цифр 0, 1 и 2. Числа, о которых говорится в пункте в) это те числа, в троичной записи которых нет ни одной 1.
5.73
. а) б) нет;
д) й элемент данной последовательности совпадает по модулю 2 с ν(n) (суммой двоичных цифр числа n).
5.74
. Занумеруем диски в головоломке Ханойская башня числами от 0 до 7. При увеличении на 1 числа n, записанного в двоичной системе счисления, могут измениться цифры сразу в нескольких разрядах. Если среди всех изменившихся разрядов наибольший номер имеет й разряд,
то это означает, что нам шаге решения головоломки Ханойская башня следует перемещать диск с номером k.
5.75
. а) Если по кругу стоят числа 1, 2, . . . , 2n, то вначале вычеркиваются все четные числа. Оставшиеся числа 1, 3, 5, . . . , 2n − 1 снова подвергаются процедуре вычеркивания. е число в этом списке имеет вид 2k − 1. После того, как из этого списка будут вычеркнуты все числа кроме одного, останется число с номером J(n), которое равно 2J(n) − 1.
5.76
. г) Пусть n = (n s
. . . n
1
n
0
)
2
, где n s
= 1
. Тогда у одного из чисел m
1
, m
2
, . . . , m в м разряде также стоит единица. Если m j
— одно из таких чисел, то m j
⊕ n < m j
5.77
. а) Если n равнялось 0 и одно из чисел m
1
, m
2
, . . . , m изменилось, то изменится и число n. Оно станет равно количеству взятых камней, отличному от нуля.
б) Согласно задаче
5.76
г), для некоторого j (1 6 j 6 l) выполняется неравенство m j
⊕n < m j
. Поэтому из й кучки можно взять m j
−(m камней, что приведет к обнулению ним-суммы.
в) Игрок находится в проигрышной позиции, если перед его ходом. Все остальные позиции — выигрышные. Для того, чтобы выиграть в Ним, нужно оставлять после своего хода проигрышную позицию.
г) Нужно сделать переход к позиции 1, 4, 5.

Ответы, указания, решения 5.78
. Можно, например положить f(A) = 3, f(B) = 5, f(A) = 6. Теперь остается заметить, что при слиянии амеб общая ним-сумма не меняется,
а в начальный момент времени она равна 5 = f(B).
5.80
. а) Игра Шоколадка сводится к игре Ним с 4 кучками камней. Например, позиция, изображенная на рисунке, соответствует такому набору камней 2, 5, 1, 4 (2 ряда слева от отмеченной дольки справа, 1 — снизу и 4 — сверху. б) Пусть в кучках m
1
, m
2
, . . . , m камней, и r
1
, r
2
, . . . , r остатки отделения чисел m
1
, m
2
, . . . , m на 6. Положим n = r
1
⊕ r
2
⊕ . . . ⊕ r l
— ним-сумма по модулю 6. Если в начальной позиции n = 0, то выигрывает второй игрок во всех остальных случаях — первый. Исключение составляет случай m
1
= m
2
= . . . = m l−1
= 1,
m l
— любое.
(13.6)
(Рассмотрите этот случай отдельно) Стратегия выигрыша первого игрока если перед ходом первого игрока набор камней удовлетворяет равенствам, причем l нечетно, то ход надо делать так, чтобы новая ним-сумма равнялась 1; если l четно и r l
= 1
, то забирается любой из камней, лежащих отдельно. Во всех остальных случаях ход надо делать так, чтобы n
0
= 0
. Если это невозможно, то первый игрок проигрывает. Сначала следует сравнить ю и ю монеты, затем ю и ю. Во-первых, специальным образом пронумеруем монеты присвоим им трехзначные номера 001, 010, 011, 012, 112, 120, 121, 122, 200,
201
, 202, Для первого взвешивания положим на одну чашу весов те монеты,
у которых старший разряд равен 0 (то есть 001, 010, 011, 012), а на другую - те монеты, у которых он равен 2 (200, 201, 202, 220). Если перетянет чашка с «0», запишем на бумажке цифру 0. Если перетянет запишем 2. Если чаши весов останутся в равновесии — запишем Для второго взвешивания на одну чашу выложим монеты 001, 200,
201
, 202 (то есть все те монеты, у которых второй разряд равен 0), а на другую — 120, 121, 122, 220 (то есть те монеты, у которых средний разряд равен 2). Запишем результат взвешивания таким же образом,