Let $n$ be a positive integer. Suppose that its positive divisors can be partitioned into pairs (i.e. can be split in groups of two) in such a way that the sum of each pair is a prime number. Prove that these prime numbers are distinct and that none of these are a divisor of $n.$
Problem
Source:
Tags: number theory
shinichiman
02.05.2016 00:55
Strange one.
Let $(d_{a_1},d_{b_1}), (d_{a_2},d_{b_2}), \cdots , (d_{a_k},d_{b_k})$ be all positive divisors of $n$ and are partitioned like that. Let $d_{a_i}+d_{b_i}=p_{c_i}$ for all $1 \le i \le k$. It's obviously that $p_{c_i} \ge 3$ so one of $d_{a_i},d_{b_i}$ must be odd number, the other is even. This follows that $n$ has exactly $k$ even divisors and $k$ odd divisors. Let $n=2^rh$ then $n$ has $\tau (h)$ odd divisors, so $\tau (n)= 2 \tau (h)$ implies $r=1$.
Consider any odd prime divisor $p$ of $n$ such that $p^{l} \| n$ then there are $\tau \left( \tfrac{n}{p^{l}} \right)$ divisors that is relatively prime to $p$ and there are $l \cdot \tau \left( \tfrac{n}{p^{l}} \right)$ divisors that is divisible by $p$. It obviously that we can't have $p \mid d_{a_i},d_{b_i}$ so for each pair $(d_{a_i},d_{b_i})$, either there is only one of them is divisible by $p$ or none of them is divisible by $p$. This gives that $l \cdot \tau \left( \tfrac{n}{p^l} \right) \le \tau \left( \tfrac{n}{p^l} \right)$ implies $l=1$. Thus, we obtain $\boxed{n=2p_1p_2 \cdots p_m}$ for $m \in \mathbb{Z}^+$.
From this, we obtain that if $d_{a_i}=n$ then $d_{b_i}=1$, if $d_{a_i}=2p_1p_2 \cdots p_{m-1}$ then $d_{b_i}=p_m$ (it can't be $1$ because we know that $1$ is on pair with $n$), ... , $d_{a_i}=2 p_1 \cdots p_{m-2}$ then $d_{b_i}=p_{m-1}p_m$ (it can't be one of $p_{m-1},p_m,1$ because these numbers are already on pair with other numbers), .... We find out that all pairs $(d_{a_i},d_{b_i})$ are of the form $(k,n/k)$ where $k$ is a divisor of $n$.
Now, to prove the claim, assume contradiction, which means there exists two distinct pair $(k,n/k)$ and $(l,n/l)$ such that $k+\frac nk= l+ \frac nl=p$ implies $(l-k)(n-lk)=0$, which gives $(k,n/k)=(l,n/l)$, a contradiction. Hence, these prime numbers $p_{c_i}$ are distinct.
It is obvious that $\gcd \left( k+\frac nk, n \right)=1$ since $\gcd \left( k, \frac nk \right)=1$ (because $n=2p_1p_2 \cdots p_m$). This gives that none of the primes $p_{c_i}$ are a divisor of $n$.
We are done.