# Find smallest $n$ so that $3^n-2^n$ is a multiple of $2015$

Find the smallest $$n\in \mathbb{N}$$ such that $$3^n-2^n$$ is a multiple of $$2015$$.
Hint : $$2015 = 5 \cdot 13 \cdot 31$$

What i tried :

$$3^n\equiv2^n\pmod{2015}\begin{cases} 3^n\equiv2^n \pmod{5}\\ 3^n\equiv2^n \pmod{15}\\ 3^n\equiv2^n \pmod{31}\end{cases}$$

Using Fermat's little Theorem :
$$\mod 5 \equiv \begin{cases} 3^4 \equiv 1 \pmod{5}\\ 2^4\equiv1 \pmod{5}\\ 2^4\equiv3^4 \pmod{5} \end{cases}$$

• $$\bbox[5px,border:1px solid blue]{2^2\equiv 3^2\pmod{5}}$$

$$\mod 13\equiv\begin{cases} 3^{12} \equiv 1\pmod{13}\\ 2^{12} \equiv 1\pmod{13}\\ 2^{12}\equiv3^{12}\pmod{13}\end{cases}$$

• $$\bbox[5px,border:1px solid red]{2^4\equiv3^4\pmod{13}}$$

$$\mod 31\equiv\begin{cases} 3^{30}\equiv1\pmod{31}\\ 2^{30}\equiv1\pmod{31}\\ \boxed{3^{30} \equiv 2^{30}\pmod{31}}\end{cases}$$ since raising an exponent to an exponent works multiplicative that gives us some motivation to take the least common multiple of the boxed exponents $$(2,4$$ and $$30)$$ , the least common multiple of $$2 ,4 ,30$$ is equal to $$60$$ so we have : $$2^{60}\equiv3^{60}\pmod{2015}$$ Now we have to check to see if $$60$$ is the smallest such exponent that allows us to get at this solution.

Checking to verify $$60$$ :
suppose $$0 is the smallest such number such that $$2^m\equiv3^m\pmod{2015}$$.
division with remainder (division algorithm) we get : $$60=m \cdot q+r \quad, 0\le r Now we want to insert this version of $$60$$ into $$2^{60}\equiv3^{60}\pmod{2015}$$ we get : $$\left(2^m\right)^q\cdot 2^r\equiv\left(3^m\right)^q\cdot 3^r\pmod{2015}$$ Note that $$2$$ and $$3$$ are invertible$$\bmod{2015}$$ so that means we can cancel $$\left(2^m\right)^q$$ and $$\left(3^m\right)^q$$ , we get $$2^r \equiv 3^r\pmod{2015}$$ $$\Rightarrow r\ne 0$$ ( otherwise the minimality of $$m$$ is contraicted) $$\Rightarrow m|60$$
so we get that $$m=1,2,3,4,5,10,12,15,20,30.$$
but after checking every number we can see that none of them works which tells us that $$60$$ is in fact the smallest such exponent.

– lulu
Jul 3, 2021 at 15:22
• Also, welcome to the site. If you follow the recomendations in this link you will probably get much better results. math.meta.stackexchange.com/questions/9959/… Jul 3, 2021 at 15:25
• You should really spend (at least) that 10 minutes before you ask here. Jul 3, 2021 at 15:25
• @JitendraSingh That's kind of a poor solution to the problem...trial and error is practically as good. Starting $\pmod {31}$ at least gets you to a solution more efficiently. In any case, it makes more sense to solve it mod $5,13,31$ separately and then intersect those solutions.
– lulu
Jul 3, 2021 at 15:27
• The edits did not make it in before the question was closed. I have voted to reopen it. Your solution represents an excellent start but it is not complete. Specifically, while you have shown that $n=60$ works, you have not shown that it is minimal. To show that, I suggest examining the $\pmod {31}$ case to show that any such $n$ would have to be divisible by $30$. That would only leave you one number to check.
– lulu
Jul 3, 2021 at 15:42

You have a good start. But notice that $$2^2\equiv 3^2 \pmod{5}$$ and $$2^4 \equiv 3^4 \pmod{13}$$, for instance. So some number smaller than (and dividing) $$60$$ is the answer.

Edit: I'm wrong here. Because of what I wrote, I thought the answer might be smaller than $$60$$, but it turns out to be $$60$$. I should have said, "the answer might be smaller than $$60$$.