Find the smallest natural number that satisfy $13^N = 1 \pmod {2013}$

Question

Moderator Note: This is a current contest question on Brilliant.org.

Find the smallest natural number that satisfy:

$$13^N = 1 \pmod {2013}$$

---

My idea is to use the Fermat's little theorem for prime numbers. First I factorize 2013 as 3*11*61

Then i get using the theorem i get:

$$13^{61-1} = 1 \pmod{ 61}\iff 13^{60} = 1 \pmod {61}$$ $$13^{11-1} = 1 \pmod{11}\iff13^{10} = 1 \pmod{11}$$ $$13^{3-1} = 1 \pmod 3\iff 13^{2} = 1 \pmod{3}$$

But because the modulo bases are different I doesn't know how to continue. And even if they were same, the multiplication won't change the modulo base. Is there any way to achieve this?

Actually my idea is to find the smallest natural nubmer that satisfies

$$13^N = 1 \pmod{ 3\cdot 11\cdot 61}$$

Answer 1

Euler's theorem will give you a candidate positive exponent. But is that the smallest?

Answer 2

Hint: Note that $13^{60}\equiv1\pmod{3}$, $13^{60}\equiv1\pmod{11}$, and $13^{60}\equiv1\pmod{61}$ from your equivalences above.

Hint: Check factors of $60$.

Answer 3

Using Fermat's Little Theorem, $a^{p-1}\equiv1\pmod p$ where $p$ is prime and $a$ is any integer relatively prime to $p$

If modulo/Multiplicative order of $a$ is $ord_pa,$ "as a consequence of Lagrange's theorem, $ord_pa$ always divides $\phi(p)=p-1$", we need to test for those powers of $a$ which divides $p-1$

Now, $$13^1\equiv1\pmod 3\implies ord_3{(13)}=1$$ $$13\equiv2\pmod {11}\implies 11^2\equiv2^2=4,11^5\equiv2^5\equiv-1\implies ord_{11}{(13)}=10$$ $$13^2=169\equiv-14\pmod {61},13^3\equiv(-14)\cdot13\equiv1\implies ord_{61}{(13)}=3$$ So, $ord_{3\cdot11\cdot61}(13)=$lcm$(1,10,3)=30$

Related : Carmichael Function