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...

  • 4
    $\begingroup$ Doesn't $n=1$ also have this property? $\endgroup$ – Hagen von Eitzen Apr 6 '17 at 10:23
  • $\begingroup$ i guess we have to exclude 1 here $\endgroup$ – starunique2016 Apr 6 '17 at 10:29
  • $\begingroup$ I edited the question @HagenvonEitzen $\endgroup$ – starunique2016 Apr 6 '17 at 10:30
  • $\begingroup$ ok now i edited it again to include my answer $\endgroup$ – starunique2016 Apr 6 '17 at 11:06
  • $\begingroup$ Doesn't $n=2$ disobey this property? $\endgroup$ – 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$.

  • $\begingroup$ How is that my answer worth a down vote? Would the downvoter please explain? $\endgroup$ – edm Apr 6 '17 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.