# Proving integers?

• Sep 1st 2012, 05:55 AM
siruka
Proving 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.
• Sep 3rd 2012, 05:07 AM
wauwau
Re: Proving integers?
$\varphi(2^a3^b)=2^a3^{b-1} | 2^a3^b$

$\frac{n}{\varphi(n)} = \prod_{i=1}^{i=r}\frac{p_i}{p_i-1}$
the rhs denominator is dividable by $2^r$ if n is not dividable by 2 or $2^{r-1}$ 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 $\varphi(n)|n$ the number of primes in the factorization of n can be at most 2
hence
$\frac{pq}{(p-1)(q-1)}$ must be integer

therefore $\frac{pq}{(p-1)(q-1)} \ge 2$ equivalent to

(*) $2 \ge (p-2)(q-2)$

wlog q<p

examine the two cases:

1) q=2: $\frac{pq}{(p-1)(q-1)} = \frac{2p}{p-1}$ is integer only for $p=3$

2) $q \ge 3$: then (*) becomes $2 \ge (p-2)(q-2) > p-2$ thus $p \le 4$ since p prime p = 2 or 3 wich is a contradiction to q<p