# Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$?

Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$? I guess not. For every even integer $n$, we can show that $3^n - 1$ is not divisible by $2^n - 1$ because $2^n -1$ is a multiple of $3$, but $3^n-1$ is not. Would anyone give some tips for the other case (case for $n$ odd integer)?

• @Nikunj but an odd integer can divide an even integer... May 16, 2016 at 8:39
• I have the nagging feeling that this is an duplicate.. May 16, 2016 at 8:43
• This question was asked by someone a week ago. If there is such a question somewhere, would you point out that where it is, please?
– hkju
May 16, 2016 at 9:05
• @hkju I have no idea myself, just wait for somebody to point it out. May 16, 2016 at 9:07
• @JeanMarie my bad, you're right! May 16, 2016 at 10:14

Here is a proof by contradiction. Assume there exists such $n$.

If $n$ is even, notice $2^n-1 \equiv 0 \pmod 3$. Thus, as $3^n-1$ is not dividible by $3$, $n$ is odd. $$2^n-1 \equiv 7 \pmod {12}$$So there exists such a $p$ that $$p \equiv \pm 7 \pmod {12}, 2^n-1 \equiv 0 \pmod p \Rightarrow 3^n-1 \equiv 0 \pmod p$$ So notice if $x=3^{\frac{n-1}{2}}$, $$3^{n} \equiv 3x^2 \equiv 1 \pmod {p} \Rightarrow (3x)^2 \equiv 3 \pmod {p}$$ This implies $3$ is a quadratic residue mod $p$. A contradiction, as $p \equiv \pm 7 \pmod {12}$.

• I am sorry, but it's hard for me to understand your first sentence, notwithstanding the fact that maybe, you should at first say that you are going to make a proof by contradiction. May 16, 2016 at 9:05
• Is it possible that $2^n-1$ is congruent to $-7$ modulo 12?
– hkju
May 16, 2016 at 9:07
• @hkju No..a minor misstep on my part. May 16, 2016 at 9:08
• @JeanMarie If $n$ is even, write it as $2k$. Then $2^{n} - 1 = 2^{2k} - 1 = (2^k - 1)(2^k + 1)$, a product of consecutive odds (i.e., the predecessor and successor of $2^k$) of which one must be a multiple of $3$. So $2^n - 1$ is a mult. of $3$, which means it will not divide evenly into $3^n - 1$. May 16, 2016 at 9:08
• @MXYMXY $3^n = 3^{2x+1} = 3(3^x)^2 = ...?$
– hkju
May 16, 2016 at 9:18