Discrete Math: compute phi(13), phi(14), etc

[ifoan]

Im trying to figure out this problem:

Compute $\displaystyle \varphi(13),\varphi(14),\varphi(15),\varphi(30),\varphi(315),\varphi(101640)$

Here is the definition of $\displaystyle \varphi$

$\displaystyle \varphi(n) := \mid\Phi_n \mid$

Here is the definition of $\displaystyle \Phi_n$

$\displaystyle \phi_n := \{r \in Z \mid gcd(r,n) = 1\}$

so far i have:
$\displaystyle \varphi(13)=12,\varphi(14)=5,\varphi(15)=8$

I'm doing this manually but it would be impossible to do 315 and 101640.

Anyone know how to do this quickly?

 

[galactus]

What is this?. Euler's phi function?.

You know if n is prime, then \(\displaystyle \L\\{\phi}(n)=n-1\)

Also:

\(\displaystyle \L\\{\phi}(n)=n{\Pi}\left(1-\frac{1}{p}\right)\)

Where p is the prime factors of n

Let's try 315:

\(\displaystyle \L\\315=3^{2}\cdot{5}\cdot{7}\)

\(\displaystyle \L\\315(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7})=144\)

There are 144 positive integers less than 315 which are coprime to it.

\(\displaystyle \L\\101640=2^{3}\cdot{3}\cdot{5}\cdot{7}\cdot{11^{2}}\)

\(\displaystyle \L\\101640(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7})(1-\frac{1}{11})=21120\)

Is this what you were looking for?.

I hope I remember it correctly.

 

[ifoan]

thank you! i was able to get 30 and 315 from there, but 101640 was too big.

Can anyone else help?

 

[galactus]

Take another look at my post. That's the way I recollect it.

 

[ifoan]

hmm, i don't know if you editted your post two times, or if i just didnt see the 101640.

I did it myself and got 21120 also.

Thank you for you help! I REALLY appreciate it.

I'm having such a difficult time in this class. I'm a CIS major and have minimal math experience. According to the professor, I should pass. I'm really struggling though. I like the way you put it. I really understand it. It's not his fault, but his notes are cryphic to me!!

Anyways, I only have about 10 more problems with this lesson, hopefully all goes well.

Thanks again!