# Divisibility problem incorrect proof

here's the problem: Find all odd integers $n$ greater than $1$ such that for any relatively prime divisors $a,b$ of $n$ the number $a+b-1$ is also a divisor of $n$.

And this is my proof (which I believe is incorrect):

Clearly any prime power works, as the only relatively prime divisors are one and the number.

Now, for any integer that isn't a prime power, we can clearly find two non-consecutive relatively prime divisors $a,b$. It's clear that $a+b-1|n$. Since $(a+b-1,a) = 1$ we must clearly have $a+2b-1|n$. We proceed by induction. The base case holds, assuming that $ka+b-1|n$ we clearly have $(ka+b-1,a) = 1$ thus $a(k+1)+b-1|n$, completing our induction. This would mean that $n$ has infinitely many divisors, and so the only solutions are the prime powers.

Could you please tell me what's wrong, and if you have time to, how to correct it? Thanks!

• why should $ak$ be a divisor of $n$? – Anurag A Jun 30 '14 at 22:31
• Sorry I think that statement was false... but my reasoning behind that fact is similar: Since $(a+b-1,a) = 1$ then $2a+b-1|n$. Since $(2a+b-1,a) =1$ then $(a+2b-1,a)=1$ then $3a+b-1|n$ and so on.... – user116489 Jun 30 '14 at 22:34
• @user52733: in that case, $a$ and $b$ are not relatively prime. – Alex Wertheim Jun 30 '14 at 22:36
• @user116489 if $a=5$ and $b=11$ then $a+b-1=15$ but then $\gcd(a,a+b-1) \neq 1$. So your assumption that $\gcd(a,a+b-1) = 1$ is incorrect. – Anurag A Jun 30 '14 at 22:40
• @user116489, let $a=21$ and $b=55$. – Barry Cipra Jun 30 '14 at 22:51

Prime powers are the only odd integers $n$ such that if $a$ and $b$ are relatively prime divisors of $n$ then $a+b-1$ is also a divisor of $n$. The proof is by contradiction.

Suppose $n$ is not a prime power. Let $p$ be the smallest prime divisor of $n$ and let $q$ be the product of the other primes dividing $n$. If $p+q-1$ divides $n$, it must be a product of powers of the primes dividing $n$. But since $p$ is the smallest prime divisor of $n$, none of the other prime divisors of $n$ can divide $p-1$. Thus $p+q-1$ must be a power of $p$, say $p^r$, with $r\gt1$, and therefore $p^2$ is also a divisor of $n$.

Now consider $p^2+q-1$. We have

\begin{align} p^2+q-1&=p^2+p^r-p\qquad(\text{since } q-1=p^r-p)\\ &=p(p^{r-1}+p-1)\\ &=p(p^{r-1}+p^r-q)\quad(\text{since }p-1=p^r-q)\\ &=p(p^{r-1}(p+1)-q) \end{align}

Since $r-1\gt0$, $p$ does not divide $p^{r-1}(p+1)-q$, and since $p$ is the smallest prime divisor of $n$, none of the primes dividing $q$ can divide $p+1$. Hence $p^{r-1}(p+1)-q$ is not divisible by any prime divisor of $n$. If $p^2+q-1$ divides $n$, we would have to have $p^{r-1}(p+1)-q=1$. But that's an immediate contradiction, since we clearly have $p^2+q-1\gt p$.

• Thanks... anyway what's the motivation behind that? – user116489 Jul 1 '14 at 14:43
• @user116489, I'm not sure what you're asking? Are you wondering how I thought to separate the smallest prime from the others? – Barry Cipra Jul 1 '14 at 15:26
• Exactly... how did you think about expressing n as pq? – user116489 Jul 1 '14 at 18:24
• @user116489, I tried various approaches, including literally sleeping on it. I had a general sense that somehow using the largest and/or smallest divisors for $a$ and $b$ would lead to a contradiction. In general the largest divisor contains all the prime divisors of $n$, so I settled on seeing what I could do with the smallest divisor, which of course is the smallest prime. With that for $a$, I wanted to use something large (but relatively prime) for $b$. Ultimately the product of all the other primes suggested itself. I was a little surprised, myself, at how the proof worked out. – Barry Cipra Jul 1 '14 at 18:44