Теория чисел
Теория и подборка олимпиадных задач по теории чисел.
Полезные материалы
- Делимость (Фоксфорд.Учебник)
- Признаки делимости (Фоксфорд.Учебник)
- Простые и составные числа (Фоксфорд.Учебник)
- Основная теорема арифметики (Фоксфорд.Учебник)
- Наибольший общий делитель (Фоксфорд.Учебник)
- Деление с остатком (Фоксфорд.Учебник)
- Алгоритм Евклида (Фоксфорд.Учебник)
- Наименьшее общее кратное (Фоксфорд.Учебник)
- Линейные диофантовы уравнения с двумя неизвестными (Фоксфорд.Учебник)
- Сравнение по модулю (Фоксфорд.Учебник)
- Малая теорема Ферма (Фоксфорд.Учебник)
- Теорема Эйлера (Фоксфорд.Учебник)
- Китайская теорема об остатках (Фоксфорд.Учебник)
- Неравенства в теории чисел (Фоксфорд.Учебник)
Записи онлайн-занятий
Подборка задач
- Существуют ли такие двузначные числа $\overline{ab}$ и $\overline{cd}$, что $\overline{ab} \cdot \overline{cd} = \overline{abcd}$. (Региональный этап, 1994-1995, 8 класс, №1)
- Натуральное число $n$ является произведением двух различных простых чисел, а сумма всех его делителей, считая 1, но не считая $n$, равна 1000. Найдите все такие $n$. (Региональный этап, 1993-1994, 9 класс, №1)
- Даны натуральные числа M и N, большие десяти, состоящие из одинакового количества цифр и такие, что M = 3N. Чтобы получить число M, надо в числе N к одной из цифр прибавить 2, а к каждой из остальных цифр прибавить по нечётной цифре. Какой цифрой могло оканчиваться число N? (Н. Агаханов, Региональный этап, 2012-2013, 9 и 10 классы, №1)
- Числа от 1 до 10 разбили на две группы так, что произведение чисел в первой группе делится на произведение чисел во второй. Какое наименьшее значение может быть у частного от деления первого произведения на второе? (А. Голованов, Окружной этап, 2002-2003, 8 класс, №1)
- Ученик за одну неделю получил 17 оценок (каждая из них – 2, 3, 4 или 5). Среднее арифметическое этих 17 оценок – целое число. Докажите, что какую-то оценку он получил не более двух раз. (Н. Агаханов, И. Богданов, Региональный этап, 2013-2014, 10 класс, №1)
- Рассматривается постедовательность натуральных чисел 2, 6, 30, ..., в которой $k$-й член есть произведение первых $k$ простых чисел. Извество, что разность некоторых двух чисел этой последовательности равна 30000. Найдите эти числа. (Региональный этап, 1993-1994, 10 класс, №1)
- Три натуральных числа таковы, что последняя цифра суммы любых двух из них является последней цифрой третьего числа. Произведение этих трёх чисел записали на доске, а затем всё, кроме трёх последних цифр этого произведения, стёрли. Какие три цифры могли остаться на доске? (Н. Агаханов, Региональный этап, 2012-2013, 11 класс, №1)
- Найдите все такие числа $a$, что для любого натурального $n$ число $an(n + 2)(n + 4)$ будет целым. (О. Подлипский, Региональный этап, 2010-2011, 9 класс, №5)
- Найдите все такие числа $a$, что для любого натурального $n$ число $an(n + 2)(n + 3)(n + 4)$ будет целым. (О. Подлипский, Региональный этап, 2010-2011, 10 и 11 классы, №5)
- Назовём натуральное число интересным, если сумма его цифр – простое число. Какое наибольшее количество интересных чисел может быть среди пяти подряд идущих натуральных чисел? (О. Подлипский, Региональный этап, 2014-2015, 9 класс, №2)
- На доске написано число 1. Если на доске написано число $а$, его можно заменить любым числом вида $a + d$, где $d$ взаимно просто с $а$ и $10 \leqslant d \leqslant 20$. Можно ли через несколько таких операций получить на доске число 18! ? (И. Рубанов, Региональный этап, 2010-2011, 8 класс, №6)
- Докажите, что уравнение $x^3 + y^3 = 4 (x^2y + xy^2 + 1)$ не имеет решений в целых числах. (А. Калинин, Окружной этап, 1992-1993, 9 класс, №5)
- Дано натуральное число $n>1$. Для каждого делителя $d$ числа $n + 1$, Петя разделил число $n$ на $d$ с остатком и записал на доску неполное частное, а в тетрадь -- остаток. Докажите, что наборы чисел на доске и в тетради совпадают. (С. Берлов, Окружной этап, 2007-2008, 9 класс, №5)
- Можно ли расставить по кругу 1995 различных натуральных чисел так, чтобы для любых двух соседних чисел отношение большего из них к меньшему было простым числом? (А. Шаповалов, Окружной этап, 1994-1995. 9 класс, №2)
- Числа от 1 до 37 записали в стороку так, что сумма любых первых нескольких чисел делится на следующее за ними число. Какое число стоит на третьем месте, если на первом месте написано число 37, а на втором -- 1? (А. Шаповалов, Окружной этап, 1996-1997, 8 класс, №6)
- Найдите все простые числа $p$ и $q$ такие, что $p+q = (p - q)^3$. (Р. Женодаров, Окружной этап, 2000-2001, 11 класс, №1)
- При каких натуральных $n$ найдутся такие целые $a$, $b$, $c$, что их сумма равна нулю, а число $a^n + b^n + c^n$ -- простое? (В. Сендеров, Окружной этап, 2006-2007, 11 класс, №5)
- Натуральные числа $m$ и $n$ таковы, что $\mbox{НОК}(m,n) + \mbox{НОД}(m,n) = m + n$. Докажите, что одно из чисел $m$ или $n$ делится на другое. (С. Токарев, Окружной этап, 1994-1995, 10 класс, №2)
- Назовём натуральное число хорошим, если среди его делителей есть ровно два простых числа. Могут ли 18 подряд идущих натуральных чисел быть хорошими? (О. Подлипский, Финал, 2012-2013, 10 класс, №1)
- Целые числа $x$, $y$ и $z$ таковы, что $(x-y)(y-z)(z-x) = x+y+z$. Докажите, что число $x+y+z$ делитя на 27. (Н. Агаханов, Финал, 1992-1993, 9 класс, №5)
- Учитель записал Пете в тетрадь четыре различных натуральных числа. Для каждой пары этих чисел Петя нашёл их наибольший общий делитель. У него получились шесть чисел: 1, 2, 3, 4, 5 и $N$, где $N > 5$. Какое наименьшее значение может иметь число $N$? (О. Дмитриев, Региональный этап, 2013-2014, 9 класс, №3)
- Найдите все такие тройки простых чисел p, q, r, что четвёртая степень каждого из них, уменьшенная на 1, делится на произведение двух остальных. (В. Сендеров, Региональный этап, 2010-2011, 9 класс, №7)
- Найдите все такие пары простых чисел $p$ и $q$, что $p^3 - q^5 = (p + q)^2$. (С. Токарев, Окружной этап, 1996-1997, 8 класс, №7)
- Найдите наименьшее натуральное число, не представимое в виде $\dfrac{2^a - 2^b}{2^c - 2^d}$, где $a$, $b$, $c$, $d$ -- натуральные числа. (В. Сендеров, Финал, 2004-2005, 10 класс, №1)
- Докажите, что для натуральных чисел $k$, $m$ и $n$ справедливо неравенство $$\mbox{НОК}(k,m) \cdot \mbox{НОК}(m,n) \cdot\mbox{НОК}(n,k) \geqslant (\mbox{НОК}(k,m,n))^2.$$ (А. Голованов, Финал, 1993-1994, 10 класс, №5)
- Даны такие натуральные числа $a$ и $b$, что число $\dfrac{a+1}{b} + \dfrac{b+1}{a}$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $\sqrt{a+b}$. (Финал, 1993-1994, 11 класс, №1)
- Для каких натуральных чисел $n$ числа 1, 2, 3, ..., $4n$ можно разбить на $n$ групп по четыре числа так, чтобы в каждой группе одно из чисел равнялось среднему арифметическому трех остальных? (Региональный этап, 1993-1994, 11 класс, №7)
- Пусть $a$, $b$ и $c$ -- попарно взаимно простые натуральные числа. Найдите все возможные значения $\dfrac{(a+b)(b+c)(c+a)}{abc}$, если известно, что это число целое. (Д. Храмцов, Окружной этап, 1995-1996, 9 класс, №3)
- Леша поставил в клетки таблицы $22\times 22$ натуральные числа от 1 до $22^2$. Врено ли, что Олег может выбрать такие две клетки, соседние по стороне или вершине, что сумма чисел, стоящих в этих клетках, делится на 4? (О. Подлипски, Финал, 2004-2005, 9 класс, №2)
- Даны натуральные числа a и b, причём $a < 1000$. Докажите, что если $a^{21}$ делится на $b^{10}$, то $a^2$ делится на $b$. (П. Кожевников, Региональный этап, 2009-2010, 8 класс, №4)
- Найдите все четверки попарно различных простых чисел $p$, $q$, $r$ и $s$ таких, что их сумма -- простое число, а числа $p^2 + rs$ и $p^2 + qr$ -- квадраты натуральных чисел. (Р. Женодаров, Окружной этап, 1993-1994, 9 класс, №7)
- На доске записано натуральное число. Его последняя цифра запоминается, затем стирается и множенная на 5 прибавляется к тому числу, которое осталось на доске после стирания. Первоначально было записано число $7^{1998}$. Может ли после применения нескольких таких операций получиться число $1998^7$? (Л. Емельянов, Окружной этап, 1997-1998, 11 класс, №6)
- Найдите все простые числа, которые являются одновременно суммой двух простых чисел и разностью двух простых чисел. (С. Кожухов, Окружной этап, 1993-1994, 10 класс, №7)
- Сумма кубов трех последовательных чисел оказалась кубом натурального числа. Докажите, что среднее из этих чисел делится на 4. (В. Сендеров, Финал, 2005-2006, 10 класс, №2)
- Существует ли такая бесконечная последовательность натуральных чисел, что для любого натурального $k$ сумма любых $k$ идущих подряд членов этой последовательности делится на $k + 1$? (Финал, 2014-2015, 10 класс, №6)