How to prove the number is a prime?

Question

A natural number $n$ has the property that if $d$ divides $n$ then $d+1$ divides $n+1$. Show that $n$ must be a prime.

Answer 1

Assuming $\exists$ such a $d$ which divides $n$ and $\neq 1$ or $n$.

Also, $$\text{if } d+1|n+1 \Longleftrightarrow \gcd(d+1, n+1) \neq 1$$ But, $$\gcd(d+1,n+1)=\gcd(d+1-n-1, n+1) = \gcd(d-n, n+1) = \gcd(d(1-k), dk+1)$$

Hence, $\gcd(d+1,n+1)= 1$ which is a contradiction.

So we can claim that no such $d$ exists and hence $n$ is a prime.

Hope that helped.

Answer 2

Let $n=ab$ with $a\ge b\gt0$. If $(a+1)\mid(n+1)$, then $ab+1=(a+1)r$ for some $r\gt0$, which implies $r=1+ah$ for some $h\ge0$. But this leads to

$$b=ah+h+1$$

and the assumption $a\ge b$ implies $h=0$, so that $b=1$. Thus $n$ must be prime.

Answer 3

Assume $n > 2$. If $n = 1$ or $n= 2$ the result is clear.

Let $n = pq$. Wolog $p \le q$.

Assume $q+1|n+1$. Then as $0< q+1 \le n+1$, there exist an integer $k \ge 1$ such that $k(q+1) = kq + k = n+1 = pq + 1$.

So $k = q(p - k) + 1 \ge $ so $p \ge k$.

$k(q + 1) = (q(p-k) + 1)(q+1) = q^2(p-k) + q + q(p-k) + 1 = n+1$ so

$q[q(p-k) + 1 + (p-k)] = n = pq$

$q(p-k) + (p-k) + 1 = p$

If $p > k$ then $p = q(p-k) + (p-k) + 1 > q + 2$ so $p > q$ which contradicts our assumption.

So $p \le k$ but we know $p \ge k$ so $ p = k$.

So $p = q(p-k) + (p-k) + 1 = 1$. So $p = k = 1$ and $q = n$.

Thus if $n$ has the property then the only possible factors of $n$ are $1$, $n$.