1

I need to know when would this equation give integer values, I think there might be an easy method I am not aware of, so I am asking here to know if such method/technique is known for finding a General solution for values of n

$$Odd = \frac{(2^n)-1}{3}$$

Omar
  • 141
  • Have you tried $n=1,2,3,4,5,6$? – kingW3 May 12 '19 at 22:27
  • I need a general solution that describes all values of n which give integer results – Omar May 12 '19 at 22:30
  • 2
    @Omar yes, but testing out with small values may give you an indication of what the answer might be (e.g. if you see a pattern). You can then try to prove why that would be true. – John Doe May 12 '19 at 22:31

2 Answers2

2

The method you are after is the usage of Modular Arithmetic.

For $\frac{2^n-1}3$ to give an integer, we need $$2^n-1\equiv0\mod3\\2^n\equiv1\mod 3$$ The inverse of $2\mod3$ is $2$, so $2^2\equiv 1\mod3$, so we can multiply of divide by $2^2$ freely. Then $$2^{n-2k}\equiv1\mod3\quad\forall k$$So you need $n=2k$, i.e. $n$ must be even.

John Doe
  • 14,545
  • for n=4, we get (16-1)/3=5 which is odd. – NoChance May 12 '19 at 22:32
  • @John Doe , thanks alot, never mind about the different sign that I edited, I am focusing on the concept , but I don't understand the last step, where did the -2k-1 come from ? and how did we end up with n=2k+1 ? – Omar May 12 '19 at 22:58
  • @Omar I think I must have misread the sign, I edited the answer to correct this. It now has $2k$, which comes from being able to freely divide by $2^2$ since $2^2\equiv1\mod3$. We keep doing this division ($k$ times) until we can't divide any more without the exponent becoming negative - i.e. it is $2^0$ or $2^1$. Since the RHS has $1=2^0$, the LHS must have the same exponent. – John Doe May 12 '19 at 23:03
0

By the binomial theorem, $2^n-1 = (3-1)^n-1 = 3a+(-1)^n$ and so $3$ divides $2^n-1$ iff $n$ is even.

lhf
  • 216,483