Let n>1 be an integer. Prove that φ (n) | n if and only if n is of the form 2^a 3^b where a≥1 and b≥0 are integers.
the rhs denominator is dividable by if n is not dividable by 2 or if it is dividable by 2
the rhs numerator is dividable only by 2 if n is dividable by a power of 2
hence for the lhs to become an integer and thus the number of primes in the factorization of n can be at most 2
hence
must be integer
therefore equivalent to
(*)
wlog q<p
examine the two cases:
1) q=2: is integer only for
2) : then (*) becomes thus since p prime p = 2 or 3 wich is a contradiction to q<p