$$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})$?$$

Mellie
Jun 22, 2015

#1**+10 **

$$\small{

\begin{array}{l}

\text{For a positive integer }$n$ \text{, }

$\varphi(n)$ denotes the number of positive integers\\

\text{less than or equal to } $n$ \text{ that are relatively prime to } $n$.\text{ What is }$\varphi(2^{100})$?

\end{array}

}$$

$$\small{

\begin{array}{rcl}

\text{Prime Factorization: }$2^{100} &=& \textcolor[rgb]{1,0,0}{2}^{100}$\\\\

$\varphi( 2^{100} ) &=& 2^{100}\cdot (1-\frac{1}{\textcolor[rgb]{1,0,0}{2}})\\\\

\varphi(2^{100}) &=& 2^{100}\cdot\frac12\\\\

\mathbf{ \varphi(2^{100})} &\mathbf{=}& \mathbf{2^{99}}=633~825~300~114~114~700~748~351~602~688$\\

\end{array}

}$$

heureka
Jun 22, 2015

#1**+10 **

Best Answer

$$\small{

\begin{array}{l}

\text{For a positive integer }$n$ \text{, }

$\varphi(n)$ denotes the number of positive integers\\

\text{less than or equal to } $n$ \text{ that are relatively prime to } $n$.\text{ What is }$\varphi(2^{100})$?

\end{array}

}$$

$$\small{

\begin{array}{rcl}

\text{Prime Factorization: }$2^{100} &=& \textcolor[rgb]{1,0,0}{2}^{100}$\\\\

$\varphi( 2^{100} ) &=& 2^{100}\cdot (1-\frac{1}{\textcolor[rgb]{1,0,0}{2}})\\\\

\varphi(2^{100}) &=& 2^{100}\cdot\frac12\\\\

\mathbf{ \varphi(2^{100})} &\mathbf{=}& \mathbf{2^{99}}=633~825~300~114~114~700~748~351~602~688$\\

\end{array}

}$$

heureka
Jun 22, 2015

#3**+8 **

I think Nauseated predicted the future

Remember when my good friend Heather joined?

This is what Nauseated told Heather Feather her very first day besides welcome:

**This site is devoted to the cutting edge developments of theoretical and applied mathematics. You will find amazing ideas and concepts on here. In fact, some of the concepts are so advanced it requires a unique universe for them to function.**

**-Nauseated**

I think this is what Nauseated meant. Not only of my number thingys or Beyonce rules, but also Heureka's unique universe

i think Nauseated may be a fortune teller, a witch at witchcraft, or the oracle of something from Greece

Oh, btw, 3 is an evil number thingy

TitaniumRome
Jun 23, 2015

#4**+5 **

.

$$\Displaystyle

\Text ${Heureka's universe intersects this universe via Euler's totient function. Specifically, Euler's product formula.

The solution counts the positive integers less than or equal to (n) that are relatively prime to (n).}$$

$$\varphi(n) =n \prod \limits_{p\mid n}\; \left(1-\frac{1}{p}\right)$$

$$\text {If p is prime and k} \geq 1 \; then}$$

$$\varphi(p^k) = p^k -p^{k-1} =p^{k-1}(p-1) = p^k \left( 1 - \frac{1}{p} \right).$$

$$\text {Heureka's solution for the above question indicates the principal} \

\text {prime is 2, and half the sequential integers are coprime to 2.}\

\text {This is clearly observable. Half the numbers are odd and}\

\text {2 is coprime to all odd numbers. }\\$$

Nauseated
Jun 24, 2015

#5**0 **

Thanks Nauseated but surely no two even numbers can be coprime even if one of them is 2.

Heureka's last answer seemed to include two.

I think the question was how many co-prime numbers are there of 12 and x where x is a positive integer less than 12.

I thought these would be 5,7, and 11 BUT Heureka said that there were 4 of them :(

I assume he was including 2, but why would 2 be included?

Melody
Jun 24, 2015

#6**+5 **

You are referring to this.

Where Heureka’s solution is also correct.

The solution set for the totient always includes (1), and the highest value is equal to (n-1) when n is prime.

Nauseated
Jun 24, 2015

#8**0 **

That is correct. If you **list all** of them for this question, I will tell you if you are correct. :)

Nauseated
Jun 24, 2015

#9**0 **

Thank you Nauseated

I would but I would not want to test you checking ability. Plus, I am helping Chris look for the Roman zero so I am a bit busy at present.

Melody
Jun 24, 2015

#10**0 **

I have included this thread under [advanced number theory]

in our

"Reference Material" sticky thread

Melody
Jun 28, 2015

#11**+5 **

Nauseated’s reply is correct then? It does not have a checkmark or points for his reply.

SquareRoot
Jun 28, 2015