Find the Euler totient function $\phi (n)$ of the following numbers:
(a) $2^{1000}$ (b) $3^{1000}$ (c) $5^{1000}$ (d) $7^{1000}$
(a) Since 2 is prime, we have
$ \phi(2^{1000}) = 2^{1000-1}(2-1) = 2^{999}$
There are $2^{999}$ numbers between 1 and $2^{1000}$ which are not multiples of 2. These are odd numbers.
(b) Since 3 is prime, we have
$ \phi(3^{1000}) = 3^{1000-1}(3-1) = 2 \times 3^{999}$
There are $2 \times 3^{999}$ numbers between 1 and $3^{1000}$ which are not multiples of 3.
(c) Since 5 is prime, we have
$ \phi(5^{1000}) = 5^{1000-1}(5-1) = 4 \times 5^{999}$
There are $4 \times 5^{999}$ numbers between 1 and $5^{1000}$ which are not multiples of 5.
(d) Since 7 is prime, we have
$ \phi(7^{1000}) = 7^{1000-1}(7-1) = 6 \times 7^{999}$
There are $6 \times 7^{999}$ numbers between 1 and $7^{1000}$ which are not multiples of 7.