Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Prove that for every positive integer , by sorting the fractions by their denominators in lowest terms. Then count the fractions in lowest terms with and . Give that count, and the value of .
counts with . If , Euler's theorem gives
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Sort the fractions. Each with reduces to a unique with , and .
Step 2. Go back. Each such comes from exactly one , namely .
Step 3. Count. For each divisor there are choices of . The fractions are split into groups of sizes , so . Proof complete.
Step 4. The count up to 12. Fractions in in lowest terms with denominator exactly number . So the count is .
Step 5. For 36. The theorem gives . Directly: for .
Answer: fractions, and the divisor sum for is .
Log in to join the discussion.
Loading…