Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.