Let $a,b,c$ and $d$ be odd integers such that $0<a<b<c<d$ and $ad=bc$. Prove that if $a+d=2^{k}$ and $b+c=2^{m}$ for some integers $k$ and $m$, then $a=1$.
Problem
Source:
Tags: Divisibility Theory
22.07.2007 05:30
nicetry007 wrote: We can write $ d = 2^{k} - a$ and $ c = 2^{m} - b$. $ ad = bc \Rightarrow a(2^{k} - a) = b(2^{m} - b) \Rightarrow b^{2} - a^{2} = 2^{m}b - 2^{k}a \Rightarrow (b + a)\;(b - a) = 2^{m}b - 2^{k}a$ (*) Claim: $ m \leq k$. $ b\; < \; d,\; c\; < \; d\; \Rightarrow\; 2^{m}\; = \; b + c\; < \; 2d\; < \;2^{k + 1}\; \Rightarrow\; m\; < \; k + 1$. Using $ m \leq k$ in (*), we get $ (b + a)\;(b - a) = 2^{m}\;(b - 2^{k - m}a) \;\Rightarrow\; 2^{m}| (b + a)\;(b - a)$ Both $ b + a$ and $ b - a$ are even. $ gcd(b + a,\;b - a) = gcd(b + a - (b - a),b - a) = gcd(2a, b - a) = 2\cdot gcd(a, (b - a)/2)$. The highest power of $ 2$ that divides both $ b + a$ and $ b - a$ is $ 2$ as $ a$ is an odd integer. In other words, one of $ \{b + a, \;b - a\}$ is divisible by $ 2$ and the other is divisible by $ 2^{m - 1}$. Claim: $ b < 2^{m - 1}$ $ 2b < b + c = 2^{m}\Rightarrow b \; < \; 2^{m - 1}$. Hence, $ b - a \; < \;2^{m - 1}$ and $ 2^{m - 1}\;|\;(b + a)$. But $ b + a \; < \; b + c = 2^{m}\Rightarrow b + a = 2^{m - 1}\Rightarrow b + c + a = 2^{m - 1} + c \Rightarrow 2^{m} + a = 2^{m - 1} + c \Rightarrow c - a = 2^{m - 1}$ $ ad = bc \Rightarrow ad = (2^{m - 1} - a)c \Rightarrow a(d + c) = 2^{m - 1}c$. Suppose $ a > 1$. Since $ a$ is an odd integer $ a | c$. Let $ c = pa$. Now $ c - a = 2^{m - 1}\Rightarrow a(p - 1) = 2^{m - 1}\Rightarrow a | 2^{m - 1}$. But $ a$ is an odd integer greater than $ 1$. Hence, our assumption that $ a \; > \;1$ is wrong. $ a = 1, \;b = 2^{m - 1} - 1,\; c = 2^{m - 1} + 1$ and $ d = 2^{2(m - 1)} - 1$. mod: checked and found correct 20071102,0:51:04