Prove that if the integer n has k distinct odd prime factors, then (2^k) | Φ(n)?

Question

Φ(n) denotes the Euler function.

Φ(n) is the total number of positive integers not exceeding n that are relatively prime to n.

Answer 1

Directly follows from the Euler's Totient Function Formula (follow the link in Sources below to read a Wiki article on the subject): if the odd prime factors in the prime factorization of n are

p_{1}, p_{2}, . . , p_{k}, then φ(n) will contain the following factors:

p_{1} - 1, p_{2} - 1, . . , p_{k} - 1, since all p''s are odd, these differences are even and they are k at all, hence their product is divisible by 2^k.

Answer 2

why don't you check it here:

http://www.mathway.com/problem.aspx?p=al...