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

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$?

• Hint: $x^3-1 = (x-1)(x^2+x+1)$
– lulu
Commented Feb 23, 2017 at 12:34
• both $a$ and $b$ must be odd Commented Feb 23, 2017 at 13:00

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

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.

• Is this pattern also true for $a^n-b^n$? Commented Feb 23, 2017 at 12:37
• @Garmekain We have $$(a^n-b^n) = (a-b)(a^{n-1} + a^{n-2}b + \cdots + ab^{n-2} + b^{n-1})$$ for all $n \in \mathbb N$.
– user371838
Commented Feb 23, 2017 at 12:38
• @Garmekain You can up vote and accept an answer if it helped you.
– user371838
Commented Feb 23, 2017 at 12:56

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)}.$$

• ... and as it turns ou that last fraction is a prime as well Commented Feb 23, 2017 at 13:32
• Ah xD I didn't check it, thanks :) Commented Feb 23, 2017 at 13:33