For a positive integer \(n\), \(\phi(n)\) denotes the number of positive integers less than or equal to \(n\) that are relatively prime to \(n\). What is \(\phi(2^{100}) \)?

BIGChungus Jul 8, 2019

#2**+2 **

**OK, young person, here is my best "guess"!**

**Since n is 2^100, or power of 2, all ODD numbers under 2^100 are "relatively prime" to it, which means: 2^100 / 2 =2^99 numbers that are relatively prime to 2^100.**

Guest Jul 8, 2019

#4**+2 **

**For a positive integer \(n,\ \phi(n)\) denotes the number of positive integers less than or equal to \(n\) that are relatively prime to \(n\). What is \(\phi(2^{100}) \)?**

\(\phi(n)\) is Euler's totient function

Formula, value for a prime power argument:

\(\text{If $p$ is prime and $k \ge 1$, then $\\ \phi(p^k) = p^{k-1}(p-1)$ }\)

\(\begin{array}{|rcll|} \hline \mathbf{\phi(p^k)} &=& \mathbf{ p^{k-1}(p-1) } \\\\ \phi(2^{100}) &=& 2^{100-1}(2-1) \\ \mathbf{\phi(2^{100})} &=& \mathbf{2^{99}} \\ \hline \end{array}\)

heureka Jul 9, 2019