Задача
NT-B2-M01-P018 Квадрат и куб
Пусть \( \gcd(a,b)=1 \). Найдите \( \gcd(a^2+b^2,a^3+b^3) \).
Покажите, что нечётный простой общий делитель невозможен, работая с \(ab^{-1}\).
Пусть нечётный простой \(p\) делит оба выражения. Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Тогда из \(a^2+b^2\equiv0\) получаем \(t^2\equiv-1\), а из \(a^3+b^3\equiv0\) получаем \(t^3\equiv-1\). Деление второго сравнения на первое даёт \(t\equiv1\), но тогда \(1\equiv-1\pmod p\), противоречие. Значит, нечётных простых общих делителей нет. Если один из \(a,b\) чётен, оба выражения нечётны, и НОД равен \(1\). Если оба нечётны, оба выражения чётны, а \(a^2+b^2\equiv2\pmod4\), поэтому НОД равен \(2\).
Это сильная задача для проверки, умеет ли ученик работать с обратными элементами без явного модуля в условии.