Let $x$ be the smallest positive integer that cannot be expressed in the form $\frac{2^a - 2^b}{2^c - 2^d}$, where $a$, $b$, $c$, $d$ are non-negative integers. Prove that $x$ is odd.
Problem
Source:
Tags: odd, number theory
15.11.2021 08:50
Anyone???
15.11.2021 09:21
Suppose for contradiction $x$ was even. So then $\frac{2^a-2^b}{2^c-2^d} = 2k$ has no solutions for some $k \geq 1$. By inspection we see that $\frac{2^2-2^1}{2^1-2^0} = 2$ so $x > 2$ meaning we can in fact have $k \geq 2$. But we can say $\frac{2^a-2^b}{2(2^c-2^d)} = \frac{2^a-2^b}{2^{c+1}-2^{d+1}} = \frac{2k}{2} = k$. If a solution $(a, b, c+1, d+1)$ exists here for $k$ then a solution $(a, b, c, d)$ exists for $2k$, a contradiction. So no solution exists for $k$, but this contradicts assumption that $2k$ was the minimal integer for which no solution exists. So $x$ can not be even and is thus odd. I think that's the main idea, but there's still corner cases i.e if $c+1 = 0$ or $d + 1 = 0$ which you should account for
15.11.2021 21:22
SilverDragon246 wrote: Suppose for contradiction $x$ was even. So then $\frac{2^a-2^b}{2^c-2^d} = 2k$ has no solutions for some $k \geq 1$. By inspection we see that $\frac{2^2-2^1}{2^1-2^0} = 2$ so $x > 2$ meaning we can in fact have $k \geq 2$. But we can say $\frac{2^a-2^b}{2(2^c-2^d)} = \frac{2^a-2^b}{2^{c+1}-2^{d+1}} = \frac{2k}{2} = k$. If a solution $(a, b, c+1, d+1)$ exists here for $k$ then a solution $(a, b, c, d)$ exists for $2k$, a contradiction. So no solution exists for $k$, but this contradicts assumption that $2k$ was the minimal integer for which no solution exists. So $x$ can not be even and is thus odd. I think that's the main idea, but there's still corner cases i.e if $c+1 = 0$ or $d + 1 = 0$ which you should account for In fact $c+1>0$ and $d+1>0$ since $c,d$ are nonnegative integers.
15.11.2021 21:55
Sorry I think I was unclear in original solution; the contradiction comes from assuming a solution exists $(a, b, m, n)$ for $\frac{2^a - 2^b}{2^m - 2^n} = k$. Then substitution $m = c + 1$ and $n = d + 1$ gives the desired contradiction for $2k$. However this is not valid if $m = 0$ or $n = 0$ since this would imply $c, d = -1$ meaning we have not shown a contradiction. So you need to look at this case separately but it's relatively trivial