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.

Printable View

- September 1st 2012, 04:55 AMsirukaProving integers?
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.

- September 3rd 2012, 04:07 AMwauwauRe: Proving 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