1
$\begingroup$

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.

$\endgroup$

closed as off-topic by Namaste, Chris Custer, Brian Borchers, Ethan Bolker, jgon Mar 30 '18 at 23:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Brian Borchers, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ If n is prime number, only number 1 and itself (n) can divide it. So if you want d to divide n, either d=n or d=1. $\endgroup$ – user3219492 Mar 19 '16 at 11:28
  • $\begingroup$ $d>1 $ and $d \ne n$ does not mean $d$ is fixed $\endgroup$ – user322683 Mar 19 '16 at 14:58
  • 2
    $\begingroup$ $2 \mid 14$, $3 \mid 15$, so $14$ is prime? $\endgroup$ – SiXUlm Mar 19 '16 at 17:49
  • 2
    $\begingroup$ @SiXUlm has to be true for all 2|14 and 3|15 but 7|14 but 8 not | 15. $\endgroup$ – fleablood Mar 19 '16 at 17:57
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it appears to ask for a proof of a false statement. $\endgroup$ – Chris Custer Mar 30 '18 at 19:46
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is it that $a$ is a prime? Sorry if the question has a trivial answer, but unfortunately I can't see it. $\endgroup$ – MathematicianByMistake Mar 19 '16 at 18:32
  • 3
    $\begingroup$ @MathematicianByMistake, what the argument shows is that in any factorization of $n$, the smaller factor must be $1$. That's only true if $n$ is a prime. $\endgroup$ – Barry Cipra Mar 19 '16 at 18:38
  • $\begingroup$ Why is $r=1+ah$? $\endgroup$ – TheRandomGuy Mar 20 '16 at 9:03
  • $\begingroup$ @Dhruv, rewrite $ab+1=(a+1)r$ as $r=1+a(b-r)$. $\endgroup$ – Barry Cipra Mar 20 '16 at 10:41
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if $d|n$ then $d-n|n$.-This statement is false. $3|9 \not\Rightarrow - 6|9$. @ Dhruv $\endgroup$ – user322683 Mar 19 '16 at 16:07
  • $\begingroup$ @ParthaGhosh I have updated my answer. $\endgroup$ – TheRandomGuy Mar 20 '16 at 9:10