4
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ Doesn't $n=1$ also have this property? $\endgroup$ Commented Apr 6, 2017 at 10:23
  • $\begingroup$ i guess we have to exclude 1 here $\endgroup$
    – Pole_Star
    Commented Apr 6, 2017 at 10:29
  • $\begingroup$ I edited the question @HagenvonEitzen $\endgroup$
    – Pole_Star
    Commented Apr 6, 2017 at 10:30
  • $\begingroup$ ok now i edited it again to include my answer $\endgroup$
    – Pole_Star
    Commented Apr 6, 2017 at 11:06
  • $\begingroup$ Doesn't $n=2$ disobey this property? $\endgroup$ Commented Apr 7, 2017 at 16:44

2 Answers 2

2
$\begingroup$

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

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

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.

$\endgroup$

You must log in to answer this question.

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