Factor $2^{15}-1$ into product of two smaller positive integers.

Question

Let $ab=n=2^{15}-1$. We know that $n$ is odd, so either $a$, $b$ or both are odd.

Suppose there is just one of $a$ or $b$ that is odd.

$$\begin{align} n&=(2k+1)(2q)\\ &=4kq+2q\\ &=2(2kq+q) \end{align}$$

This contradicts the fact that $n$ is odd, so both $a$ and $b$ must be odd.

$$\begin{align} n&=(2k+1)(2q+1)\\ &=4kq+2k+2q+1\\ &=2(2kq+k+q)+1\\ \frac{n-1}{2}&=2kq+k+q \end{align}$$

Solving for $k$ gives us

$$k=\frac{n-1-2q}{2+4q}$$

Now we need to get one value of $q$ such that $k$ is an integer

Trying values of $q$ starting from $0$ gives the value $q=3$ and $k=2340$, so $a=4681$ and $b=7$.

---

But I don't like the last step of just trying numbers. Is there a sistematic way to get the answer without just guessing values for $q$ or $k$?

Answer 1

HINT: $$2^{15}-1=(2^5)^3-1$$ and $$x^3-1=(x-1)(x^2+x+1)$$

Answer 2

Hint:

Just use the identities $$a^3-b^3 =(a-b)(a^2+ab+b^2) $$ $$a^5-b^5 =(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4) $$ and see what you get. Hope it helps.

Answer 3

We can do better without any calculation.

$(2^n-1)_{n\ge 1}$ is a strongly divisibility sequence, hence $\gcd(2^3-1,2^5-1)=2^{\gcd(3,5)}-1=1$. It follows that $$ 2^{15}-1=(2^3-1)(2^5-1)\frac{2^{15}-1}{(2^3-1)(2^5-1)}. $$