# $x+y-1$ divide $n$.

Find all $$n>1$$ odd number s.t. for any $$x, y$$ divisors of $$n$$ with $$gcd(x,y)=1$$ we have $$x+y-1$$ divide $$n$$.

It's intuitive that $$n$$ is of the form $$p^k$$ with $$p$$ prime.

My idea:

I consider $$n=p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_k^{a_k}$$ with $$p_1.

$$k\geq 2$$

I let $$x=p_1$$ and $$y=p_2^{a_2}\cdot...\cdot p_k^{a_k}$$.

But $$p_2,...,p_k$$ don't divide $$x+y-1$$ because of minimality of $$p_1$$. So $$x+y-1$$ should be a power of $$p_1$$. But this is not necessary false and I am stuck.

• Any $n$ of the form $p^a$ is an example. The only relatively prime divisors of $n$ must be of the form $p^b,1$ for $b≤a$ and in each such case $p^b+1-1=p^b$ which is a divisor of $n$,
– lulu
Nov 14 '20 at 19:11
• If we drop the restriction that $n$ is odd, then $n$ does not need to be a prime power; $12$ also works. So you'd want to use the parity of $n$ somehow to prove that prime powers are the only examples. (Possibly $12$ is the only unusual case, though.) Nov 14 '20 at 19:14

Only prime powers can satisfy the desired hypothesis. As you rightly observed, if $$p$$ is the smallest prime factor of $$n$$, with $$p^m\mid\mid n$$, and $$n$$ is not a prime power, then with $$x=p$$ and $$y=np^{-m}$$ such that $$(x+y-1)\mid n$$, it follows that $$x+y-1= p^l$$ for some natural number $$l\le m$$; equivalently, $$n=(1-p+p^l)p^m\,.$$ Clearly, we must have that $$l\ne 1$$, thus in particular $$m\ge 2$$. We claim that we can find a different pair $$(x,y)$$ failing the desired hypothesis. This time, let $$x=p^2\,,~\,~\,~\,~\text{and}\,~\,~\,~\,~y= 1-p+p^l\,.$$ It is now not difficult to check that $$(x+y-1)\nmid n$$; indeed, a common prime factor of both $$n$$ and $$x+y-1=-p+p^2+p^l$$ must either divide $$y-1$$ and $$x$$ (which is simply $$p$$) or must divide $$y$$ and $$x-1=p^2-1=(p+1)(p-1)$$, which, because $$p$$ is odd, cannot exist because it would necessarily be smaller than $$p$$, contrary to the minimality of $$p$$. We therefore conclude that if $$(x+y-1)\nmid n$$, then $$p$$ is the only prime factor of $$x+y-1=p(-1+p+p^{l-1})$$, which is blatantly absurd!
The argument shows that if one allows for $$n$$ to be even, the last part would require that $$p=2$$ and $$l$$ to be even such that $$1+2^{l-1}$$ is only divisible by $$3$$; this by Gersonides theorem (special case of Catalan-Mihailsescu Theorem) forces $$l\in\{2,4\}$$, leading to the only potential even non-prime power cases satisfying your hypothesis as $$n\in\{2^{m+1}\cdot 3,2^{m+3}\cdot 3\cdot 5:m\ge 1\}$$. Of these, it appears $$n=12$$ is the only admissible solution.
• Why is it not possible that $x+y-1=p^l y_1$ where $y_1 > 1$ and $y_1 | y$? Thanks. Nov 14 '20 at 21:55
• @Neat Math: I presume this is with regards to the initial assumption that $x=p$ and $y=np^{-m}$. For that, it is not possible because $p$ is smallest prime factor of $n$ and as such any common prime factor of $n$ and $x+y-1$ must necessarily be $p$; hence once we require that $(x+y-1)\mid n$, then $x+y-1$ is bound to be a prime power of $p$. Nov 14 '20 at 22:09
• @NeatMath Note with $x = p^2$ and $y = 1 - p + p^{l}$, then $x + y - 1 = p(p^{l-1} + p - 1)$. With the requirement $x + y - 1 \mid n \implies p(p^{l-1} + p - 1) \mid (1 - p + p^{l})p^m$, since $\gcd(p^{l-1} + p - 1, p^m) = 1$, then $p^{l-1} + p - 1 \mid 1 - p + p^{l}$. However, then $p^{l-1} + p - 1 = 1 - p + p^{l} \implies p^{l-1}(p-1) = 2(p-1) \implies p^{l-1} = 2$, which is not possible for odd prime $p$. This means there's a $q \gt p$ where $-(p-1) + p^{l} = q(p^{l-1} + (p-1)) \implies (q-p)p^{l-1}+q(p-1)=0$, which is also not possible. Nov 14 '20 at 22:19
• @NeatMath In my comment above, the final equation should be $(q - p)p^{l-1}+(q+1)(p-1)=0$ instead. Nov 14 '20 at 22:33
• @JohnOmielan I was asking about Jack's claim in the first paragraph since i missed his assumption that $p$ is the smallest prime that divides $n$. But thanks for your time. Nov 15 '20 at 0:54