Call a natural number $n$ good if for any natural divisor $a$ of $n$, we have that $a+1$ is also divisor of $n+1$. Find all good natural numbers. S. Berlov
Problem
Source: All Russian 2014 Grade 11 Day 2 P1
Tags: number theory, prime numbers, number theory proposed
30.04.2014 12:37
It is easy. or I have made a mistake. Anyways we show all the prime numbers $>2$ and $1$ are $\text{good}$. This is obvious that they are good. Now we show there aren't any other. Now suppose some $n$ composite is good and not a prime power. Take its smallest divisor $\tilde{p}$ Take another prime (possibly equal to $\tilde{p}$ ) $q\ge \tilde{p}$ and $q+1\mid pq+1\implies q+1\mid p-1$ but $q+1\ge p+1 >p-1$ giving our contradiction. Hence $n$ has atmost one prime dividing it. $n=p^{\alpha}\;\;,\alpha\ge 2$ hence $p^{\alpha-1}+1\mid p^{\alpha}+1\implies p^{\alpha-1}+1\mid p-1$ but we have $p^{\alpha-1}+1>p+1>p-1$ which holds for $\alpha\ge 2$ and thus we have only possibility that $n=\text{prime}$. Since $2$ is not $\text{good}$ we have our desired conclusion. EDIT: A case missed as pointed out by Sardor. Sorry for the inconvenience.
30.04.2014 14:59
$ 1 $ is also $ good $ number.
30.04.2014 15:34
Sardor wrote: $ 1 $ is also $ good $ number. That can be checked by hand.. btw let $n(>2)$ is composite say $n=ab$ with $a,b\neq 1,n$ the condition implies $a+1|ab+1\implies a+1|b-1\implies a+1\leq b-1$ Similarly obtain, $b+1\leq a-1$ adding $2\leq -2 $, absurd! So, $n$ cannot be decomposed into two factors , thus only odd prime cases left and $\cdots$!
30.04.2014 16:28
Sardor wrote: $ 1 $ is also $ good $ number. Darn I missed that case. Anyways Thanks dude I am editing it.
18.05.2014 13:34
if $n$ is not prime and not equal to 1 has a divisor $d$ which $d> \sqrt{n}$ $d+1\mid n-d\Rightarrow d+1\mid d(\frac{n}{d}+1)\Rightarrow d+1\mid \frac{n}{d}+1\Rightarrow d+1\leq \frac{n}{d}+1\Rightarrow d^{2}\leq n\Rightarrow d< \sqrt{n}$ which is not true. so the answers are $n=1$ or $n$ is prime.
22.06.2014 19:25
^ I think the above solution is supposed to say (n/d -1 ) although same conclusion follows.
01.04.2015 05:59
Es trivial que $1$ cumple. Si $n$ es bueno, entonces $1+1=2 \mid n+1$, por lo tanto $n$ es impar. Es fácil observar que cualquier primo impar es bueno. Ahora demostraremos que ningún número compuesto es bueno. En efecto, si existe algún entero positivo compuesto $n$ que es bueno, entonces tomemos su menor primo, digamos $p$, entonces existe un entero positivo $k$ tal que $n=pk$. Luego, $p+1 \mid pk+1$, es decir, $p+1 \mid pk-p=p(k-1)$, pero como $p$ y $p+1$ son coprimos, entonces $p+1 \mid k-1$, en consecuencia $p+1 \leq k-1$, o sea $k \geq p+2...(1)$. Por otro lado, también se cumple que $k+1 \mid pk+1$, entonces $k+1 \mid pk-k=k(p-1)$, pero como $k$ y $k-1$ son coprimos, se tiene que $k+1 \mid p-1$, por lo tanto, $k \leq p-2$, lo cual es un absurdo por $(!)$. Finalmente, los únicos números buenos son el $1$ y los números primos impares.
24.02.2021 21:51
18.08.2021 07:58
We claim that the only solutions to this problem are odd primes and 1. For the sake of contradiction,assume that $n$ is a solution,we will show that $n$ is a prime. By hypothesis if $a+1|n+1$,then $a+1|(n+1)-(a+1)=n-a$ Obviously since $a|n-a$ and $\gcd(a,a+1)=1$ we must have $a(a+1)|n-a$,which is absurd since $n-a \ge a(a+1) >a^2 \ge n$,a contradiction hence $n$ must be a odd prime number or 1 Btw,it's my 200th Hso post!!
18.08.2021 12:08
Replace good with pog because why not. Clearly $n$ must be odd because $2 \mid n+1$, also it is easy to check that $1$ and odd primes work. I claim that these are the only pog numbers. FTSOC assume $n=pq$ where $1<p\le q<n$ (Note that $n=pq \implies n\le q^2$). $$q\mid n \implies q \mid n-q$$$$q+1\mid n+1 \implies q+1 \mid n+1 - (q+1) = n-q$$Since $\gcd(q,q+1)=1 \implies q(q+1) \mid n-q \implies q(q+1) \le n-q \implies q^2 + 2q \le n \implies q^2 < n$ which is a contradicion.