2
$\begingroup$

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!

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ Got it! Thanks! I knew I have to use somewhere that that there were no even factors in $9a^{35}+10$'s factorization... can I ask you just what is the property that enables you to go from $a\equiv 30\pmod{35}$ to $a\equiv 65\pmod{70}$ due to this fact? $\endgroup$
    – jrs
    Jun 7, 2016 at 21:32
  • 1
    $\begingroup$ @Gio: You are welcome. In principle we use CRT, solving the system of congruences $x\equiv 30\pmod{35}$, $x\equiv 1\pmod{2}$. In practice, we have $x\equiv 30\pmod{35}$ if and only if $x\equiv 30\pmod{70}$ or $x\equiv 65\pmod{70}$. The first does not meet the oddness condition. The second does. $\endgroup$
    – André Nicolas
    Jun 7, 2016 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .