I am an undergraduate student in Bachelors in Mathematics undergoing a course in Algebraic Number Theory. I am stuck on the following problem:
Let $n\in \mathbb N$. Let $d_1<d_2<\dotso<d_w$ be the set of proper positive divisors of $n$.
Is it true that if $n\notin\{p^2,pq\}$, then for $i\neq j$ we must have
\begin{align}
\sum _{\substack
{k=1\\d_k\mid d_i\; \text{or}\; d_i\mid d_k\\ k\neq i}}^w \phi(d_k)\neq \sum _{\substack
{k=1\\d_k\mid d_j \; \text{or}\; d_j\mid d_k\\ k\neq j}}^w \phi(d_k)?
\end{align}
My try: I tried it with some examples and for all of them I found the above proposition true. But the problem is I can't prove this in general.
Example: Take $n=12$. Its divisors are $2,3,4,6$.
Let us take $d_1=2$ and $d_2=3$. Hence $i=1,j=2$. Also $d_1=2$ divides $4,6$.
Moreover $d_2=3$ divides only $6$.
Thus
\begin{align}
\sum _{\substack
{k=1\\d_k\mid d_i \; \text{or}\; d_i\mid d_k\\ k\neq i}}^w \phi(d_k)=\phi(4)+\phi(6)=4.
\end{align}
Again
\begin{align}
\sum _{\substack
{k=1\\d_k\mid d_i \; \text{or}\; d_i\mid d_k\\ k\neq i}}^w \phi(d_k)=\phi(6)=2,
\end{align}
hence they are not equal for $i=1,j=2$.
If we do similar examples, I find the proposition true. Can someone please help me how to prove this in general.
Best Answer
No, this is not true.
Take $n=18$. The (proper, not including $1$ or $18$) divisors are $\{2,3,6,9\}$. The only such divisor which $2$ divides or which divides $2$ (besides itself) is $6$, while the only such divisor for $9$ is $3$. So, the sum is $\phi(6)=\phi(3)=2$ for either $2$ or $9$. In general, for an odd prime $p$, the divisors $2$ and $p^2$ of $2p^2$ exhibit the same property.
There are more "exotic" examples as well, including the first odd counterexample, $297$. Here, the divisors $9$ and $11$ lead to equal sums. The general pattern here is that $297=p^3q$ with $p^2+2=q$, and it is not known that there are infinitely many pairs of primes with this pattern.