3
$\begingroup$

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)?

$\endgroup$
5
  • 5
    $\begingroup$ @Nikunj but an odd integer can divide an even integer... $\endgroup$
    – Jean Marie
    May 16, 2016 at 8:39
  • $\begingroup$ I have the nagging feeling that this is an duplicate.. $\endgroup$
    – S.C.B.
    May 16, 2016 at 8:43
  • $\begingroup$ 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? $\endgroup$
    – hkju
    May 16, 2016 at 9:05
  • $\begingroup$ @hkju I have no idea myself, just wait for somebody to point it out. $\endgroup$
    – S.C.B.
    May 16, 2016 at 9:07
  • $\begingroup$ @JeanMarie my bad, you're right! $\endgroup$
    – Nikunj
    May 16, 2016 at 10:14

1 Answer 1

6
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Jean Marie
    May 16, 2016 at 9:05
  • $\begingroup$ Is it possible that $2^n-1$ is congruent to $-7$ modulo 12? $\endgroup$
    – hkju
    May 16, 2016 at 9:07
  • $\begingroup$ @hkju No..a minor misstep on my part. $\endgroup$
    – S.C.B.
    May 16, 2016 at 9:08
  • $\begingroup$ @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$. $\endgroup$ May 16, 2016 at 9:08
  • $\begingroup$ @MXYMXY $3^n = 3^{2x+1} = 3(3^x)^2 = ...?$ $\endgroup$
    – hkju
    May 16, 2016 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.