How many Numbers from 1 to N has GCD(i,N) = g

• PREREQUISITE : Sieve , Euler Phi .

  • EXPLANATION :

    Let Us Assume Two Numbers a and m and their GCD(a,m) = g
    
    Formally , GCD(a,m) = g ...eq(1)
    
    where , 0 <= a <= m ... eq(2) , a = ga' and m = gm'
    
    now putting the value of a and m into eq(1) ,
    
    GCD(ga',gm') = g
    
    => g x GCD(a',m') = g
    
    => GCD(a',m') = 1 ...eq(3)
    
    That Means, Instead of Finding GCD(a,m) = g we can find GCD(a',m') = 1
    
    Now again if we divide the Equation 2 by g
    
    0 <= a' <= m' ...eq(4)
    
    Now as we can see , a' is always less or equal than m' and instead of finding GCD(a,m) = g we can find GCD(a',m') = 1
    
    That means, Pointing to our main Question , Instead of Finding How many Number from 1 to N has GCD(i,N) = g we need to find ,
    
    How many Numbers From 1 to N' (N' = N/g) has GCD(i,N') = 1 . In other words we need find phi(N') . So, We need to Find phi(N/g)