Farooq's Website

Home | Projects | Files on fubuntu | Files on bitcoinshell

2x + 2y = k

2x + 2y = k where x, y and k are positive integers and k is a constant. The question's that for different values of k how many solution does our equation have? For any odd k there is no solution and for positive powers of 2 there is one. We want a general solution for this equation.

Solution by Susam Pal

We will take this fact for granted: Every positive integer can be uniquely expressed as the sum of distinct powers of 2. In other words, every positive integer has a unique binary representation.

Now consider the case where x = y. Let m = x = y. Then k = 2m + 2m = 2(m+1). Further, if k = 2(m+1) where m > 1, x = y = m is a solution. There cannot be a solution in which x != y because that would result in another binary representation of k apart from the existing representation of 2(m+1) which would contradict the uniqueness of the binary representation of k. Therefore there must be exactly 1 solution when k is a positive power of 2.

Now consider the case where x != y. Let x = m and y = n. Then k = 2m + 2n = 2n + 2m. Thus both (x = m, y = n) and (x = n, y = m) are solutions. There cannot be a solution in which x = y because that would lead to k = 2(x+1) which violates the uniqueness of the binary representation of k. Also, there cannot be another solution in which either x or y does not belong to {m, n} because that would too violate the uniqueness of the binary representation of k. We conclude that there must be exactly 2 solutions when k is a sum of two distinct positive powers of 2.

For any other positive integer k, no solutions are possible. We can show this by contradiction. Let k be such that it is neither a positive power of 2 nor a sum of two distinct positive powers of 2. If we assume that a solution exists for such k, then we have two positive integers x and y such that 2x + 2y = k. If x = y, it contradicts the fact that k is not a positive power of 2. If x != y, it contradicts the fact that k is a sum of two distinct positive powers of 2.

Thus, we can conclude that the equation has exactly 1 solution when k is a positive power of 2, 2 solutions when k is a sum of two distinct positive powers of 2, no solutions otherwise.

Thanks, Susam