# Proving that $n\mid A_n$ with integers that are relatively prime

Problem: Let $1 \leq b_1 < b_2 < \dots < b_{\phi(n)} < n$ be integers relatively prime with $n$, and $B_n = b_1 b_2 \cdots b_{\phi(n)}$. Consider the sum

$$1/b_1 + 1/b_2 + \dots + 1/b_{\phi(n)} = A_n/B_n$$

Prove that $n\mid A_n$. Is it true that $n^2\mid A_n$

I am thinking of rewriting the fractions on the left side to have the same denominator,$B_n$, but I am not sure if that helps me or not?

-
You may need some restrictions, as $2$ does not divide $A_2=1$. If $n>2$ is the only necessary restriction, look at $n=6$. –  Aaron Jul 28 '13 at 1:18
Sorry I am a mistake in typing the problem. Do you still think I need the restrictions? –  Username Unknown Jul 28 '13 at 1:20

In the calculations below, we assume that $n\gt 2$.
Imagine bringing the terms to a common denominator $B_n$. Then the numerator is a sum of products $b_1b_2 \cdots \hat{b_i} \cdots b_{\varphi(n)}$. Here $\hat{b_i}$ indicates that the term $b_i$ is missing. Let $c_i$ be the number in the interval $1$ to $n$ such that $c_ib_i \equiv 1\pmod{n}$. Then $$b_1b_2 \cdots \hat{b_i} \cdots b_{\varphi(n)}\equiv c_iB_n\pmod{n}.$$ It follows that $$A_n \equiv (c_1+c_2+\cdots +c_{\varphi(n)})B_n\pmod{n}.$$ Now the $c_i$ travel, in some order, through the $b_i$, so their sum is congruent to $b_1+b_2+\cdots+b_{\varphi(n)}$.
The $b_i$ come in pairs with sum $n$, so their sum is congruent to $0$ modulo $n$. This completes the proof.
As to divisibility by $n^2$, there is the easy counterexample $n=4$.
I have this for the case of n=4. $\phi(4)=2$. $1/b_1 + 1/b_2 = A_2/B_2$, which is the same as $b_2 +b_1=A_2$. How am I suppose to the contradiction from here? –  Username Unknown Jul 28 '13 at 2:33
We have in this case $b_1=1$ and $b_2=3$. Binging to the common denominator $1\cdot 3$, we find that $A_4=4$ and $B_4=3$. Thus $n$, that is, $4$, divides $A_4$. But $4^2$ certainly does not divide $A_4$. So $n=4$ is a counterexample to the assertion that $n^2$ divides $A_n$. By the way, if $n$ is a prime greater than $3$, then $n^2$ does divide $A_n$. –  André Nicolas Jul 28 '13 at 2:42