Тема Делимость и делители (множители)

Оценки для доказательства делимости

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

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

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

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

Подтемы раздела делимость и делители (множители)

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

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

Задача 1#79759

Даны натуральные числа $a$ и $b$ такие, что число $a+-1+ b+-1 b a$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $√ ---- a+b.$

Показать доказательство

Имеем:

a+-1 b+-1 a2+-b2+a-+b b + a = ab

Пусть $d$ — наибольший общий делитель чисел $a$ и $b.$ Так как $ab$ делится на $2 d ,$ то $2 2 a + b+ a+ b$ делится на $2 d.$ Число $2 2 a +b$ также делится на $2 d .$ Поэтому $a+b$ делится на $2 d$ и $√---- a +b≥ d.$

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

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

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

Задача 2#67958

Найдите все простые $p,$ для которых числа $p+ 1$ и $p2+1$ являются удвоенными квадратами натуральных чисел.

Источники: СПБГУ-23, 11.2 (см. olympiada.spbu.ru)

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

Подсказка 1

Пусть p+1 = 2x², p²+1 = 2y². Вот давайте вычтем эти два выражения: будет p(p-1) = 2(y-x)(y+x). Про что можно тут подумать, раз слева стоит простой множитель?

Подсказка 2

Про делимости! У нас делится на p либо 2, либо y-x, либо y+x. Если проверить p = 2, то он не подойдет. А может ли y-x делится на p?

Подсказка 3

Можно заметить, что т.к. p+1 = 2x², то x<p, а также y<p и x<y. Тогда y-x тем более < p и он на него не делится. Остается, что y+x делится на p. Используя наши оценки на x и y, поймите, чему равно y+x и решите полученную системку!

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

Пусть

2 2 2 p+1 =2x и p +1 =2y ,

тогда

2 2 p(p− 1)= 2(y − x )= 2(y− x)(y+ x)

Поэтому одно из чисел 2, $y− x$ и $y+ x$ кратно $p.$ Если 2 кратно $p,$ то $p= 2,$ что невозможно, поскольку $p+1 =3$ не является удвоенным квадратом.

Первый способ.

Из неравенства $x < y < p$ следует, что

x+ y = p

Таким образом, имеем систему из двух уравнений

( { x +y = p ( 2(y− x) =p− 1

Решаем её

( ( { x+ y = p { 2x +2y = 2p p+1- ( 2(y − x)= p− 1 ⇒ ( 2y − 2x= p− 1 ⇒ 4x =p+ 1⇒ x = 4

Значит,

( p+1-)2 p +1= 2 4

Следовательно, $p= 7.$

Второй способ.

Если $y− x$ делится на $p,$ то

y +x >y− x≥ p⇒ 2(y− x)(y+ x)≥2p2 > p(p − 1)

Значит, это невозможно. Следовательно, $y+x$ делится на $p.$ Заметим, что

y2= p2+-1> p2−-1= p− 1 x2 p +1 p +1

Тогда если $p ≥11,$ то

y2 > 10x2 ⇒ y > 3x

Значит,

2(y− x)> y+ x≥ p

Стало быть,

2(y− x)(y+ x) >p2 > p(p +1)

Но этого не может быть. Таким образом, осталось рассмотреть случаи $p= 3,p =5$ и $p= 7.$ В первых двух из них $p+ 1$ не является удвоенным квадратом, а $p= 7$ подходит.

Ответ: 7

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

Задача 3#73164

Найдите все натуральные числа $a$ , $b$ и $c$ такие, что

(ab−-1)(ac−-1)- bc

является квадратом целого числа.

Источники: 61 УТЮМ

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

Заметим, что $(ab−-1)(ac−-1)-=(a − 1)(a − 1) < a2 bc b c$ . При этом наше выражение не меньше $(a− 1)2$ . Тогда $(a− 1) (a− 1) =(a− 1)2 b c$ . Если $a >1$ , то $b =c= 1$ (иначе левая часть будет строго больше правой). Если же $a =1$ , и $b,c> 1$ , то левая часть снова будет больше правой. Тогда одно из чисел $b$ и $c$ равно 1, а второе может быть любым.

Ответ:

$(1,1,c)$ , $(1,b,1)$ , $(a,1,1)$ для любых натуральных $a$ , $b$ и $c$

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

Задача 4#81488

Существует ли $2016$ различных натуральных чисел таких, что никакая сумма нескольких из этих чисел не является полным квадратом.

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

Возьмём простое число $p,$ большее $1+2+ ...+ 2016.$ Рассмотрим числа $p,2p,...,2016p.$ Любая сумма нескольких из этих чисел имеет вид $kp,$ где $k$ меньше $p,$ а потому и не кратно $p.$ То есть любая сумма делится на $p,$ но не делится на $2 p ,$ а значит не является квадратом.

Ответ:

Да

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

Задача 5#85844

Старательный Роберт выписывает на доску все пары, состоящие из трехзначного и четырехзначного чисел, такие, что каждое из этих чисел делится на их разность. Сколько пар выпишет на доску Роберт?

Источники: Лига открытий - 2018

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

Рассмотрим произвольную пару, выписанную Робертом. Обозначим разность в ней через $x.$ Тогда сами числа равны $nx$ и $(n+1)x$ при некотором натуральном $n.$ При этом число $nx$ должно быть трехзначным, а $(n +1)x$ — четырехзначным. Заметим, что при $x≥ 1000$ такое невозможно. Если же $1 ≤x ≤999,$ то такое $n$ обязательно найдется, и более того, оно единственно: подходит наибольшее $n,$ при котором $nx <1000.$ Число $nx$ в таком случае трехзначно, ведь будь оно двузначно, мы могли бы увеличить $n$ хотя бы на $1.$ При этом число $(n+ 1)x ≥1000,$ но при этом, очевидно, не больше $1998,$ так как $x ≤999.$ Остальные $n,$ очевидно, не подходят: при больших значениях $n$ число $nx$ уже не трехзначно, а при меньших число $(n+ 1)x$ не четырехзначно.

Итак, при любом $1≤ x≤ 999$ существует ровно одна пара с разностью $x,$ подходящая под условие, а при остальных $x$ таких пар нет вообще. Значит, пар $999.$ Все они различны хотя бы потому, что в этих парах разная разность чисел в паре.

Ответ:

$999$

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

Задача 6#71294

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

Источники: СпбОШ - 2017, задача 11.4(см. www.pdmi.ras.ru)

Показать доказательство

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

Курсы

Всё необходимое для достижения цели

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

Задача 7#70349

Натуральные числа $a$ и $b$ больше $1.$ Известно, что числа $a2+ b$ и $a +b2$ простые. Докажите, что числа $ab+ 1$ и $a+ b$ взаимно простые.

Источники: СпбОШ - 2015, задача 11.3(см. www.pdmi.ras.ru)

Показать доказательство

Пусть они не простые. Тогда $ab+ 1$ и $a+ b$ имеют общий простой делитель $p.$ Рассмотрим произведение чисел $a2+ b$ и $a+ b2$ и преобразуем

2 2 22 3 3 2 2 (a + b)(a+ b)= a b +ab+ a +b = ab(ab+ 1)+ (a+ b)(a − ab+ b).

Тогда произведение тоже делится на $p.$ Но поскольку $p ≤a+ b< min(a2+ b,b2+ a),$ число $p$ является собственным делителем какого-то из чисел $a2+b$ или $a+ b2,$ что противоречит их простоте.

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

Задача 8#70862

Дано натуральное число $N.$ На доске написаны числа от $N3$ до $N3 +N.$ Среди них $a$ чисел покрасили в красный цвет, а какие-то $b$ из остальных — в синий. Оказалось, что сумма красных чисел делится на сумму синих. Докажите, что $a$ делится на $b.$

Источники: СпбОШ - 2014, задача 11.3(см. www.pdmi.ras.ru)

Показать доказательство

Если $b =1,$ то $a$ делится на $b.$ Поэтому можно считать, что $b≥ 2,$ тогда $a≤N − 1.$
Пусть сумма $a$ чисел равна $3 sa = aN + a1,$ а сумма $b$ чисел равна $3 3 sb =bN +b1 ≥ N .$ По условию $sa$ делится на $sb.$ Обозначим их отношение через $k.$ покажем, что $k≤ N.$ Действительно,

3 3 3 3 sa = aN +a1 ≤ (N − 1)N + a1 ≤(N − 1)(N + N)< (N + 1)N

(последний переход несложно проверить), и значит, $k= s∕s < (N + 1)N3 ∕N3 = N +1. a b$ Поскольку $s =ks , a b$ получим равенство $aN3 +a = k(bN3 + b), 1 1$ или, что то же самое,

3 (a− kb)N =kb1− a1.

Если $a$ не делится на $b$ , т.е. $a ⁄=kb,$ то $|(a − kb)N3 |≥N3,$ и значит, $|kb1− a1|≥ N3.$ Проверим, что на самом деле выполнено неравенство $kb1− a1 ≥ N3,$ т.е. что число $kb1 − a1$ не может быть слишком крупным отрицательным числом. Действительно, $0 ≤a1 ≤ aN$ и $0 ≤b1 < bN,$ и поэтому $kb1 − a1 ≥ −a1 ≥ −aN ≥ −N2.$ Тогда

3 2 3 N ≤ kb1 − a1 ≤ kb1 < kbN ≤ bN ≤ N .

Здесь как раз применяем, что $k ≤N.$ В итоге, противоречие.

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

Задача 9#62512

Даны натуральные числа $a$ и $b$ , причём $a <1000$ . Докажите, что если $a21$ делится на $b10$ , то $a2$ делится на $b.$

Источники: Олимпиада Эйлера, 2010, РЭ, 4 задача(см. old.mccme.ru)

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

Рассмотрим некоторое простое число $p$ , пусть оно входит в число $a$ в степени $k a$ , в число $b$ — в степени $k b$ . Тогда из условия мы имеем, что $21ka ≥10kb$ , а нам требуется показать, что $2ka ≥ kb$ . Пусть это неверно. Тогда $2ka < kb ⇐⇒ 20ka < 10kb ≤21ka$ . Заметим, что первые два числа в неравенстве кратны десяти, поэтому $10kb ≥ 20ka+ 10$ , то есть $21ka ≥ 20ka+ 10 ⇐⇒ ka ≥10$ . Но может ли в число, меньшее $1000$ , какое-то простое число входить в хотя бы десятой степени? Нет, поскольку даже минимальное простое $10 2 > 1024$ этому условию не удовлетворяет. Мы получили противоречие, значит, требуемое доказано.

Ответ:

что и требовалось доказать

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

Задача 10#73199

Найдите наименьшее натуральное $n,$ для которого число $nn$ не является делителем числа $2008!$

Источники: ММО-2008, 11.2(см. mmo.mccme.ru)

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

Если $n2 ≤2008,$ то $2008!$ делится на $nn$ (так как числа $n,2n,...,(n − 1)n$ и $n2$ содержатся среди чисел $1,2,...,2007,2008$ ). Так как $2 2 44 < 2008 <45 ,$ то достаточно проверить делимость $2008!$ на $n n$ при $n >45.$

Ясно, что $2008!$ делится на $45 45 90 45 =5 ⋅3 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $45$ чисел, кратных $5,$ и $90$ чисел, кратных $3$ ( $5⋅45= 22< 2008$ и $3⋅90= 270<2008$ ).

$2008!$ делится на $46 46 46 46 = 2 23 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $46$ чётных чисел и $46$ чисел, кратных $23$ ( $23⋅46= 1058< 2008$ ).

$2008!$ не делится на $47 47 ,$ так как число $47$ простое, и поэтому среди чисел $1,2,...,2007,2008$ есть лишь $42$ числа, кратных $47$ ( $47⋅42 =1974< 2008 <2021= 43 ⋅47$ ).

Ответ:

$47$

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

Задача 11#81746

К натуральному числу $a> 1$ приписали это же число и получили число $b,$ кратное $a2.$ Найдите все возможные значения числа $-b a2.$

Источники: Турнир городов - 2004, весенний тур, базовый вариант, 11.2

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

Если число $a$ $n$ -значно, то $b =(10n+1)a.$ Отсюда

-b (10n+-1)a 10n+-1 a2 = a2 = a

Ясно, что $n−1 a ⁄=10$ (в таком случае $b$ не кратно $2 a$ ), значит,

10n+ 1 1< ---a--< 10

Число $10n +1$ (а тем более, частное) не делится ни на $2,$ ни на $3$ (сумма цифр равна $2$ ), ни на $5,$ поэтому единственное возможное частное – $7.$ Такое частное можно получить например, при $3 n = 3, a= 143= 107+1.$

Ответ:

$7$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#81751

Найдите все пары целых чисел $(x,y),$ для которых числа $x3 +y$ и $x+ y3$ делятся на $x2+ y2.$

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

Пусть $d =$ НОД $(x,y).$ Тогда $x= du, y = dv,$ где $u$ и $v$ взаимно просты. По условию $d3u3+ dv$ делится на $d2,$ поэтому $v$ делится на $d.$ Аналогично $u$ делится на $d.$ Значит, $d= 1,$ то есть $x$ и $y$ взаимно просты. Тогда и число $2 2 x + y$ взаимно просто с $y.$ Число $( 2 2) (3 ) x x +y − x +y = y(xy − 1)$ делится на $2 2 x + y.$ Поскольку $2 2 x + y$ и $y$ взаимно просты, то $xy− 1$ делится на $2 2 x + y .$ Но это возможно только при $|xy|≤ 1.$ Действительно, в противном случае $2 2 0 <|xy− 1|< 2|xy|≤x + y .$ Непосредственная проверка всех оставшихся вариантов $(x,y =0,±1)$ дает восемь решений $(±1,±1),(0,±1),(±1,0).$

Ответ:

$(1,1), (1,0), (1,−1), (0,1), (0,−1), (−1,1), (−1,0), (−1,−1)$

Предыдущий раздел

Следующий раздел