Теория чисел на ШВБ —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на ШВБ

Тема ШВБ (Шаг в будущее)

Теория чисел на ШВБ

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела швб (шаг в будущее)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#77774

Последовательность Фибоначчи задана рекуррентно $a = a = 1,a = a + a ,n≥ 2 1 2 n+1 n n−1$ . С каким остатком число 3 в степени $a 2022$ делится на 13?

Показать ответ и решение

Чтобы найти остаток при делении $3n$ на $13,$ достаточно знать остаток при делении на $3,$ потому что

3 3k+r r 3 = 27≡ 1(mod 13)⇒ 3 ≡ 3 (mod 13).

По индукции доказывается, что остатки при делении чисел Фибоначчи на $3$ повторяются с периодом $8:$

k 1 2 3 4 5 6 7 8 9 10...

ak 1 1 2 3 5 8 13 21 34 55...

ak(mod 13) 1 1 2 0 2 2 1 0 1 1...

Поскольку $2022$ делится на $8$ с остатком $6,$ имеем

3a2022 ≡ 3a6 =38 ≡ 32 = 9(mod 13).

Ответ: 9

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#88129

Найдите натуральное число, которое имеет десять натуральных делителей (включая единицу и само число), два из которых простые, а сумма всех его натуральных делителей равна 186.

Показать ответ и решение

Пусть искомое число $N$ имеет простые делители $p1$ и $p2$ . Тогда $N$ представимо в виде $α1α2 p1 p2$ при некоторых натуральных $α1$ и $α2$ . Без ограничений общности можем считать, что $α1 ≤ α2$ .

Количество натуральных делителей числа $N$ равно

τ(N )= τ(pα11pα22)= (1 +α1)(1+ α2)= 10.

При этом значения каждого из множителей не меньше 2, следовательно, $α1 +1 = 2,α2 +1 = 5$ , то есть $α1 = 1,α2 = 4$ .

Сумма всех натуральных делителей числа $N$ равна

σ(N) = σ(p1p4)= (1 +p1)(1 +p2 +...+ p4)= 186 = 2⋅3⋅31. 2 2

Если $p2 ≥3$ , то $(1+ p2 +...+ p42)≥ 136$ , что невозможно, т.к. $1+ p1 ≥ 3$ . Таким образом, $p = 2 2$ , следовательно, $(1+ p + ...+p4)= 31 2 2$ , то есть $1 +p =6 1$ и $p1 = 5$ . Наконец, $4 N = 5⋅2 = 800$ .

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#88134

Найдите наименьшее натуральное число, имеющее ровно 42 натуральных делителя (включая единицу и само число).

Подсказки к задаче

Подсказка 1

Подумаем, а что мы вообще знаем о количестве делителей?

Показать ответ и решение

Пусть $n$ — искомое натуральное число, разложим на простые:

k1 k2 km n =p1 ⋅p2 ⋅...⋅pm

Любой натуральный делитель этого числа имеет вид

l1 l2 lm d= p1 ⋅p2 ⋅...⋅pm

где $li ∈{0,1,...,ki},i= 1,...,m$ . Число делителей числа $n$ равно

(k1+1)(k2+1)⋅⋅⋅(km+ 1)= 42.

Разложим число 42 на неединичные сомножители всеми возможными способами и выберем из них наименьшее $n.$ Поскольку $42= 2⋅3⋅7$ , то имеем пять случаев: