# UVa 10179

Jump to navigation
Jump to search

## 10179 - Irreducible Basic Fractions[edit]

## Summary[edit]

Find the number of irreducible fractions with denominator n.

## Explanation[edit]

Given a fraction m/n, for it to be reduced, GCD(m,n) must not be equal to 1. Therefore, the question is reduced to finding the number of positive integers less than n which are relatively prime to n.

What they are asking for is actually to find the value of the Euler's Phi function or totient function for n. So just apply the formula to find the Euler's Phi function and you would get the answer.

## Solutions[edit]

## Input[edit]

7 12 123456 7654321 0

## Output[edit]

6 4 41088 7251444