Математикадан республикалық олимпиада, 1998-1999 оқу жылы, 10 сынып

$m$ және $n$ — натурал сандар. $a={{\left( n+1 \right)}^{m}}-n$ және $b={{\left( n+1 \right)}^{m+3}}-n$ болсын.
а) Егер $m$ саны 3-ке бөлінбейтін болса, онда $a$ мен $b$-ның өзара жай саңдар екенін дәлелде.
б) $a$ және $b$ өзара жай сандар болмайтындай, барлық $m$ және $n$ сандар жұптарын тап.

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

Если $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$

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