Математика
Русский язык

19. Задачи на теорию чисел

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Наибольший общий делитель чисел и наименьшее общее кратное

Задание 1
Уровень задания: Легче ЕГЭ

Найдите НОД\((34,1717)\).

Добавить задание в избранное

НОД\((34,1717)=\) НОД\((2\cdot17,101\cdot17)=17\), так как НОД\((2,101)=1\).

Ответ:

\(17\)

Задание 2
Уровень задания: Легче ЕГЭ

Найдите НОД\((60,539)\).

Добавить задание в избранное

НОД\((60,539)=\) НОД\((2^2\cdot3\cdot5,7^2\cdot11)=1\), так как в разложении чисел 60 и 539 нет одинаковых простых множителей.

Ответ:

\(1\)

Задание 3
Уровень задания: Легче ЕГЭ

Докажите, что дробь \(\dfrac{18n+1}{45n+1}\) несократима.

Добавить задание в избранное

Пусть НОД\((18n+1,45n+1)=a\), тогда по определению наибольшего общего делителя \((18n+1)\, \vdots \, a\) и \((45n+1)\, \vdots \,a\), но тогда \(\bigl(5(18n+1)-2(45n+1)\bigr)\, \vdots \,a\).

Так как \(5(18n+1)-2(45n+1)=90n+5-90n-2=3\), то \(3\, \vdots \, a\), значит, \(a\) равно либо \(1\), либо \(3\).

Но так как \(18n+1\) не делится на \(3\), то \(a=1\), следовательно, НОД\((18n+1,45n+1)=1\).

 

Таким образом, дробь \(\dfrac{18n+1}{45n+1}\) – несократима.

Ответ:

Доказательство

Задание 4
Уровень задания: Легче ЕГЭ

Коля получает пятёрку через каждые \(6\) дней, Вася получает пятёрку через каждые \(9\) дней, а Андрей получает пятёрку через каждые \(15\) дней. Те дни, когда они втроём получают по пятёрке, они называют днями икс. Через сколько дней наступит следующий день икс, если известно, что сегодня тоже день икс?

Добавить задание в избранное

Количество дней до следующего дня икс равно \(НОК(6; 9; 15) = НОК(2\cdot 3;\, 3\cdot 3;\, 3\cdot 5) = 2\cdot 3\cdot 3\cdot 5 = 90\).

Ответ: 90

Задание 5
Уровень задания: Легче ЕГЭ

Известно, что \(a, b\in\mathbb{N}\), при этом \(ab = 2016\). Какое наибольшее значение может принимать \(НОД(a; b)\)?

Добавить задание в избранное

Пусть \(d = НОД(a; b)\), тогда оба числа \(a\) и \(b\) делятся на \(d\), следовательно, \(ab\) делится на \(d^2\).

Разложим \(2016\) на простые множители: \(2016 = 2^5\cdot 3^2\cdot 7\). Наибольший полный квадрат, на который может делиться \(2016\), равен \(2^4\cdot 3^2 = 12^2\), то есть \(d\leqslant 12\).

Проверим, может ли быть так, что \(d = 12\). Пусть \(d = 12\), тогда для некоторых натуральных \(m\) и \(n\) справедливо \(a = 12m\), \(b = 12n\), откуда \(144mn = 2016\), следовательно, \(mn = 14\). Положим \(m = 2\), \(n = 7\), тогда \(a = 24\), \(b = 84\), \(ab = 2016\), \(НОД(a; b) = НОД(24; 84) = 12\) – подходит по условию. Таким образом, ответ: наибольшее возможное значение \(НОД(a; b)\) равно \(12\).

Ответ: 12

Задание 6
Уровень задания: Равен ЕГЭ

Известно, что \(a, b\in\mathbb{N}\) взаимно просты и дробь \(\dfrac{3a + 5b}{5a + 3b}\) сократима на число \(d\in\mathbb{N}\), \(d\neq 1\). Найдите наибольшее возможное \(d\).

Добавить задание в избранное

\[d = НОД(3a + 5b; 5a + 3b)\,.\]

Число \(5(3a + 5b) - 3(5a + 3b) = 16b\) делится на \(d\). Число \(5(5a + 3b) - 3(3a + 5b) = 16a\) делится на \(d\). Так как \(a\) и \(b\) взаимно просты, то \(16\) делится на \(d\).

Проверим, может ли быть \(d = 16\). Число \(3a + 5b - (5a + 3b) = 2(b - a)\) делится на \(d\). Если \(d = 16\), то \((b - a)\) делится на \(8\).

Возьмём, например, \(b = 9\), \(a = 1\), тогда \[\dfrac{3a + 5b}{5a + 3b} = \dfrac{48}{32} = \dfrac{16\cdot 3}{16\cdot 2}\,,\] то есть \(d = 16\) – подходит.

Ответ: 16

Задание 7
Уровень задания: Равен ЕГЭ

Известно, что \(n\in\mathbb{N}\). Может ли число \(n(n + 1)\) быть степенью натурального числа (полным квадратом, кубом и т.д.)?

Добавить задание в избранное

Пусть \(n(n + 1) = k^m\). Так как числа \(n\) и \(n + 1\) взаимно просты, то число \(n\) само представимо в виде \(n = a^m\), \(a\in\mathbb{N}\) (всякое число \(p\), являющееся простым делителем \(n\), входит в разложение на множители числа \(k^m\) в степени, кратной \(m\), но \(n + 1\) не делится на \(p\), следовательно, \(p\) входит в разложение на множители числа \(n\) в степени, кратной \(m\)), а число \(n + 1\) представимо в виде \(n + 1 = b^m\), \(b\in\mathbb{N}\), причём \(b > a\), но тогда \[1 = (n + 1) - n = b^m - a^m = (b - a)(b^{m - 1} + b^{m - 2}a + ... + ba^{m - 2} + a^{m - 1})\,,\] откуда \(b^{m - 1} + b^{m - 2}a + ... + ba^{m - 2} + a^{m - 1} = 1\), что невозможно при условии \(m\geqslant 2\), \(a\in\mathbb{N}\), \(b > a\), следовательно, наше предположение неверно и \(n(n + 1)\) не может быть степенью натурального числа.

Ответ:

Нет