Determine all positive integers $n$ such that for every positive devisor $ d $ of $n$, $d+1$ is devisor of $n+1$.
Problem
Source: Romanian "Stars of Mathematics" Junior 2019 P1
Tags: number theory
04.12.2019 17:44
Hint:Consider two( proper) divisors a and b of n such that n = ab If n doesn't have proper divisors,then it is a prime or 1,and then it's easy to solve the problem
08.12.2019 11:48
The only natural numbers $n$ which satisfies the implication $(1) \;\; d>0, d|n \;\;\; \Rightarrow \;\;\; d + 1 | n + 1$ are the odd primes. Proof: Assume $d<n$ is a divisor of $n$. Then $\frac{n}{d} - \frac{n+1}{d+1} = \frac{n - d}{d(d + 1)} \in \mathbb{N}$, yielding $\frac{n - d}{d(d + 1)} \geq 1$ which means $(2) \;\; n > d^2$. Let $p$ be the smallest prime divisor of $n$. By choosing ${\textstyle d = \frac{n}{p}}$ and inserting this in inequality (2) result in $(3) \;\; {\textstyle \frac{n}{p} < p}$. The fact that ${\textstyle \frac{n}{p}}$ is a divisor of $n$ and $p$ is the smallest prime divisor of $n$ combined with inequality (3) implies ${\textstyle \frac{n}{p}=1}$, i.e. $n=p$. Hence $d=1$ or $d=p$, which according to implication (1) give us $2 \, | \, p+1$ and $p+ 1 \,|\, p+1$ respectively. Hence $p$ is an odd prime. q.e.d.