Задача
NT-B1-M11-P014 НОД с параметром
#14
★★★☆☆ Уровень 3 из 5
Найдите \(\gcd(n^2+1,n+2)\) для натурального \(n\).
Замените \(n\) на \(-2\) по модулю \(n+2\).
По модулю \(n+2\) имеем \(n\equiv-2\), поэтому \(n^2+1\equiv4+1=5\). Значит НОД равен \(\gcd(n+2,5)\). Он равен \(5\), если \(n\equiv3\pmod5\), и \(1\) иначе.
Типичная олимпиадная обработка НОД выражений.