| Puzzle 1: Find all triples of integers $(a,b,c) \in \mathbb{N}^3_{> 0}$ such that $$\text{I)}\;ab-c = 2^{e_1}, \;\; \text{II)}\;ac-b = 2^{e_2}, \;\; \text{III)}\; bc-a = 2^{e_3}$$ with $(e_1,e_2,e_3) \in \mathbb{N}^3$ |
If you have some free hours, try it for yourself. I don't think that the proof below the fold is very nice or beautiful, and also for my taste distinguished too many cases, but it is overall not that hard to follow.
Before we distinguish two cases, let me first proof two facts which concerns special cases of the variables. We assume without loss of generality, that $e_1 \leq e_2 \leq e_3$, since any solution $(a,b,c)$ can be re-ordered in such a way, that this will hold. This ordering also implies that $a \leq b \leq c$, since $ab - c \leq ac -b$ $\Leftrightarrow$ $a(b-c) \leq c - b$. If $b\neq c$, either $b-c$ or $c-b$ must be negative and the equation implies that this is $b-c$, hence $b \leq c$. The case $a \leq b$ is analogous.
FACT 1. None of the integers $a,b,c$ can be equal to $1$.
Subproof: Assume wlog that $a=1$, hence $b-c=2^{e_1}$ and $c-b=2^{e_2}$, addition yields $0 = 2^{e_1}+2^{e_2}$, which is impossible.
Q.e.d.
FACT 2. It holds $e_i \neq e_j$, for $i \neq j$ except for the two solutions $(a,b,c) = (2,2,2)$ or $(a,b,c) = (2,2,3)$.
Subproof:
1) $e_1 = e_2 = e_3$: Here we get $ab - c = ac - b = bc - a$. Adding the first two yields $(a+1)(b-c) = $, hence $b=c$. Addition of the later two yields $(c+1)(a-b) = 0$, so $a=b=c$ and $a(a-1) = 2^{e_1}$, which is only possible for $a = 2$, so $(a,b,c) = (2,2,2)$.
2) $e_1 = e_2 < e_3$: Here we only have $ab - c = ac - b$, which is equal to $(a+1)(b-c) = 0$, hence $b = c$, thus $(a-1)b = 2^{e_1}$. The case $e_1=0$ is not possible, since it $b > 1$ (due to FACT 1). So either:
2.1) $a = 2$ and $b = 2^{e_1} = c$: Thus $2^{e_1}2^{e_1} - 2 = 2^{e_2}$ which is $$2^{2e_1 - 1} - 1 = 2^{e_2-1}$$ But the only two powers of two that are close by $1$ are $2^1-2^0 = 1$. Hence $e_1 = e_2 = 1$, which leads again to $(a,b,c) = (2,2,2)$.
2.2) $a$ is odd and $b,c$ even: We have $b^2 - a = 2^{e_3}$. Reducing modulo $2$ yields $0 - 1 \equiv 0\pmod{2}$, which is false and there is no solution.
3) $e_1 < e_2 = e_3$: Here we have $ac - b = bc - a$ which is $(c+1)(a-b) = 0$, so $a = b$. and $a(c-1) = 2^{e_2} = 2^{e_3}$. So either:
3.1) The case $c = 2$ and $a=2^{e_2}$, leads again to $(a,b,c) = (2,2,2)$.
3.2) $c$ is odd and $a,b$ even: Then it is $a(c-1) = 2^{e_2}$ and $a^2 - c = 2^{e_1}$. Reducing the later mod $2$: $0 - 1 \equiv 2^{e_1}\pmod{2}$, so $e_1 = 0$. Hence $a^2 = 1 + c$. Thus $a(c-1) = a(a^2-2) = 2^{e_2}$. Since $a | 2^{e_2}$ it is $a = 2 = b$ and from $a^2 - 1 = c = 3$. Hence we get the solution $(a,b,c) = (2,2,3)$ and its permutations.
4) The case $e_1 = e_3$ is equal to $e_1=e_2=e_3$ since $e_1 \leq e_2 \leq e_3$.
Q.e.d.
For the rest we can safely assume that $e_1 < e_2 < e_3$ since all other cases are covered by FACT 2. If $0 < e_1$ it is easy to see that either $a,b,c$ are all odd or all even:
\begin{array}{| c | c | c | c | c | c | c |}
\hline
\text{mod } 2 & a & b & c & \text{I} & \text{II} & \text{III} \\
\hline
& 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & 0 & 1 & 1 & 0 & 0 \\
& 0 & 1 & 0 & 0 & 1 & 0 \\
& 0 & 1 & 1 & 1 & 1 & 1 \\
& 1 & 0 & 0 & 1 & 0 & 0 \\
& 1 & 0 & 1 & 1 & 1 & 1 \\
& 1 & 1 & 0 & 1 & 1 & 1 \\
& 1 & 1 & 1 & 0 & 0 & 0 \\
\hline
\end{array}
The table shows, that only the first or the last combination are valid combinations for $a,b,c$ modulo $2$, since only in these combinations I, II and III are valid modulo $2$.
A) If $e_1 > 0$ then $a\equiv b \equiv c \mod{2}$.
A.1) $a\equiv b \equiv c \equiv 0\pmod{2}$. So $a,b$ and $c$ are even. We start by subtracting II from the III:
\begin{align*}
bc-a - (ac-b) & = 2^{e_3}-2^{e_2} \\
c(b-a) - a + b & = 2^{e_2}(2^{e_3-e_2}-1) \\
(c+1)(b-a) & = 2^{e_2}(2^{e_3-e_2}-1) \\
\end{align*} Since $c+1$ is odd, it is $2^{e_2} | (b-a)$ and we can write $a = x + 2^{e_2}l_1$ as well as $b = x + 2^{e_2}l_2$ with integers $l_1, l_2 \geq 0$. Reducing II modulo $2^{e_2}$ yields
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2}}
\end{align*} since $(c-1)$ is odd, it is $x \equiv 0\pmod{2^{e_2}}$, so $2^{e_2} | a$ and $2^{e_2}| b$. We write $a = 2^{e_2}a'$ and $b = 2^{e_2}b'$ and use this in I: $$2^{e_2}a'2^{e_2}b' - c = 2^{e_1}$$ since $0 < e_1 < e_2$ this yields $2^{e_1} | c$. Applying this to III, with $2^{e_1}c' = c$, it is: $$2^{e_2}b'2^{e_1}c' - 2^{e_2}a' = 2^{e_3}$$ and $$b'2^{e_1}c' - a' = 2^{e_3-e_2} \geq 2^1 $$, so we found another factor of $2$ in $a'$, i.e., $2 | a'$. So we know that $2^{e_2+1} | a \Rightarrow a > 2^{e_2}$, but this leads to:
\begin{align*}
ac - b & = 2^{e_2} \\
2^{e_2}c - b & < 2^{e_2} \\
2^{e_2}b - b & < 2^{e_2} \\
(2^{e_2}- 1)b & < 2^{e_2} \\
\end{align*} Since $0 < e_1 < e_2$, $e_2$ is at least $2$, so the last inequality is only possible for $b = 1$ which contradicts FACT1.
So the "all even" case, does not lead to a solution!
A.2) $a\equiv b \equiv c \equiv 1\pmod{2}$. We start in the same way as in case A.1 and use the equation
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation} But here, we also add II and III which yields:
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} Since $c$ is odd and larger than $1$, either $c+1$ is dividable by $4$ and $(c-1)/2$ is odd or the other way round.
A.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. So $b \equiv a\pmod{2^{e_2-1}}$. We write $a = x + 2^{e_2-1}l_1$ and $b = x + 2^{e_2-1}l_2$, with $x$ odd. Then
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2-1}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2-1}}
\end{align*} hence $c-1 \equiv 0 \pmod{2^{e_2-1}}$, so $c > 1 + 2^{e_2-1} > 2^{e_2-1}$. Equivalently, $2c > 2^{e_2}$, hence $$ac - b = 2^{e_2} < 2c$$ which is $$(a-2)c < b$$, since $c\geq b$ this implies $a=2$ which contradicts that $a$ is odd.
A.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ so we get write $ac - b = 2^{e_2}$ as $$x(c+1) \equiv 0 \pmod{2^{e_2-1}}$$ with $x$ odd, hence $c+1 \geq 2^{e_2-1}$, that if $2c + 2 \geq 2^{e_2}$, so we have $$ac-b \leq 2c+2 \Leftrightarrow (a-2)c \leq b+2$$ Since $b \leq c$ it could be $c = b$ but then $a=4$, which contradicts that $a$ is odd, likewise $a=2$. So it must be $c > b$ and we get $a=3$ and $c = b + 2$. Using this in I and II:
\begin{align*}
ab - c = 3b - (b+2) & = 2b - 2 = 2^{e_1} \\
ac - b = 3(b+2) - b & = 2b + 6 = 2^{e_2} \\
\end{align*} hence $$2^{e_2} - 2^{e_1} = 8$$. But the only perfect powers of two which are $8$ apart are $2^4 - 2^3 = 2^3$, hence $2b - 2 = 8$ so $b=5$ and $b+2 = c = 7$: $(a,b,c) = (3,5,7)$
So the "all odd" case, leads to a solution. Next, we assume, that the smallest exponent $e_1$ is zero.
B) If $e_1 = 0$, and $0 < e_2 < e_3$ it is $a \equiv b \equiv 0\pmod{2}$ and $c \equiv 1 \pmod{2}$. We start again from the equations
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation}
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} We apply the same reasoning:
B.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. But from
$$ab - c = 2^{e_1} = 1$$ follows $ab = c+1$ and thus $$\frac{a}{2}b = \frac{c+1}{2}$$, but $b$ is also even, this is impossible.
B.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ and $x$ even. If $l_1 > 0$ it is $a \geq 2^{e_2-1}$ hence
$2^{e_2-1}c - b < ac - b = 2^{e_2}$ thus $$2^{e_2-1}(c-2) < b$$. Note that $e_1 = 0 \leq e_2 - 1$, hence $b < c < b+2$, hence $b+1 = c$. So $ac-a-c=1$, hence $(a-1)c = a+1$ which is equivalent to $$c = 1 + \frac{2}{a-1}$$, the only even $a$ that makes $c$ an integer is $a=2$, hence $c=3$ and thus $b=2$. The solution is equal to FACT 2 $(a,b,c) = (2,2,3)$.
So we have $l_1=0$, so $a = x$ hence $a+b = 2^{e_2-1}l_2$. If $l_2 > 1$, it is $a+b \geq 2^{e_2}$ hence $ac - b = 2^{e_2} \leq a + b$ thus $$a(c-1) \leq 2b$$ since $a$ is even $$c-1 \leq \frac{a}{2}(c-1) < b$$ which is not possible, since $c$ is odd and $b$ is even and $b \leq c$. So $l_2=1$. Hence $a+b=2^{e_2-1}$. We multiply this by $2$ which makes it equal to II:
\begin{align*}
2(a+b) & = 2\cdot 2^{e_2-1} \\
2a + 2b & = 2^{e_2} = ac - b \\
3b & = a(c-2) \\
\frac{3b}{a} - c & = -2 \\
\end{align*} This we subtract from $ab - c = 1$: $$ab - c - \frac{3b}{a} + c = 3$$ hence
\begin{align*}
b\left(a - \frac{3}{a}\right) & = 3 \\
b\left(\frac{a^2 - 3}{a}\right) & = 3 \\
\end{align*} But $a \nmid a^2 - 3$ except if $a=3$ which is not possible since $a$ is even. Hence $a | b$ and $$\frac{b}{a}(a^2-3) = 3$$ Already for $a=4$ this is impossible since $4^2 - 3 = 13 > 3$. Hence $a=2$. From this we get $\frac{b}{2}(2^2-3) = 3$ which yields $b=6$ and from $ab - c = 12-c = 11$ we get $c=11$. So the last solution is: $(a,b,c) = (2,6,11)$.
So in total there are the solutions $$(a,b,c) = \{(2,2,2),(2,2,3),(3,5,7),(2,6,11)\}$$ and their permutations.
Q.e.d.
No comments:
Post a Comment