mathschallenge.net logo

Geometric Division

Problem

A positive integer, $n$, is divided by $d$ and the quotient and remainder are $q$ and $r$ respectively. In addition $d$, $q$, and $r$ are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.

For example, 58 divided by 6 has quotient 9 and remainder 4. It can also be seen that 4, 6, 9 are consecutive terms in a geometric sequence (common ratio 3/2).

Prove that $n$ cannot be prime.


Solution

We are solving $n = dq + r$ and clearly the remainder must be less than the divisor; that is, $r \lt d$.

If $r \gt q$, then the terms will be ordered, $q \lt r \lt d$.

Let $r = qx$ and $d = qx^2$, where $x$ is the common ratio.

$\therefore n = dq + r = q^2 x^2 + r = (qx)^2 + r = r^2 + r = r(r + 1)$

However, $r(r + 1)$ can only be prime if $r = 1$, but as $r \gt q$ it follows that $q$ would be non-integer or zero.

Hence $q \gt r$, and without loss of generality we shall suppose that $r \lt q \lt d$.

Let $q = rx$ and $d = rx^2$.

$\therefore n = dq + r = r^2 x^3 + r = r(rx^3 + 1)$

If $r = 1$ then $n = x^3 + 1$. Therefore $x^3$ must be integer, and as $x$ is the common ratio of a geometric progression $x \gt 1$.

But $x^3 + 1 = (x + 1)(x^2 - x + 1) = (x + 1)(x(x - 1) + 1)$, and as $x \ge 2$, it follows that $x(x - 1) + 1 \ge 3$ (using $x = 2$ to obtain the minimum value). Hence $p$ would be the product of two numbers greater than two and could not be prime.

So let us consider the case where $r \gt 1$.

If $x$ is integer then $p = r(rx^3 + 1)$ will be the product of two numbers greater than one and cannot be prime.

Next, consider $x$ being non-integer; let $x = \dfrac{a}{b}$ where $GCD(a, b) = 1$.

$\therefore n = r(rx^3 + 1) = r \left (r \dfrac{a^3}{b^3} + 1 \right ) = \dfrac{r}{b} \left ( r \dfrac{a^3}{b^2} + b \right )$

But $d = r x^2 = r \dfrac{a^2}{b^2}$ and as $d$ is integer it follows that $b$2 divides $r$ and we can see that $r \dfrac{a^3}{b^2} + b$ will be integer greater than one in value.

Let $\dfrac{r}{b^2} = c \implies \dfrac{r}{b} = bc$, and as $b \ge 2$, $\dfrac{r}{b} \ge 2$.

Hence $n$ would again be the product of two integers greater than one and cannot be prime.    Q. E. D.

Problem ID: 304 (12 Jan 2007)     Difficulty: 4 Star

Only Show Problem