We consider an integer n>1 with the following property: for every positive divisor d of n we have that d+1 is a divisor ofn+1. Prove that n is a prime number.
Problem
Source: Dutch NMO 2021 p5
Tags: number theory, prime, divisor
28.12.2021 21:33
Let p be the smallest prime dividing n so that n=pk. We must have k|pk⟹k+1|pk+1⟹k+1|pk+1−pk−p=1−p⟹k+1|p−1⟹k≤p−2. However if k>1 there must be at least a prime divisor of k which is ≥p, and so k≥p>p−2≥k which is a contradiction. If instead k=1, we are done.
28.12.2021 22:00
parmenides51 wrote: We consider an integer n>1 with the following property: for every positive divisor d of n we have that d+1 is a divisor ofn+1. Prove that n is a prime number. Had you used the search function, you would have found that this problem was already used in Bay Area 2004 and the problem was already posted on this forum two years ago here, indeed by a certain guy called parmenides51.
28.12.2021 22:10
indeed, at least now we got a solution (it was posted in Bay Area forum so a search within forum HSO, might not have found that)
28.12.2021 22:49
Well, of course the problem has also been posted on HSO several times before (it is really a classic), and of course also with a solution. See e.g. here or here (Romanian Star of Mathematics 2019).
17.06.2022 17:58
Suppose not and let p be the smallest prime divisor of n=pk, where k>1. If n satisfy the problem conditions then k+1∣pk+1⟹k+1∣pk+1−p(k+1)=1−p, so k+1∣p−1. Since k+1>0 and p−1>0, we have k+1≤p−1⟹k<p. However, since n isn't prime, k>1, so k must have a prime divisor. However, this prime factor is less than p which contradicts the fact that p is the smallest prime divisor of n.