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

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

  • $\begingroup$ 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$, $\endgroup$
    – lulu
    Nov 14 '20 at 19:11
  • $\begingroup$ 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.) $\endgroup$ 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.

  • $\begingroup$ Why is it not possible that $x+y-1=p^l y_1$ where $y_1 > 1$ and $y_1 | y$? Thanks. $\endgroup$
    – Neat Math
    Nov 14 '20 at 21:55
  • 1
    $\begingroup$ @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$. $\endgroup$ Nov 14 '20 at 22:09
  • $\begingroup$ @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. $\endgroup$ Nov 14 '20 at 22:19
  • $\begingroup$ @NeatMath In my comment above, the final equation should be $(q - p)p^{l-1}+(q+1)(p-1)=0$ instead. $\endgroup$ Nov 14 '20 at 22:33
  • $\begingroup$ @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. $\endgroup$
    – Neat Math
    Nov 15 '20 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.