Define as the product of all positive integers less than or equal to and relatively prime to . Compute the number of integers such that divides .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Here one may appeal to the generalized Wilson's theorem which states that the product of the units mod n is equal to − 1 if and only if there exists a primitive root mod n . If this is the case then ϕ ! ( n ) + 1 ≡ − 1 + 1 ≡ 0 m o d n as desired. Then, to find these numbers, one need only apply the criterion that there exist primitive roots mod n if and only if n = 1 , 2 , 4 , p k , 2 p k where p is an odd prime. Then for a solution, all one needs is a list of primes smaller than 50 and then to find all the numbers smaller or equal to 50 that are expressible in the form just presented.
Bonus: For fun, if someone wanted a way to compute ϕ ! ( n ) without needing to list all the integers relatively prime to n then I have proven an alternative that only needs one to list all the square-free divisors of n :
lo g ( ϕ ! ( x ) ) = lo g ( ∏ n ≤ x , g c d ( n , x ) = 1 n ) = ∑ n ≤ x , g c d ( n , x ) = 1 lo g ( n ) = ∑ d ∣ x μ ( d ) ∑ q ≤ d x lo g ( q d ) = ∑ d ∣ x μ ( d ) lo g ( ∏ q ≤ d x q d ) = ∑ d ∣ x μ ( d ) lo g ( ( d x ) ! d d x ) = ∑ d ∣ x lo g ( ( ( d x ) ! d d x ) μ ( d ) ) and therefore ϕ ! ( x ) = ∏ d ∣ x ( [ d d x ( d x ) ! ] μ ( d ) )