Can you find it?

Note that $2013 = 3 \cdot 11 \cdot 61$ .

This means that $13^n \equiv 1 \pmod{2013}$ is true if and only if all of the following are true:

• (a) $13^n \equiv 1 \pmod{3}$
• (b) $13^n \equiv 1 \pmod{11}$
• (c) $13^n \equiv 1 \pmod{61}$

Which values of $n$ satisfy (a)?

$13^n \equiv 1^n \pmod{3}$

$13^n \equiv 1 \pmod{3}$

Thus, $13^n$ always leaves a remainder of $1$ when divided by $3$ .

Which values of $n$ satisfy (b)?

Thirteen is the same as two, modulo eleven, so

$13^n \equiv 2^n \pmod{11}$

Since we're dealing with relatively small numbers here, it's faster to simply list out the powers of two modulo eleven than to resort to more clever methods. Just multiply by two and subtract eleven when necessary. Repeat. Get these numbers:

• $2^0 \equiv 1 \pmod{11}$
• $2^1 \equiv 2 \pmod{11}$
• $2^2 \equiv 4 \pmod{11}$
• $2^3 \equiv 8 \pmod{11}$
• $2^4 \equiv 5 \pmod{11}$
• $2^5 \equiv 10 \pmod{11}$
• $2^6 \equiv 9 \pmod{11}$
• $2^7 \equiv 7 \pmod{11}$
• $2^8 \equiv 3 \pmod{11}$
• $2^9 \equiv 6 \pmod{11}$
• $2^{10} \equiv 1 \pmod{11}$

We can stop since we've found a repeated residue. This means that powers of two (and thus powers of thirteen), modulo eleven, repeat in cycles of $10$ . In particular,

$13^n \equiv 1 \pmod{11} \iff n \equiv 0 \pmod{10}$

Which values of $n$ satisfy (c)?

We do the same thing as above, although this time the multiplication has a danger of being slightly more tedious.

• $13^0 \equiv 1 \pmod{61}$
• $13^1 \equiv 13 \pmod{61}$
• $13^2 \equiv 169 \equiv 108 \equiv 47 \pmod{61}$
• $13^3 \equiv 47 \cdot 13 \equiv 611 \equiv 1 \pmod{61}$

Fortunately, we're done fairly early, with a nice result:

$13^n \equiv 1 \pmod{61} \iff n \equiv 0 \pmod{3}$

We've found (necessary and sufficient) conditions on $n$ so that $13^n$ leaves a remainder of $1$ when divided by $3$ , $11$ , and $61$ , respectively. Thus, $13^n \equiv 1 \pmod{2013}$ exactly when all of these conditions are met:

$13^n \equiv 1 \pmod{2013} \iff n \equiv 0 \pmod{10}, n \equiv 0 \pmod{3}$

$13^n \equiv 1 \pmod{2013} \iff n \equiv 0 \pmod{30}$

The smallest positive integer that is divisible by both $3$ and $10$ is

$n=30$

One thing to note is Euler's Theorem won't necessarily give us the value of the smallest N . So, we shall have find out the smallest value of N manually. We know, $2013=3 \times 11 \times 61$ and $12 \mid (13^{N}-1)$ So we aren't concerned about the $3$ We know, by Fermat's theorem that $13^{60} \equiv 1\pmod {61}$ and $13^{10} \equiv 1\pmod {11}$ But, we wish to find smaller solutions. It is understandable that if it works for a smaller N , then $N \mid 60$ or $N \mid 10$ as the case may be. Luckily we get, $13^{3} \equiv 1\pmod {61}$ after the first two trials. And for, $11$ we have, $13^{N} \equiv 2^{N}\pmod {11}$ After checking for, $N=2,5,10$ we get $N=10$ So, we get our required number i.e. $N=3 \times 10 =\boxed{30}$ Thus, $\boxed{13^{30} \equiv 1\pmod{2013}}$

$2013=3\cdot 11\cdot 61$

$13\equiv1\pmod 3\implies 13^1\equiv1\pmod 3, N=1$

$13\equiv2\pmod{11}$ and $\phi(11)=11-1=10$ whose divisors are $1,2,5,10$

Now, $2^2=4\not\equiv1\pmod{11}$ and $2^5=32\not\equiv1\implies N=10$

Now, $\phi(61)=61-1=60$ whose divisors are $1,2,3,4,5,6,10,12,15,20,30,60$

$13^1=13\equiv\pmod{61},13^2=169\equiv47, 13^3\equiv47\cdot13\pmod{61}\equiv611\equiv1 implies N=3$

So, N_{min}=lcm$(1,10,3)=30$

One thing to note is Euler's Theorem won't necessarily give the smallest $n$ . So we, have to do manually. $2013=3*11*61$ and $12|13^N-1$ so we are concerned not about the three. We see by Fermat's Thm. that $13^{60}\equiv 1 \pmod {61}, 13^{10}\equiv 1\pmod {11}$ . But we wish to find smaller solutions. It is understandable that if it works for a smaller n, then $n|60$ or $n|10$ as the case may be. Luckily we get $13^3\equiv 1\pmod {61}$ after the first two trials. And for 11, $13^N\equiv 2^N\pmod {11}$ . After checking for $n=2,5,10$ , we get $n=10$ . So, our required number is $3*10=\boxed{30}$

Factorizing $2013$ we find $3*11*61$ .

After that we solve the congruence for each factor:

$13^{a} \equiv 1 \pmod{3}$

$13^{3b} \equiv 1 \pmod{61}$

$13^{10c} \equiv 1 \pmod{11}$

$\{a,b,c\} \in \mathbb{N}^{*}$

Knowing that solutions of $N$ must satisfies all the congruences of the factors, we define it by $lcm(a,3b,10c)$ .

To get the wanted solution (smallest possible integer), we assume $a = b = c = 1$ and so we obtain that $N = lcm(1,3,10) = 30$

Since 2013 = 3 * 11 * 61, we can break down 13^N \equiv 1 \pmod{2013} to : 13^N \equiv 1 \pmod{61}

13^N \equiv 1 \pmod{11}

13^N \equiv 1 \pmod{3}

Now we just the to find the least common multiple of the equations above.

For 13^N \equiv 1 \pmod{61} we try a few N's: N = 0 mod 61 = 1

N = 1 mod 61 = 13 * 1 mod 61 = 13

N = 2 mod 61 = 13 * 13 mod 61 = 47

N = 3 mod 61 = 13 * 47 mod 61 = 1

So N has to be a multiple of 3.

For 13^N \equiv 1 \pmod{11} we try a few N's:

N = 0 mod 11 = 1

N = 1 mod 11 = 2

N = 2 mod 11 = 2 * 2 mod 11 = 4

("by If a \equiv b \pmod{N}, then ka \equiv kb \pmod{N}, where k is a constant", Brilliant Blog) In this case, k = 13^1, since 13 \equiv 2 \pmod{11}, we can multiply it to the next case to find 13^2 \equiv\pmod{11}, 13^3 \equiv \pmod{11}, etc.

N = 3 mod 11 = 4 * 2 mod 11 = 8

N = 4 mod 11 = 8 * 2 mod 11 = 5

N = 5 mod 11 = 5 * 2 mod 11 = 10

N = 6 mod 11 = 10 * 2 mod 11 = 9

N = 7 mod 11 = 9 * 2 mod 11 = 7

N = 8 mod 11 = 7 * 2 mod 11 = 3

N = 9 mod 11 = 3 * 2 mod 11 = 6

N = 10 mod 11 = 6 * 2 mod 11 = 1

So N has to be a multiple of 10.

Lastly, for 13^N \equiv 1 \pmod{3}:

N = 0 mod 3 = 1

N = 1 mod 3 = 1

N = 2 mod 3 = 1

Since 13 = 1 \pmod{3}, we can keep multiplying 13 in for each succeeding case and all of them will be congruent to 1 \pmod{3}.

Therefore, our answer is the least common multiple of 3 and 10, which is 30.

First notice that $2013 = 3 \cdot 11 \cdot 61$ . By chinese remainder theorem it's enough to solve the equation one factor at a time. For $3$ it's always satisfied because $13 \equiv 1 \pmod{3}$ .

For $11$ we have to solve $13^N \equiv 2^N \equiv 1 \pmod{11}$ . Because multiplicative group of integers mod $11$ has $10$ elements only $2, 5, 10$ are possibilities. It's easy to see that only $10$ works because $2^2 \equiv 4 \not \equiv 1 \pmod{11}$ and $2^5 \equiv 32 \equiv -1 \not \equiv 1 \pmod{11}$ .

For $61$ the task is similar only much harder. In theory we'd have to check all of the divisors of $60$ . Fortunately $3$ already works $13^3 \equiv 169 \cdot 13 \equiv 47 \cdot 13 \equiv 611 \equiv 1 \pmod{61}$ and since $2$ doesn't work ( $13^2 \equiv 47 \not \equiv 1 \pmod{61}$ ), this is the answer (the rest of the divisors being obviously bigger).

Putting it together, the answer is the least common multiple of the solutions found at each factor. That is, $3 \cdot 10 = {\bf 30}$ .

Since $2013 = 3 \cdot 11 \cdot 61$ , we look at the equation in modulo $3$ , modulo $11$ and modulo $61$ . Since $13 \equiv 1\pmod 3, 13^N \equiv 1\pmod 3$ for all $N$ . Since $13 \equiv 2\pmod {11}$ , $13^N \equiv 2^N \equiv 1\pmod {11}$ for $N \equiv 0\pmod {10}$ since $2^{10} = 1023 \equiv 1 \pmod {11}$ . $13^3 = 2197 = 36 \cdot 61 + 1 \equiv 1\pmod {61}$ so taking $\gcd (1,10,3) = 30$ , $N = 30$ .

2013 = 3 11 61

13^3%61 = 1 13^anything%3 = 1 13^10%11 = 1

hence, 3*10 = 30

We first find factors of 2013, i.e. 3 X 61 X 11 Now we observe that 13^N = 1 (mod 3) for any value of N, For 13^N = 1(mod 11) to hold, N has to be at least 10. Similarly, for 13^N = 1(mod 61) is true for N=3.

Hence, minimum value of N=30.

Tools needed to solve the problem:

• Fermat's Little Theorem
• Modulo Arithmetic

$13^N\equiv1 \pmod{2013}$

can be expressed as

$13^N-1=2013k$

Since $2013=3\times11\times61$

Then $13^N-1$ can is divisible by $3,11,61$

Let $N=3k$ , we have

$13^{3k}-1=3\times11\times61\times k$

$(13^k-1)(13^{2k}+13^k+1)=3\times11\times61\times k$

By trial and error, I somehow know that $13^{2k}+13^k+1$ is divisible by $61$ and $3$

Since $11$ is a prime, by Fermat's Little Theorem we have

$13^{10}\equiv1 \pmod{11}$

Hence, $k=10$ and $N=30$

Some flaws in the solution:

1. I can't explain why $13^{2k}+13^k+1$ is divisible by $61$ and $3$ .

2. I didn't try that $N=3k$ immediately when I first saw this problem and I tried $N=4k$ instead.

3. I can't really use Chinese Remainder Theorem and Euler's Theorem in this problem. If you know how, please comment or post a solution!

Since we may need a good solution for this problem, I need more suggestion to complete this solution. Hope you all can help!

import java.io.*;

import java.math.*;

public class CanYouFindIt

{

public static void main(String args[])

{

     BigInteger b=new BigInteger("13");

     BigInteger v=new BigInteger("2013");

     BigInteger k=new BigInteger("2");

     boolean c=false;

     int i=1;

     while(c==false)

     {

        b=b.multiply(BigInteger.valueOf(13));

        k=b.mod(v);

        if(k.equals(BigInteger.ONE))

            c=true;

        i++;

     }

     System.out.println(i);

}

}

OUTPUT :: 30

Given that $2013 = 3*11*13*61$ and $13^N = 1 \left(mod \: 2013\right)$ , it must therefore be true that $13^N = 1 \left(mod \: 3\right) = 1 \left(mod \: 11\right) = 1 \left(mod \: 61\right)$

$13 = 1 \left(mod \: 3\right)$ so therefore $13^N = 1 \left(mod \: 3\right) \forall N \in \mathbb{Z}^+$

$13 = 2 \left(mod \: 11\right)$ so:

$2^2 = 4 \left(mod \: 11\right)$

$2^3 = 8 \left(mod \: 11\right)$

$2^4 = 5 \left(mod \: 11\right)$

$2^5 = 10 \left(mod \: 11\right)$

$2^6 = 9 \left(mod \: 11\right)$

$2^7 = 7 \left(mod \: 11\right)$

$2^8 = 3 \left(mod \: 11\right)$

$2^9 = 6 \left(mod \: 11\right)$

$2^{10} = 1 \left(mod \: 11\right)$

Therefore, $13^{10} = 1 \left(mod \: 11\right)$ and similarly $13^N = 1\left(mod \: 11\right) \forall N = 10n, n \in \mathbb{Z}^+$

$13 = 13 \left(mod \: 61\right)$

$13^2 = 47 \left(mod \: 61\right)$

$13^3 = 1 \left(mod \: 61\right)$

Therefore $13^3 = 1 \left(mod \: 61\right)$ and so $13^N = 1 \left(mod \: 61\right) \forall N = 3n, n\ in \mathbb{Z}^+$

We now know that $N$ is of the shape $10n$ and $3k$ . Since the $LCM \left(10, 3\right)$ is $30$ , the smallest value of $N$ such that $13^N = 1 \left(mod \: 2013\right)$ is $N=30$

$2013=3\cdot 11 \cdot 61$

$13^N$ should leave the same remainder, $1$ , when divided by $3,11,$ or $61$ .

$13^N \equiv 1^N \equiv 1 \pmod{3}$

This shows us that the prime $3$ does not influence the value of $N$ .

$13^N \equiv 2^N \equiv 1 \pmod{11}$

We need to find the multiplicative order of $2$ modulo $11$ . Fermat's theorem tells us that $N$ "can" be a multiple of $10$ . We can easily check that, 10 is the smallest solution to the above congruence.

We deduce that $N=10k$ for some positive integer $k$ .

The last congruence:

$13^{10k} \equiv 1 \pmod{61}$

By FLT a possible solution is $N=60, k=6$ , but we do not know that is the minimum or not.

We note that :

$13^{10} \equiv (-14)^5 \equiv -14 \cdot 13^2 \equiv 13 \pmod{61}$

So, $13^{10+10} \equiv 13^2 \equiv 47 \pmod{61}$ , and $13^{20+10} \equiv 47 \cdot 13 \equiv 1 \pmod{61}$

We conclude that $N=30k$ , which is minimised for $k=1$ , and thus the answer is $\boxed{30}$ .

Although this solution might disgust most of you, it's worth nothing that values of ${ 13 }^{ N }$ for successive values of $N$ can be cheaply calculated using one of the most basic properties of modular arithmetic. (Calculating them individually is expensive.)

A split-second after launch we see:

169 184 379 901 1648 1294 718 1282 562 1267 367 745 1633 1099 196 535 916 1843 1816 1465 928 1999 1831 1660 1450 733 1477 1084 1 : 30

Doing this with a calculator wouldn't take overly long.

13^n equivalent to 1 mod 2013. It means we have to find the multiple of 2013 which will give the value equivalent to ( 13^n -1).. so we got 30.

Infinite Loop; hopefully there's a solution :)

1
2
3
4
5
6
7

sid = 3
while 1:
    rem = (13**sid)%2013
    if rem==1:
        print sid
        break
    sid = sid + 1

Since $13^N = 1 (mod 2013)$

We are looking for $13^N - 1 = 0 (mod 2013)$

We know $2013 = 3 \times 11 \times 61$ aand $13^N - 1 = (13 - 1)(13^{N-1} + 13^{N-2} + .... +1)$

$= 12(13^{N-1} + 13^{N-2} + ....+1)$ . Since 12 is divisible by 3, we have managed to account for divisibility by 3.

Now let's prove divisibility by 11 and 61. We see that $13^2+ 13 + 1 = 183 = 3 \times 61$ , so we have another factor of 3 and a factor of 61. The factor of 61 cannot possibly be in 12, it has to be in $(13^{N-1} + 13^{N-2} + ....+1)$ and we need $13^2+13+1$ to be a factor of $(13^{N-1} + 13^{N-2} + ....+1)$ so for this to be possible, $(N-1)+1$ has to be divisible by $2+1$ or rather $N$ has to be divisible by $3$ .

We are now left with divisibility by 11. We see that the factor of 11 cannot be in 12, so it HAS to be in $(13^{N-1} + 13^{N-2} + ....+1)$ as well. Now $13^{N-1} + 13^{N-2} + ....+1 = 2^{N-1} + 2^{N-2} + ....+1 (mod 11)$

$= 2^N-1 (mod 11)$ . We see that the smallest possible value of N is 10 as we have $2^{10}-1 = (2^5 -1)(2^5+1) = 33(2^5 - 1)$ which is clearly divisible by 11 since 33 is divisible by 11. Hence for $13^9 + 13^8 + ...+1$ to be a factor of $(13^{N-1} + 13^{N-2} + ....+1)$ , $n$ has to be divisbile by $10$ too.

We have $3 \times 10 = \boxed{30}$ as our smallest possible value.