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

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

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

Уравнения в целых числах

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

Решите уравнение \(x - y = 1\) в целых числах.

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

Выразим \(y\): \[y = x - 1.\] Таким образом, при любом \(x\in\mathbb{Z}\) получим, что \(y = x - 1\) – целое число, то есть ответом будет множество всевозможных пар вида \((x; x - 1)\), где \(x\in\mathbb{Z}\), то есть \(\{(x; x - 1)\)| \(x\in\mathbb{Z}\}\).

Ответ:

\(\{(x; x - 1)\)| \(x\in\mathbb{Z}\}\)

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

Решите уравнение \(48x + 36y = 0\) в целых числах.

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

Выразим \(y\): \[y = -\dfrac{4}{3}x.\] Таким образом, только при \(x = 3k\), где \(k\in\mathbb{Z}\) получим, что \(y = -4k\) – целое число, то есть ответом будет множество всевозможных пар вида \((3k; -4k)\), где \(k\in\mathbb{Z}\), то есть \(\{(3k; -4k)\)| \(k\in\mathbb{Z}\}\).

Ответ:

\(\{(3k; -4k)\)| \(k\in\mathbb{Z}\}\)

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

Докажите, что если НОД\((n; m) > 1\), где \(n, m\in\mathbb{N}\), то не существует целых чисел \(p\) и \(q\), таких что \(pn + qm = 1\).

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

\(n\) и \(m\) делятся на НОД\((n; m)\), следовательно, \(pn + qm\) делится на НОД\((n; m) > 1\), следовательно, \(pn + qm\) не может быть равно 1.

Ответ:

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

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

Найдите какие-нибудь \(p, q\in\mathbb{Z}\) такие, что НОД\((9; 5) = 9p + 5q\).

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

НОД\((9; 5) = 1\).

НОД\((9; 5) =\) НОД\((9 - 5 = 4; 5) =\) НОД\((9 - 5 = 4; 5 - (9 - 5) = 1)\), таким образом, \(1 = 5 - (9 - 5) = 2\cdot 5 + (-1)\cdot 9\).

Ответ:

\(p = -1\), \(q = 2\).

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

Решите уравнение \[x^2 + 8y = 32\] в целых числах.

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

Так как в равенстве \[x^2 + 8y = 32\] все слагаемые, кроме первого, делятся на \(8\), то и первое слагаемое должно делиться на \(8\).

Докажем от противного, что если \(x^2\, \vdots \,8\) при целом \(x\), то \(x\, \vdots \, 4\):
Пусть \(x\) не делится на \(4\). Если \(x\) не делится на \(2\), то \(x^2\) не делится на \(2\), что неверно. Если \(x\) делится на \(2\), то \(x = 2y\), где \(y\) – целое нечётное, тогда \(x^2 = 4y^2\), но \(y^2\) – нечётное, следовательно, \(x^2\) не делится на \(8\) – противоречие.

Таким образом, \(x\) во всех решениях имеет вид \(x = 4k\), где \(k\) – целое. Но все ли \(x\) вида \(x = 4k\) подходят? Выразим \(y\) при условии \(x = 4k\):\[16k^2 + 8y = 32\qquad\Leftrightarrow\qquad y = 4 - 2k^2\] – целое при \(k\in\mathbb{Z}\), следовательно, решениями уравнения являются всевозможные пары вида \((4k; 4 - 2k^2)\), \(k\in\mathbb{Z}\).

Ответ:

\(\{(4k; 4 - 2k^2)\)| \(k\in\mathbb{Z}\}\)

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

Известно, что при некоторых действительных \(m\) и \(n\) числа \(m^2 - n^2\) и \(2mn\) – натуральные. Обязательно ли \(m\) и \(n\) целые?

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

Обозначим \(a = 2mn\), \(b = m^2 - n^2\), тогда \[m = \dfrac{a}{2n},\qquad b = \dfrac{a^2}{4n^2} - n^2\qquad\Rightarrow\qquad (n^2)^2 + bn^2 - \dfrac{a^2}{4} = 0.\] Решая полученное биквадратное уравнение на \(n\), находим: \[n = \sqrt{\dfrac{\sqrt{a^2 + b^2} - b}{2}},\] тогда \[m = \dfrac{a}{\sqrt{2}\cdot\sqrt{\sqrt{a^2 + b^2} - b}}.\]

Пусть, например, \(a = b = 1\), тогда \(n = \sqrt{\dfrac{\sqrt{2} - 1}{2}}\), \(m = \dfrac{1}{\sqrt{2}\cdot\sqrt{\sqrt{2} - 1}}\) – не являются целыми числами (например, \(n^2 = \dfrac{1}{\sqrt{2}} - 0,5\) – явно не целое).

Ответ:

Нет

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

Докажите, что для любых натуральных чисел \(n\) и \(m\) существуют целые числа \(p\) и \(q\), такие что НОД\((n; m) = pn + qm\).

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

Убедимся, что любой общий делитель всякой пары натуральных чисел \((n; m)\) является также и общим делителем пары \((m; n - m)\): если уменьшаемое делится на число \(k\), то оно имеет вид \(n = ak\), если вычитаемое делится на число \(k\), то оно имеет вид \(m = bk\), тогда \[n - m = ak - bk = (a - b)k,\] то есть их разность также делится на число \(k\).

Аналогично доказывается, что любой общий делитель пары \((m; n - m)\) является общим делителем пары \((n; m)\), следовательно, \[\text{НОД}(n; m) =\ \text{НОД}(m; n - m).\]

Пусть \(n > m\). Можно свести НОД\((n; m)\) к наибольшему общему делителю другой пары чисел, в которой наибольшее из чисел окажется меньше, чем \(n\), а именно: НОД\((n; m) =\) НОД\((m; n - m)\).

Таким образом, можно получить последовательность равенств вида \(... =\) НОД\((k; 0)\) или вида \(... =\) НОД\((k; k)\), но НОД\((k; k) =\) НОД\((k; 0)\).

Такую последовательность действительно можно получить, так как при \(n > m\) получается, что \(n > m\) и \(n > n - m\), то есть в равенстве НОД\((n; m) =\) НОД\((m; n - m)\) максимум из чисел под знаком НОД в правой части с каждым таким шагом уменьшается по крайней мере на 1, но числа \(n\) и \(m\) – конечны, следовательно, через конечное число преобразований можно получить цепочку равенств вида \(... =\) НОД\((k; 0)\).

 

\(\bullet\) Назовём выражение вида \(an + bm\), где \(a, b\in\mathbb{Z}\) линейной комбинацией над \(\mathbb{Z}\) чисел \(n\) и \(m\). Ясно, что сумма линейных комбинаций над \(\mathbb{Z}\) чисел \(n\) и \(m\) снова линейная комбинация над \(\mathbb{Z}\) чисел \(n\) и \(m\), разность линейных комбинаций над \(\mathbb{Z}\) чисел \(n\) и \(m\) снова линейная комбинация над \(\mathbb{Z}\) чисел \(n\) и \(m\).

 

Последнее полученное равенство можно продолжить: \[... =\ \text{НОД}(k; 0) = k.\] При этом число \(k\) получалось последовательным вычитанием из линейной комбинации над \(\mathbb{Z}\) чисел \(n\) и \(m\) линейных комбинаций над \(\mathbb{Z}\) чисел \(n\) и \(m\), то есть \(k\) есть линейная комбинация над \(\mathbb{Z}\) чисел \(n\) и \(m\), следовательно, существуют целые числа \(p\) и \(q\), такие что \(k = pn + qm\).

Ответ:

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