0
$\begingroup$

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

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

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is this pattern also true for $a^n-b^n$? $\endgroup$
    – Garmekain
    Commented Feb 23, 2017 at 12:37
  • $\begingroup$ @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 $. $\endgroup$
    – user371838
    Commented Feb 23, 2017 at 12:38
  • $\begingroup$ @Garmekain You can up vote and accept an answer if it helped you. $\endgroup$
    – user371838
    Commented Feb 23, 2017 at 12:56
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .