I am given the Totient Function φ(x) = (x/2)
I must prove that x must be in the form 2^m
I must prove that x must be in the form 2^m
-
If x = p_1^m_1 p_2^m_2 ... p_n^m_n is the prime factorization of the positive integer x, so that p_1 = 2, p_2 = 3, etc. then by a famous formula φ(x) = x(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_n). We are told that φ(x) =(x/2). Comparing the latter two expressions, we conclude that 1/2 = (1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_n). Or since p_1 = 2, 1 - 1/p_1 = 1 - 1/2 =1/2, then the product (1 - 1/p_2)...(1 - 1/p_n) = 1. This can only happen only if m_2 = m_3 = ... = m_n = 0 i.e. if all other primes > 2 occur with exponent of zero in the factorization of x. Hence x = p_1^m_1 = 2^m if we let m_1 = m. //