Finding Irreducible Basic Fractions with Denominator n

[s_chaursia]

A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1. Given a
positive integer n, in this problem you are required to find out the number of irreducible
basic fractions with denominator n .
For example, the set of all basic fractions with denominator 12, before reduction to
lowest terms, is
Reduction yields
Hence there are only the following 4 irreducible basic fractions with denominator 12
Input
Each line of the input contains a positive integer n (< 1000000000) and the input
terminates with a value 0 for n (do not process this terminating value).
Output
For each n in the input print a line containing the number of irreducible basic fractions with
denominator n
Sample Input
12
123456
7654321
0
Sample Output
4
41088
7251444

 

[HallsofIvy]

This makes no sense at all. Are you asking for a computer program to do that? If not, what do you mean by "input" and "output"?

 

[mistermath]

Well, computer program are usually easier math problems :) I believe he wants a computer program, but you can challenge yourself by finding a function f(x) such that it returns the number of irreducible basic fractions with denominator x.

It looks like a fraction is simple if you can write m/n where gcd(m,n) = 1 and 0<m<n. Well if that is the case, then you're just looking for how many positive numbers are relatively prime to n that are less than n..

If so, look up the euler phi function..
http://en.wikipedia.org/wiki/Euler's_totient_function