-1

This is probably quite simple but bear in mind that I am a beginner.

As part of a larger proof, I need to show that $\frac{2^x}{3}$ can never equal an integer, for any integer $x$.

As a follow up question, is there a general method I can apply to show that other related formulae can also never equal an integer, such as $\frac{2^x - 1}{6}$, $\frac{2^x-3}{9}$ and $\frac{2^x-1}{18}$.

F Chopin
  • 149
  • does contradiction work? – p_square Aug 04 '21 at 12:28
  • 5
    Do you know the Fundamental Theorem of Arithmetic? – David K Aug 04 '21 at 12:29
  • 3
    Assume that $\frac{2^x}{3}=k$ and $k$ is an integer. It is clear that it must be positive. Then, $2^x=3k$. The left side has no prime factor $3$, but the right side has. The uniqueness of prime factorization shows that the integers cannot coincide. – Peter Aug 04 '21 at 12:29
  • To use contradiction I suppose I would assume that there exists an integer y where y = 2^x / 3. And then attempt to prove that y can't exist. The trouble is that my skills are too basic to know what the next step is from there. – F Chopin Aug 04 '21 at 12:31
  • Hint : Use Euclid's lemma : If a prime $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ must divide at least one of those integers $a$ and $b$ – Infinity_hunter Aug 04 '21 at 12:32
  • @Peter: Great, that makes sense to me. How would I attempt the more general form? – F Chopin Aug 04 '21 at 12:32
  • 1
    For the given expressions, you can apply a similar approach, but in general you will need modular arithmetic. Two of the expressions are trivial to solve : The numerator is odd (if $x$ is a positive integer) , but the denominator even. This cannot lead to an integer. Try the second with my above hint. – Peter Aug 04 '21 at 12:35

4 Answers4

0

Showing that there is a non-zero remainder when $2^x$ is divided by $3$ for all $x$ is enough. Note that $2\equiv -1 (\bmod 3)\implies 2^x\equiv \pm 1 (\bmod 3)$. Hence, $2^x$ is never divisible by $3$. So, $\frac{2^x}{3}$ is never an integer.

Is there a general method you can apply to show that other related formulae can also never equal an integer? Yes, you can use Modular arithmetic or simple divisibility arguments to solve these kinds of problems.

Oshawott
  • 3,956
0

Suppose that $\frac{2^x}{3}$ is an integer $n_0$, then $2^x = 3n_0$. Now, if $n_0$ is odd then $3n_0$ is odd so then it cannot equal $2^x$ which is even. Therefore $n_0$ must be even, say $n_0=2 n_1$ for some integer $n_1$. Thus $2^{x-1} = 3n_1$. Again, $n_1$ cannot be odd, so $n_1=2n_2$ for some $n_2$, and $2^{x-2}=3n_2$. If we repeat this process, we find that there is some integer $n_x$ such that $2^{x-x} = 3n_x$. But $2^{x-x}=1$, while $3n_x$ is either $0$ if $n_x$ is zero, or $3n_x$ is at least $3$. This is a contradiction, so no $n_0$ exists with $2^x = 3n_0$.

Slugger
  • 5,556
0

In general suppose you want to know if $\frac ab$ is an integer, where $a$ is whatever you put in the numerator of your formula and $b$ is whatever you put in the denominator. (For example, when you ask about $\frac{2^x - 1}{18},$ then $a = 2^x - 1$ and $b = 18$.)

That is, you have $a$ and $b$ from somewhere and you want to know if $\frac ab = k$ for some integer $k.$

This is the same as asking whether $a = bk$ for some integer $k.$ You can often solve this by finding a prime number that you can show divides one side but does not divide the other. Sometimes you can do a little algebra to get a new equation and then find a prime number that divides one side and not the other.

For example, for $\frac{2^x}{3}$ you want to know if it is possible that $2^x = 3k$ for some integer $k.$ But $3$ is a factor on the right side and not on the left side, so the answer is no.

As another example, for $\frac{2^x - 3}{9}$ the question is whether $2^x - 3 = 9k$ for some integer $k.$ That's the same as whether $2^x = 9k + 3$ for some integer $k.$ Again there's a factor of $3$ on the right but not on the left.

For $\frac{2^x - 1}{6}$ the question is whether $2^x - 1 = 6k$ for some integer $k.$ That's the same as whether $2^x = 6k + 1$ for some integer $k.$ Now there's a factor of $2$ on the left but not on the right.

Somewhat more generally, if you take successive powers of a number, for example $2^x$ for $x = 1, 2, 3, \ldots,$ and each time take the remainder after dividing by some other fixed number, for example $18,$ there are only a finite number of possible remainders you can have, and after some time you will see one of them occur again. Once that happens, you can be sure that the same remainder will occur again and again, interleaved with the same sequence of other remainders every time.

In this example:

$2^1$ has remainder $2$ when divided by $18.$

$2^2$ has remainder $4$ when divided by $18.$

$2^3$ has remainder $8$ when divided by $18.$

$2^4$ has remainder $16$ when divided by $18.$

$2^5$ has remainder $14$ when divided by $18.$

$2^6$ has remainder $10$ when divided by $18.$

$2^7$ has remainder $2$ when divided by $18.$

And now the remainders will repeat forever: $4, 8, 16, 14, 10, 2.$

The remainder of $2^x - 1$ in each case also can take only a finite number of values, and it ends up repeating at the same frequency as $2^x.$ So it is possible to determine within a finite number of calculations what all possible values of the remainder of $2^x - 1$ are when divided by $18,$ and confirm that none of them is zero.

David K
  • 98,388
0

(2 ^ x) / 3 = k

2 ^ x = 3k

xlog(2) = log(3k)

x = log(3k) / log(2)

x = (log(3) + log(k)) / log(2)

x = ( log(3) / log(2) ) + ( log(k) / log(2) )

First term is irrational, second term is irrational for any integer k except rational for k=2 (irrational + rational is still irrational).

Therefore because irrational + irrational = irrational, and irrational + rational = irrational, x cannot be rational for any value of k

Therefore x cannot be an integer when k is an integer.

Alex
  • 1
  • 2