Задача
NT-B1-M06-P020 Примитивная сумма квадратов
#20
★★★☆☆ Уровень 3 из 5
Пусть \(\gcd(x,y)=1\). Докажите, что \(x^2+y^2\) не делится на \(3\).
Если сумма делится на \(3\), используйте задачу про остатки квадратов по модулю \(3\).
Предположим, что \(3\mid x^2+y^2\). Тогда по модулю \(3\) оба квадрата должны быть \(0\), значит, \(3\mid x\) и \(3\mid y\). Это противоречит \(\gcd(x,y)=1\). Следовательно, \(x^2+y^2\) не делится на \(3\).
Важная идея: сначала перейти к примитивному решению.