Задача
NT-B2-M01-P004 Когда НОД больше единицы
#4
★★☆☆☆ Уровень 2 из 5
Найдите все натуральные \(n\), для которых \( \gcd(n^2+1,n+3)>1 \).
Сведите НОД к \( \gcd(n+3,10) \).
По модулю \(n+3\) имеем \(n\equiv-3\), значит \(n^2+1\equiv10\). Поэтому \( \gcd(n^2+1,n+3)=\gcd(10,n+3) \). Этот НОД больше \(1\), если \(n+3\) делится на \(2\) или на \(5\). Следовательно, \(n\) нечётно или \(n\equiv2\pmod5\).
Здесь появляется типичный финальный шаг: перевести условие НОД в объединение классов остатков.