# 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

• What's your hurry? Jun 25, 2015 at 7:24
• @Gerry Myerson : such a problem has been asked in competitive exams in which we don't have much time to solve this in regular process, that's why i want to know tricky way Jun 25, 2015 at 7:32
• The fastest way is Fermat's Little Theorem. Jun 25, 2015 at 7:41
• "Use this One Simple Trick to solve the congruence! Click now to find out how!" Jun 25, 2015 at 12:49

"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$$

$$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 :)

• Great..!!! you make it very very easy.. Thanks alot :) Jun 25, 2015 at 7:47
• @Chiranjeev Good to hear! You are welcome. Jun 25, 2015 at 7:47
• $\LaTeX$ tip: Use a\equiv b\pmod{c} to get $$a\equiv b\pmod{c}$$
– Teoc
Jun 25, 2015 at 14:07
• $67$ also works. Jul 16, 2015 at 16:34
• @dREaM Indeed it does! Thank you. Jul 17, 2015 at 8:45

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.