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

| cite | improve this answer | |
$\endgroup$
  • $\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 '16 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 '16 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.