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

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

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

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

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

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

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

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

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

Задача 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 3) 1 1 2 0 2 2 1 0 1 1...

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

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

Ответ: 9

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

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

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

Задача 2#105231

Найдите все натуральные числа $n,$ для которых число $210+ 213 +214+3 ⋅2n$ является квадратом натурального числа.

Источники: ШВБ - 2020, 11 класс (см. olymp.bmstu.ru)

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

Рассмотрим несколько случаев

1) Пусть $n< 10,$ тогда $10 13 14 n n( 10−n 13−n 14−n ) N = 2 + 2 + 2 +3 ⋅2 =2 2 +2 + 2 + 3 ,$ второй сомножитель — нечетное число, $n ( k)2 2 = 2 ,n =2k.$

Если $n = 2,$ то $2( 8 11 12 ) 2 N =2 2 +2 + 2 + 3 = 2 ⋅6403$ не является квадратом натурального числа.
Если $n = 4,$ то $( ) N =24 26+29+ 210+3 = 24⋅1603$ не является квадратом натурального числа.
Если $n = 6,$ то $( ) N =26 24+27+ 28+ 3 =26⋅403$ не является квадратом натурального числа.
Если $n = 8,$ то $( ) N =28 22+25+ 26+ 3 =28⋅103$ не является квадратом натурального числа.

Пусть $n =10,$ тогда $10 13 14 10 12 N =2 + 2 + 2 +3⋅2 = 2 (1+2+ 4)$ не является квадратом натурального числа.
Пусть $n =11,$ тогда $10 13 14 11 10 N =2 + 2 + 2 +3⋅2 = 2 ⋅31$ не является квадратом натурального числа.
Пусть $n =12,$ тогда $10 13 14 12 10 N =2 + 2 + 2 +3⋅2 = 2 ⋅37$ не является квадратом натурального числа.

3) Пусть $n> 12,$ тогда $N = 210(1+ 23 +24+ 3⋅2n− 10)= 210 ⋅(2k+ 1)2,$ и

25+ 3⋅2n−10 = 4k2+4k +1

n−10 2 3 ⋅2 = 4k +4k− 24

3⋅2n−12 = k2+ k− 6

3 ⋅2n−12 = (k +3)(k − 2)

Числа $k+3$ и $k − 2$ разной четности, следовательно, одно из них является делителем 3. Поскольку $k> 0$ , то либо $k− 2= 1$ , $k= 3,$ $3⋅2n−12 = 6,$ $n= 13,$ либо $k − 2= 3,k= 5,$ $3⋅2n−12 = 24,$ $n= 15.$

Ответ:

13, 15

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

Задача 3#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+ ...+ p4)≥ 136, 2

что невозможно, т.к. $1 +p1 ≥ 3$ .

Таким образом, $p2 = 2$ , следовательно,

(1 + p2 +...+ p42)= 31,

то есть $1+ p1 = 6$ и $p1 =5$ . Наконец, $N =5 ⋅24 = 80.$

Ответ: 80

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

Задача 4#88134

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

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

Пусть $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$ , то имеем пять случаев: