Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How it will be solved

  1. Sep 18, 2008 #1
    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
    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).
    For each n in the input print a line containing the number of irreducible basic fractions with
    denominator n
    Sample Input
    Sample Output
  2. jcsd
  3. Sep 18, 2008 #2


    User Avatar
    Science Advisor

    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"?
  4. Sep 19, 2008 #3
    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..
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook