China TST 2008

[asif e elahi]

Let $n$ be a positive integer such that $n$ divides $\sum_{k=2}^{n}k^{\phi (n)}$. Let $p_{1},p_{2}.........p_{i}$ be the distinct prime divisors of $n$.prove $\sum_{j=1}^{i}\frac{1}{p_{j}}+\frac{1}{p_{1}p_{2}.........p_{i}}$ is a positive integer.

[Nirjhor]

For any prime $p$ dividing $n$ we have $\displaystyle \sum_{k=2}^n k^{\phi(n)}\equiv n-\dfrac{n}{p}-1~(\bmod~ p)$ because there are $\dfrac{n}{p}$ multiples of $p$ in $[2,n]$, thus $n-\dfrac{n}{p}-1$ integers not divisible by $p$, which are congruent to $1~(\bmod~ p)$ by Euler's theorem. Hence by hypothesis $p\mid \dfrac{n}{p}+1$. This implies a prime $p$ divides $n$ exactly once, so $n=p_1\cdots p_i$. Now we gotta prove that $n\mid 1+\displaystyle\sum_{j=1}^i a_j$ where $a_k=\dfrac{n}{p_k} ~\forall ~k$. But multiplying our proven divisibility for all primes dividing $n$ we find \[0\equiv \displaystyle \prod_{j=1}^i \left(1+a_j\right)=1+\sum_{j=1}^i \sigma_j\left(a_1,\ldots,a_i\right)\equiv 1+\sigma_1\left(a_1,\ldots,a_i\right)~(\bmod~n)\] since $n\mid a_s a_t$ for any $s\neq t$.

[Masum]

There is something relevant to this problem, if known, may be this problem can be considered trivial.
http://en.wikipedia.org/wiki/Giuga_number
http://math.stackexchange.com/questions ... uga-number