NT-B2-M01-P020 Квадратичная форма и степени

Для простого делителя \(p\ne3\) используйте \(t\equiv ab^{-1}\pmod p\). Тогда \(t^2+t+1\equiv0\), значит порядок \(t\) равен \(3\).

Обозначим \(Q=a^2+ab+b^2\). Если \(3\mid n\), то \(a^3-b^3=(a-b)Q\), значит \(a^3\equiv b^3\pmod Q\), и потому \(Q\mid a^n-b^n\). В этом случае НОД равен \(Q\). Пусть теперь \(3\nmid n\). Рассмотрим простой \(p\ne3\), делящий \(Q\) и \(a^n-b^n\). Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Из \(Q\equiv0\) следует \(t^2+t+1\equiv0\), то есть \(t^3\equiv1\) и \(t\not\equiv1\). Значит, порядок \(t\) равен \(3\). Но из \(a^n\equiv b^n\) следует \(t^n\equiv1\), поэтому \(3\mid n\), противоречие. Следовательно, при \(3\nmid n\) возможен только общий простой делитель \(3\). Число \(3\) делит \(Q\) тогда и только тогда, когда \(a\equiv b\pmod3\); из взаимной простоты тогда \(a,b\) не делятся на \(3\), и \(Q\) делится на \(3\), но не на \(9\). При том же условии \(a^n-b^n\) делится на \(3\). Ответ: если \(3\mid n\), НОД равен \(Q\); если \(3\nmid n\) и \(a\equiv b\pmod3\), НОД равен \(3\); в остальных случаях НОД равен \(1\).

Это сильная завершающая задача модуля: она соединяет НОД, обратные элементы, порядок по модулю и отдельный разбор простого \(3\).