2
$\begingroup$

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<m<60$ 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<m$$ 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.

$\endgroup$
13
  • 3
    $\begingroup$ Please edit to include your efforts. $\endgroup$
    – lulu
    Jul 3, 2021 at 15:22
  • 3
    $\begingroup$ 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/… $\endgroup$
    – Asinomás
    Jul 3, 2021 at 15:25
  • 1
    $\begingroup$ You should really spend (at least) that 10 minutes before you ask here. $\endgroup$ Jul 3, 2021 at 15:25
  • 3
    $\begingroup$ @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. $\endgroup$
    – lulu
    Jul 3, 2021 at 15:27
  • 6
    $\begingroup$ 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. $\endgroup$
    – lulu
    Jul 3, 2021 at 15:42

1 Answer 1

0
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .