# Find all $n$ such that $x+y$ is a power of $2$ whenever $xy=n$.

Let $n$ be a positive integer. $n$ is called a golden integer if $n$ is composite, and if we write $n$ as $n=xy$, where $x$ and $y$ are positive integers, then $x+y$ is a power of two ($x+y=2^{r}$). Find all golden integers.

It is obvious by definition and the fact that $n=1\times n$ that there is an integer $a$, such that $n=2^{a}-1$. $n$ is composite, hence there are two integers, say $x$ and $y$, such that $1<x\leq y<n$ and $n=xy$. Thus we have the following system, $$x+y=2^{b}$$ $$xy=2^{a}-1$$ Consequently, $$(x+1)(y+1)=2^{b}(2^{a-b}+1)$$ $$(x-1)(y-1)=2^{b}(2^{a-b}-1)$$ Does anyone know how to continue this solution?

• I don't understand if every decomposition must lead to a power of 2 or if there must exists one such decomposition – Exodd Aug 24 '18 at 10:47
• It must hold for all decompositions. – user542970 Aug 24 '18 at 10:48
• There are various ways to show that $2^{2b-2}-2^a+1$ must be a square (eg solve for $x-y$ by squaring the first and deducting four times the second, or form a quadratic in $x$ and solve that). – Mark Bennet Aug 24 '18 at 11:12
• Either $n=15$ or $n=2^p-1$ for some prime $p$, and the prime case seems difficult. – Servaes Aug 24 '18 at 11:32
• Where did you come across this problem? – Servaes Aug 24 '18 at 13:07

If $n$ is a golden number and $n=xy$ is a decomposition with $x,y>1$, then indeed $$x+y=2^b\qquad\text{ and }\qquad xy=2^a-1,$$ for positive integers $a$ and $b$. Note that $b<a$ because $$2^b=x+y<xy=2^a-1.$$
Suppose $a$ is prime, say $a=p$. Then $x$ and $y$ divide $2^p-1$ and hence${}^1$ $x\equiv y\equiv1\pmod{p}$. Then because $b<a=p$ and $$2^b=x+y\equiv2\pmod{p},$$ we see that $b-1$ strictly divides $p-1$, so $2(b-1)\leq p-1$. But also $$2^p-1=xy=x(2^b-x)\leq 2^{2b-2},$$ which shows that $p\leq 2b-2$. This means $2b-2\leq p-1<p\leq 2b-2$, a contradiction.
Hence $a$ is composite, say $a=uv$ with $u,v>1$. Then $$n=2^a-1=(2^u-1)\sum_{k=0}^{v-1}2^{ku},$$ and because $n$ is golden we have $$(2^u-1)+\sum_{k=0}^{v-1}2^{ku}=2^c,$$ for some integer $c$. This implies $v=2$, and by symmetry also $u=2$ and so $n=15$.
1. Note that $2^m-1$ and $2^n-1$ are coprime if and only if $m$ and $n$ are coprime. So if $q$ is a prime dividing $2^p-1$ then for all $m<p$ the prime $q$ does not divide $2^m-1$. So modulo $q$ the number $2$ has order $p$, which implies that $p\mid q-1$ and so $q\equiv1\pmod{p}$. It follows that all divisors of $2^p-1$ are congruent to $1$ modulo $p$.
• wait, why $x\equiv y\equiv 1 \pmod p$? – Exodd Aug 24 '18 at 14:55