Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

Question

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem.

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

So far I've tried to solve the congruence equation $9a^{25} \equiv -10 \pmod {35}$. The result for (using inverses and Fermat's theorem) is $a \equiv 30 \pmod {35}$

If this is ok, what should I do next? Thanks!

Answer 1

Yes, $a\equiv 30\pmod{35}$. Since you have a proof of this, I will not write one out. Now you are nearly finished. For note also that $a$ is odd. This is because if $a$ were even, the gcd of $9a^{25}+10$ and $280$ would be even.

Since $a\equiv 30\pmod{35}$ and $a$ is even, it follows that $a\equiv 65\pmod{70}$.