Республиканская олимпиада по математике, 1999 год, 10 класс

Пусть $a=(n+1)^m-n$ и $b=(n+1)^{m+3}-n$, где $m$ и $n$ — натуральные числа.
а) Докажите, что $a$ и $b$ взаимно просты, если $m$ не делится на 3.
б) Найдите все пары $(m,n)$, для которых $a$ и $b$ не взаимно простые.

Комментарий/решение

Если $p | $НОД($(n+1)^m - n, (n + 1)^{m + 3} - n$), то НОД($p, n$) = НОД($p, n + 1$) = 1

Дальше по алгоритму Евклида: $p | $ НОД($a, b$) =

НОД($a, b - a$) = НОД($a, (n + 1)^{m+3} - (n+1)^m$) = НОД($a, (n+1)^m \cdot ((n + 1)^3 - 1)$) = НОД($a, (n+ 1)^3 - 1$), так как НОД($p, n + 1$) = 1

(1) НОД($(n + 1)^m - n, (n+ 1)^3 - 1$) =

НОД($(n+1)^m - n - (n+1)^m \cdot ((n+ 1)^3 - 1)), (n+ 1)^3 - 1$) =

(2) НОД($(n+1)^{m-3} - n, (n+ 1)^3 - 1$) =

НОД($(n+1)^{m-3} - n - (n+1)^m \cdot ((n+ 1)^3 - 1)), (n+ 1)^3 - 1$) =

(3) НОД($(n+1)^{m-6} - n, (n+ 1)^3 - 1$) = . . . (степень $m$ из (1) просто сокращается на 3)

. . .

НОД($(n+1)^{\text{остаток $m$ на три}} - n, (n+ 1)^3 - 1$)

Заметим что если остаток 1 или 2, то значение выше будет принимать 1. Значит они взаимно просты только когда $m$ не делится на 3

Теперь из выше понимаем, что:

НОД($a, b$) = НОД($(n + 1)^0 - n, (n + 1)^3 - 1$) =

НОД($n - 1, n^3 + 3n^2 + 3n$) = НОД($n-1, n^2 +3n + 3$), так как НОД($p, n$) = 1

НОД($n - 1, n^2 +3n + 3$) = НОД($n -1, n^2 +3n + 3 - (n + 4) \cdot (n - 1)$) = НОД($n -1, 7$)= 7

$\Rightarrow 7 | n - 1 \Rightarrow n = 7k + 1 \text{ и } m = 3l, \forall k, l \in N$

Проверяем ответ и все правильно