Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2013_2014/8mat_1314/spec/simple_tasks_3.pdf Дата изменения: Sun Feb 9 16:58:50 2014 Дата индексирования: Sun Apr 10 22:59:46 2016 Кодировка: Windows-1251 Поисковые слова: mars global surveyor

Обязательные упражнения, 3 четверть
Разбор задач 13.0.

Разложите 2014 на простые множители. Запомните это разложение! Чему равен
2 ћ 19 ћ 53 (11 . . . 1, 11 . . . 1 )?
n единиц m единиц
Решение.

Ответ.

13.1.

Ответ.

11 . . . 1
(n,m) единиц

Пусть

n

m.

Согласно лемме из алгоритма Евклида:
m n-m m

(11 . . . 1, 11 . . . 1) = (11 . . . 1 00 . . . 0, 11 . . . 1) = (11 . . . 1 ћ10m , 11 . . . 1).
n m n-m m

Заметим, что

(10m , 11 . . . 1) = 1,

поэтому
n

10m

можно убрать. Имеем:
n-m m

(11 . . . 1, 11 . . . 1) = (11 . . . 1, 11 . . . 1).
m

Заметим, что для пары количества единиц (n; m) мы проделали одну операцию алгоритма Евклида (из большего числа вычли меньшее). Продолжая таким образом, через несколько действий, количества единиц станет равно (n, m) и 0. То есть
(11 . . . 1, 11 . . . 1) = . . . = (11 . . . 1, 0) = 11 . . . 1 .
n m (n,m) (n,m)

a) b) с)

13.2.

входить простые ... q = p . Тогда у числа a будет два делители, отличные от p1, . . . , ps. Действительно, пусть d i канонических представления: в одном q нет, в другом a = d ћ y = q ћ xy есть. Противоречие с основной теоремой арифметики. Значит d = p1 ћ . . . ћ ps . Аналогично можно показать, что i i (если не так, то у a будут два канонических представления: в одном pi в степени i, в другом в степени строго большей, чем i). Аналогично i i, значит i min(i, i). Заметим, что любой набор i, удовлетворяющих этому условию соответствует некоторому общему делителю a и b. Наибольшим из них, очевидно, является то, в котором i максимально, то есть i = min(i , i ). b) Аналогично, пусть c = p ћ . . . ћ p ћ q1 ћ . . . ћ qt общее кратное a и b. Аналогично рассуждению 1 s пункта a) можно показать, что i i, i i, про i можно только сказать, что они неотрицательны. Значит i max(i, i), i 0. Заметим, что любой набор i, i, удовлетворяющих этим условиям соответствует некоторому общему кратному этих двух чисел. Наименьшим из них является то, для которого i = max(i, i), i = 0. с) Следует из пунктов a) и b) и того факта, что min(x, y) + max(x, y) = x + y для любых x и y. Пусть a > 1 натуральное число. Найдите (an - 1, am - 1). a(n,m) - 1. Пусть n m. По лемма из алгоритма Евклида
1 s 1 s 1 t

ћ . . . ћ ps , b = p1 ћ . . . ћ ps . Докажите, что 1 s s min(s ,s ) min(1 ,1 ) ћ . . . ћ ps , где min(x, y) это наименьшее из чисел x и y; (a, b) = p1 max(s ,s ) max(1 ,1 ) ћ . . . ћ ps , где max(x, y) это наибольшее из чисел x и y; [a, b] = p1 (a, b) ћ [a, b] = a ћ b. Решение. a) Пусть d общий делитель a и b. Тогда в разложение d не могут a=p
1
1

Пусть

14.1.

Ответ.

Решение.

(an - 1, am - 1) = (an - am , am - 1) = (am (a

n-m

- 1), am - 1).

Заметим, что

(am , am - 1) = (1, am - 1) = 1

, поэтому

a

m

можно убрать. Значит,
- 1, am - 1).

(an - 1, am - 1) = (a

n-m

Таким образом для пары степеней (m; n) мы из большего числа вычли меньшее. Продолжая, рано или поздно (согласно алгоритму Евклида) мы получим пару (n, m) и 0, то есть
(an - 1, am - 1) = (a
n-m

- 1, am - 1) = . . . = (a

(n,m)

- 1, a0 - 1) = a

(n,m)

- 1.


Пусть p простое и n < p < 2n. Докажите, что C2nn делится на p. (2n)! n C2n = . Заметим, что числитель делится на простое p, а знаменатель нет. n! ћ n! Тогда, так как C2nn целое, то оно делися на p. Пусть a) n = pqr2; b) n = p ћ p ћ . . . ћ p . Найдите сумму делителей числа n. 2 1 s Докажем a) (1 + p)(1 + q)(1 + r + r2); b) (1 + p1 + . . . + p ) ћ . . . ћ (1 + ps + . . . + p ). 1 s только пункт b) (поскольку пункт a) является его частным случаем). Заметим, что все делители числа n имеют вид p ћ p ћ . . . ћ p , где 0 i i. Легко заметить, что после раскрытия скобок 2 1 s каждое из этих слагаемых получится, получится ровно один раз и никаких других слагаемых не возникнет (достаточно взять из первой скобки p1 , из второй p , . . . , из последней p ). 2 s Учитывая, что 1 + x + . . . + xn = (xn+1 - 1)/(x - 1), ответ в пункте b) можно +1 +1 переписать в виде p1p -- 1 ћ . . . ћ psp -- 1 1 1 1 s Может ли число делится на 8 и давать остаток остаток 10 при делении на 12? Нет, не может. Заметим, что если число дает остаток 10 при делении на 12, то оно имеет вид 12k + 10, и дает остаток 2 при делении на 4. А число, которое делится на 8, делится и на 4, то есть дает остаток 0 при делении на 4. Если число делится на 4, то при делении на 12 оно может давать остатки только 0, 4 и 8.
14.2.
Решение.

15.1.

1

2

s

Ответ.

1

s

Решение.

1

2

s

1

2

s

Замечание.

1

s

15.2.

Ответ.

Решение.

Замечание.