Олимпиадные задачи по математике "Теория чисел" ( с решением)

Олимпиадные задачи «Теория чисел»

Задача 1.  Петин счет в банке содержит 500 долларов. Банк разрешает совершать операции только двух видов: снимать 300 долларов или добавлять 198 долларов. 
Какую максимальную сумму Петя может снять со счета, если других денег у него нет? 

Задача 2.  Наибольший общий делитель (НОД) натуральных чисел m и n равен 1. Каково наибольшее возможное значение НОД чисел m+2000n и n+2000m?

Задача 3. Докажите, что произведение любых трёх последовательных натуральных чисел делится на 6.  

Задача 4. Найдите все натуральные  n > 1,  для которых  n³ – 3  делится на  n – 1.

Задача 5. Докажите, что любое натуральное число, десятичная запись которого состоит из 3-х  одинаковых цифр, делится на 37.

Задача 6^*. Сумма трёх различных наименьших делителей некоторого числа A равна 8. На сколько нулей может оканчиваться число A?

Задача 7^*. Докажите, что число, имеющее нечётное число делителей, является точным квадратом.

Задача 8 ^*.  Найдите наименьшее натуральное n, для которого

 (n + 1)(n + 2)(n + 3)(n + 4)  делится на 1000.

Задача 9^* . Даны числа: 4, 14, 24, ..., 94, 104. Докажите, что из них нельзя вычеркнуть сперва одно число, затем из оставшихся ещё два, затем ещё три и, наконец, ещё четыре числа так, чтобы после каждого вычёркивания сумма оставшихся чисел делилась на 11.

Задача 10^*.  Докажите, что все числа 10017, 100117, 1001117, ... делятся на 53.

Задача 11^*. Доказать, что  7 + 7² + ... + 7^4K,  где K - любое натуральное число, делится на 400.

Задача 12^*    Найдите все такие числа a, что для любого натурального n число  an(n + 2)(n + 3)(n + 4)  будет целым.                        

Задача 13*  Назовём натуральное число хорошим, если среди его делителей есть ровно два простых числа.  Могут ли 18 подряд идущих натуральных чисел быть хорошими?

Задача 14^* . Доказать, что  1¹⁹⁸³ + 2¹⁹⁸³ + ... + 1983¹⁹⁸³  делится на  1 + ... + 1983.

Задача 15^* .    Сумма кубов трёх последовательных натуральных чисел оказалась кубом натурального числа. Докажите, что среднее из этих трёх чисел делится на 4.                                                                         

Решения к задачам

Решение задачи 1: Поскольку 300 и 198 делятся на 6, Петя сможет снять лишь сумму, кратную 6 долларам. Максимальное число, кратное 6 и не превосходящее 500, - это 498.

Докажем, что снять 498 долларов возможно. Произведем следующие операции: 500-300=200, 200+198=398, 398-300=98, 98+198=296, 296+198=494. Сумма, лежащая в банке, уменьшилась на 6 долларов.

Проделав аналогичную процедуру 16 раз, Петя снимет 96 долларов. Затем он может снять 300, положить 198 и снова снять 300. В результате у него будет 498 долларов.

Решение задачи 2: Пусть a=2000m+n, b=2000n+m, d - наибольший общий делитель a и b. Тогда d делит также числа

2000a-b=(2000²-1)m и 2000b-a=(2000²-1)n.

Поскольку m и n взаимно просты, то d делит 2000²-1. С другой стороны, при m=2000²-2000-1, n=1, получаем a=(2000²-1)(2000-1), b=2000²-1=d.

Ответ: 2000²-1.

Решение задачи 3: Среди этих трёх чисел есть хотя бы одно чётное число. Значит, в разложении произведения на простые множители есть множитель 2.
  Среди этих трёх чисел одно число делится на 3. Значит, в разложении произведения на простые множители есть множитель 3.
  В разложении произведения на простые множители есть простые числа 2 и 3. Значит, оно делится на их произведение, то есть на 6.

Решение задачи 4 :   n³ – 3 = (n³ – 1) – 2.  Первое слагаемое делится на  n – 1,  значит, и 2 делится на  n – 1.  Следовательно,  n – 1 = 1 или  ,  n – 1=2.

Ответ:  n = 2, 3.

Решение задачи 5: Такое число делится на  111 = 3·37.

Решение задачи 6^*: Число 8 можно представить в виде суммы трёх различных натуральных чисел двумя способами:  8 = 1 + 2 + 5 = 1 + 3 + 4.  Числа 1, 3 и 4 не могут быть тремя наименьшими делителями числа A: если A делится на 4, то оно делится и на 2. Значит, три наименьших делителя A – это 1, 2 и 5. Таким образом, A делится на 10, но не делится на 4. Следовательно, число A оканчивается ровно на один нуль.
Ответ^: На один нуль.

Решение задачи 7^*:  Если d – делитель числа n, то ⁿ/_d  – также делитель. Таким образом, все делители числа делятся на пары. Если число имеет нечётное число делителей, то делители какой-то пары совпадают. Тогда  d = ⁿ/_d,  откуда  n = d ²,  то есть число n – квадрат целого числа.

Решение задачи 8 ^*:  При любом натуральном n данное произведение делится на 8, так как среди любых четырёх последовательных натуральных чисел одно делится на 4 и еще одно – на 2. Следовательно, достаточно найти наименьшее n, для которого данное произведение делится на  125 = 5³.  Так как на 5 может делиться только один из множителей, то n – наименьшее, если множитель, делящийся на 125, – наибольший. Значит,  n + 4 = 125,  то есть  n = 121.

Ответ: n = 121.

Решение задачи 9^*: Всего дано 11 чисел, а нужно вычеркнуть 10 чисел. Поэтому в конце должно остаться одно число, кратное 11, то есть число 44. С другой стороны, число 44 мы должны вычеркнуть самым первым. Действительно, сумма всех данных чисел равна  11·108 : 2,  поэтому она делится на 11. Следовательно, если после вычёркивания одного числа сумма оставшихся чисел делится на 11, то вычеркнутое число тоже делится на 11.

Решение задачи10^*: Умножив такое число на 9, получим число 9010...053, которое делится на 53, так как  901 = 53·17.  Значит, и исходное число делится на 53.

Решение задачи11^*: Данную сумму можно сгруппировать следующим образом:
(7 + 7² + 7³ + 7⁴) + (7⁵ + 7⁶ + 7⁷ + 7⁸) + ... + (7^4K–3 + 7^4K–2 + 7^4K–1 + 7^4K) = (7 + 7² + 7³ + 7⁴)(1 + 7⁴ + 7⁸ + ... + 7^4K–4).  Сумма (7 + 7² + 7³ + 7⁴) = 7·400  делится на 400, откуда и вытекает доказываемое.

Решение задачи 12^*:     Подставив  n = 1,  n = 3  и  n = 4,  получаем, что числа 2²·3·5a, 2·3²·5·7a и 2⁶·3·7a – целые. Значит, a – рациональное число, имеющее несократимую запись ^p/_q, где q является делителем числа  НОД(2²·3·5, 2·3²·5·7, 2⁶·3·7) = 6.  Итак,  a = ^k/₆  при некотором целом k.
   Осталось показать, что все числа такого вида подходят. Действительно, одно из трёх последовательных чисел  n + 2,  n + 3,  n + 4  делится на 3, а одно из последовательных чисел  n + 2,  n + 3  делится на 2; значит,  n(n + 2)(n + 3)(n + 4)  делится на 6. Поэтому      – целое число.

Ответ :     ,  где k – любое целое число.

Решение задачи 13*:  Предположим, что нашлись 18 хороших чисел подряд. Среди них найдутся три числа, делящихся на 6. Пусть это числа 6n,  6(n + 1)  и  6(n + 2).  Поскольку эти числа – хорошие, и в разложение каждого из них на простые множители входят двойка и тройка, других простых делителей у них  быть не может. Лишь одно из трёх подряд идущих натуральных чисел n,  n + 1,   n + 2  может делиться на 3. Значит, остальные два являются степенями двойки. Но пары степеней двойки, отличающихся не более чем на два, – это только  (1, 2)   и  (2, 4);  поэтому  n ≤ 2.  Однако тогда среди наших 18 чисел есть простое  число 13 (так как  6n ≤ 13 ≤ 6(n + 2)),  не являющееся хорошим. Противоречие. Ответ: Не могут.

Решение задачи 14^*:  Докажем, что для произвольного нечётного  n = 2m – 1  сумма  S = 1ⁿ + 2ⁿ + ... + nⁿ  делится на  1 + 2 + ... + n = nm. Числа n и m взаимно просты, поэтому достаточно проверить, что S делится на n и на m. 
   S = (1ⁿ + nⁿ) + (2ⁿ + (n – 1)ⁿ) + ... + ((m – 1)ⁿ + (m + 1)ⁿ) + mⁿ.  Сумма в каждой скобке, кроме последней, делится на  n + 1 = 2m,  поэтому S делится на m. 
   С другой стороны,  S = (1ⁿ + (n – 1)ⁿ) + (2ⁿ + (n – 2)ⁿ) + ... + ((m – 1)ⁿ + mⁿ) + nⁿ,  поэтому S делится на n.

Решение задачи 15^*:  В решении латинскими буквами везде обозначены натуральные числа.
  По условию,  (x – 1)³ + x³ + (x + 1)³ = y³,  или  3x(x² + 2) = y³.  Значит, y делится на 3,  y = 3z  и   x(x² + 2) = 9z³. Очевидно, НОД(x, x² + 2) ≤ 2.
  Пусть  НОД(x, x² + 2) = 1.  Тогда либо  x = 9u³ и  x² + 2 = v³,  либо  x = u³,  x² + 2 = 9v³  при некоторых натуральных u, v. В первом случае  81u⁶ + 2 = v³,  что невозможно, так как куб целого числа при делении на 9 дает остаток 0 или ±1. Аналогично, второе равенство влечёт, что  u⁶ + 2 = 9v³,  что невозможно по тем же причинам.
  Итак,  НОД(x, x² + 2) = 2,  x(x² + 2) = 9z³.  Тогда x (и, следовательно, z) чётно, поэтому  x(x² + 2)  делится на 8. Поскольку  x² + 2  не делится на 4, получаем, что x делится на 4.