# Let $n$ be an integer such that if $d | n$ then $d + 1 | n + 1.$ Show that $n$ is a prime number

Let $n$ be an integer such that for any integer $d$, if $d | n$ then $d + 1 | n + 1$.

Show that $n$ is a prime number or equal to $1$

My workout...

Suppose $n = xy$ for some postive integers $x$ and $y. x|n$, and hence we assume without loss of generality $x + 1|n + 1.$

Then $x|xy + 1$.
However, $xy + x$ is divisible by $x$.

This implies $x − 1$ is divisible by $x$, which is an impossibility if $x$ is not equal to $1$. Therefore whenever $n$ is decomposed into two factors, one must turn out to be $1$. Hence $n$ must be a prime.

I am looking for any other method which solves this quickly and more quickly...

• Doesn't $n=1$ also have this property? – Hagen von Eitzen Apr 6 '17 at 10:23
• i guess we have to exclude 1 here – starunique2016 Apr 6 '17 at 10:29
• I edited the question @HagenvonEitzen – starunique2016 Apr 6 '17 at 10:30
• ok now i edited it again to include my answer – starunique2016 Apr 6 '17 at 11:06
• Doesn't $n=2$ disobey this property? – Harsh Kumar Apr 7 '17 at 16:44

Suppose that $d\mid n$ and $d+1\mid n+1$.
Assume that $d\ne1$ and $d\ne n$. If $d^2\lt n$, we can use $\frac{n}{d}$ in place of $d$ to get that $d\lt n$ and $d^2\ge n$. Then \begin{align} \frac{n}{d}-\frac{n+1}{d+1} &=\frac{n-d}{d(d+1)}\\[3pt] &\in(0,1) \end{align} However, if both $\frac{n}{d}$ and $\frac{n+1}{d+1}$ are integers, their difference must be an integer, and we have a contradiction. Therefore, we have $d=1$ or $d=n$.
Since for each $d$ so that $d\mid n$ we have $d+1\mid n+1$, we must have that for each $d$ so that $d\mid n$, either $d=1$ or $d=n$. Therefore, $n$ is prime.
You can prove that every composite number $n$ disobeys the statement "if $d$ divides $n$, then $d+1$ divides $n+1$. Let's say $n=ab$ for some numbers $a,b\ge2$, with $a\ge b$. Then $a$ divides $n$ but $a+1$ does not divide $n+1$. To see this, observe $n+1=(a+1)b-b+1$, so that the remainder of $n+1$ divided by $a+1$ is $1-b$. But $1-b$ is not congruent to $0$ modulo $a+1$ by observing that $1-b\lt 0$ and $1-b+(a+1)=a-b+2\gt 0$.