Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?

Which of the following primes satisfy the congruence

$$a^{24}\equiv6a+2\pmod{13}$$

1) 41

2) 47

3) 67

4) 83

I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute. Thank you in Advance

Solution 1:

"I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute."

Ok, so perhaps you are looking at Fermat's Little Theorem, where $n$ is prime, and $a$ is not a multiple of $n$:

$$a^{n-1}\equiv1\ mod\ n$$

So in your case of

$$a^{24}\equiv6a+2\ mod\ 13$$

Therefore using Fermat's Little Theorem:

$$a^{12}\equiv1\ mod\ 13$$ Therefore $$a^{24}\equiv (a^{12})^2\ mod\ 13$$

$$a^{24}\equiv1\ mod\ 13$$

$$1\equiv6a+2\ mod\ 13$$

Now using basic algebra, you can find that $$6a \equiv-1\ mod\ 13$$which means that

$$6a \equiv 12$$

and $$a \equiv 2$$

So now you can easily see that the answer is going to be $1)\ 41$.

With practice, the answer comes very easily. Hope this helps :)

Solution 2:

By Fermat's little theorem, $a^{24} = (a^{12})^2 \equiv 1^2 = 1 \pmod{13}$ (assuming $13\nmid a$, which is the case here).Thus you're really trying to solve $1\equiv6a+2\pmod{13}$, which is much easier.