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

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

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

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

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

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

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

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

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

Задача 1#119859

Множество $A$ состоит из натуральных чисел $n,$ делящихся на $[3√n].$ Здесь $[x]$ — целая часть числа $x,$ то есть наибольшее целое число, не превышающее $x.$ Найдите количество чисел из отрезка $[25,2025],$ принадлежащих множеству $A.$

Источники: ПВГ - 2025, 11.4(см. pvg.mk.ru)

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

Подсказка 1

Попробуйте рассмотреть какой-то удобный интервал, внутри которого можно легко посчитать количество таких чисел. А потом рассмотрите интервалы такого вида, входящие в отрезок [25; 2025].

Подсказка 2

Рассмотрите интервал [k³, (k+1)³-1], где k — целая часть кубического корня из n. Сколько чисел в нём кратно k?

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

Рассмотрим отрезок $[k3,(k +1)3− 1],$ где $[√3n-]= k.$ Мы хотим выбрать из такого отрезка числа, которые делятся на $k.$ Количество целых чисел на таком отрезке

3 3 (k+1) − k = k(3k+ 3)+1

причём первое число $k3,$ очевидно, делится на $k.$ Значит, всего подходящих чисел на отрезке будет

k(3k+-3) k +1 =3k+ 4

В нашей задаче в исследуемый интервал целиком входят отрезки для $k =3,...,11.$ Там искомых чисел

9⋅(11 +3) 3⋅---2----+ 4⋅9= 225

На отрезке $[25,26]$ только одно число делится на $2,$ а на отрезке $[123 = 1728,2025]$ всего $298$ чисел, причём снова певрвое число делится, поэтому мы берём $[21972 ]+ 1= 25$ чисел. Всего $1+225+ 25= 251$ число.

Ответ:

$251$

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

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

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

Задача 2#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

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

Задача 3#105231

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

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

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

Подсказка 1

В точный квадрат все простые множители входят в чётных степенях. В нашей задачей рассматривают сумму, которая содержит степени двойки, так что можно рассмотреть именно степень вхождения двойки.

Подсказка 2

Попробуем провести разумный перебор. Допустим, самая маленькая степень вхождения двойки в слагаемые будет в 3*2ⁿ. Тогда она должна быть чётной, мы можем явно проверить эти случаи.

Подсказка 3

Пусть теперь n достаточно большое. Тогда можно вынести 2¹⁰, останется какая-то нечётная сумма, которая должна быть равна (2k+1)² для какого-то k.

Подсказка 4

После раскрытия скобок можно будет сократить на 4, а после разложить на множители. Остаётся заметить, что скобки, связанные с k, имеют разную чётность, а значит, одна из них гарантированно маленькая.

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

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

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

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

Задача 4#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

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

Задача 5#88134

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

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

Подсказка 1

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

Подсказка 2

Количество делителей равно произведению степеней, в которых простые числа входят в число (пусть M), увеличенных на единицу! Тогда рассмотрим разложение M и составим уравнение по условию!

Подсказка 3

Пусть простые делители входят в M в степенях k₁, k₂, …, kₙ. Тогда (k₁+1)(k₂+1)…(kₙ+1) = 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$ , то имеем пять случаев: