+0

# phi of 6?

0
480
7

what is Φ6?

Guest Feb 22, 2015

#6
+20549
+5

$$\\\mathbf{How\ to\ calcultate\ the\ \textit{Euler phi function} \ \phi(n):}\\  We have the prime factorization of n = p_1\cdot p_2\cdot p_3 \cdots\\ \phi(n) = n \cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2}) \cdot (1-\frac{1}{p_3}) \cdots$$

$$\\\mathbf{Example\ 1: n = 6 } \\ The prime factorization of 6 = 2 * 3 = p_1*p_2 \\ \phi(6) = 6 \cdot (1-\frac{1}{2}) \cdot (1-\frac{1}{3}) \\ \phi(6) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} \\ \phi(6) = \frac{6}{3} \\ \phi(6) = 2$$

$$\\\mathbf{Example\ 2: n = 9 } \\ The prime factorization of 9 = 3^2 = p_1^2 \\ \phi(9) = 9 \cdot (1-\frac{1}{3}) \\ \phi(9) = 9 \cdot \frac{2}{3} \\ \phi(6) = 3 \cdot 2 \\ \phi(6) = 6$$

$$\\\mathbf{Example\ 3: n = 7 } \\ The prime factorization of 7 = 7 = p_1 \qquad 7  is a prime number! \\ \phi(7) = 7 \cdot (1-\frac{1}{7}) \\ \phi(7) = 7 \cdot \frac{6}{7} \\ \phi(7) = 6$$

$$\\\mathbf{Example\ 4: n = 11 } \\ The prime factorization of 11 = 11 = p_1 \qquad 11  is a prime number! \\ \phi(11) = 11 \cdot (1-\frac{1}{11}) \\ \phi(11) = 11 \cdot \frac{10}{11} \\ \phi(11) = 10$$

$$\boxed{\text{ In general  \phi(p) = p-1 , if p is a prime number }}\\\\ \begin{array}{lr} p = 2: &\phi(2) = 1 \qquad =(2-1)\\ p = 3: &\phi(3) = 2 \qquad =(3-1)\\ p = 5: &\phi(5) = 4 \qquad =(5-1)\\ p = 7: &\phi(7) = 6 \qquad =(7-1)\\ p = 11: &\phi(11) = 10 \qquad =(11-1)\\ p = 13: &\phi(13) = 12 \qquad =(13-1)\\ \cdots & \phi(p) = p-1 \end{array}$$

The first 99 values of the Phi function are:

+0+1+2+3+4+5+6+7+8+9
0+ 112242646
10+41041268816618
20+812102282012181228
30+8301620162412361824
40+16401242202422461642
50+20322452184024362858
60+16603036324820663244
70+24702472364036602478
80+32544082246442564088
90+24724460467232964260

heureka  Feb 23, 2015
#1
+20549
+5

what is Φ6?

$$\!\ \varphi(6) = 2. \qquad 1 \text{ and } 5 \\\\ 6 = 2 \cdot 3\\ \!\ \varphi(6)}=6\cdot (1-\frac{1}{2})( 1-\frac{1}{3} )}=2$$

heureka  Feb 22, 2015
#2
+94088
0

Heureka, could you (or someone else) explain the phi function to me please?

I thought phi was an irrational number like pi.

Melody  Feb 22, 2015
#3
+20549
+5

Hello Melody,

$$\\\mathbf{De{finition:}}\\ \begin{text} L{et}  n \ge 1 be an integer. Then we de{fine} the \\ \textit{Euler phi function} \phi by\\ \phi(n)= the number of positive integers \\ less than n that are relatively prime to n \end{text}$$

$$\\\mathbf{Relatively Prime:}\\  \begin{text} Describes two numbers for which\\ the only common factor is 1. \\ In other words, relatively prime numbers have\\ a greatest common factor (gcf) of 1. \\ For example, 6 and 35 are relatively prime (gcf = 1).\\ The numers 6 and 8 are not relatively prime (gcf = 2). \end{text}$$

$$\\\mathbf{Example\ 1: n = 6 }  and n is not a prime number \\ \samll{\text{  \begin{array}{rr} {1}& gcf(6,1) = {1}\\ 2& gcf(6,2) = 2\\ 3& gcf(6,3) = 3\\ 4& gcf(6,4) = 2\\ {5}& gcf(6,5) = {1}\\ 6& gcf(6,6) = 6\\ \end{array}  }}\\ 6 \text{ has } {2} \text{ relative primes } 1 \text{ and } 5 \text { see the red color. So } \phi(6) = {2}$$

$$\\\mathbf{Example\ 2: n = 9 }  and n is not a prime number \\ \samll{\text{  \begin{array}{rr} {1}& gcf(9,1) = {1}\\ {2}& gcf(9,2) = {1}\\ 3& gcf(9,3) = 3\\ {4}& gcf(9,4) = {1}\\ {5}& gcf(9,5) = {1}\\ 6& gcf(9,6) = 3\\ {7}& gcf(9,7) = {1}\\ {8}& gcf(9,8) = {1}\\ 9& gcf(9,9) = 9\\ \end{array}  }}\\ 9 \text{ has } {6} \text{ relative primes } 1,2,4,5,7,8 \text { see the red color. So } \phi(9) = {6}$$

$$\\\mathbf{Example\ 3: n = 7 }  and n is a prime number \\ \samll{\text{  \begin{array}{rr} {1}& gcf(7,1) = {1}\\ {2}& gcf(7,2) = {1}\\ {3}& gcf(7,3) = {1}\\ {4}& gcf(7,4) = {1}\\ {5}& gcf(7,5) = {1}\\ {6}& gcf(7,6) = {1}\\ 7& gcf(7,7) = 7\\ \end{array}  }}\\ \small{ 7 \text{ has } 7-1={6} \text{ relative primes } 1 \text{ until } 6 \text { see the red color. So } \phi(7) = {6}.}\\ \text{ So } \phi \text{ of a prime number } \phi(p) = p-1$$

heureka  Feb 23, 2015
#4
+94088
0

Thank you Heureka,  that explains it beautifully

Melody  Feb 23, 2015
#5
+94088
0

I have a further question Heureka.

$$\!\ \varphi(6) = 2. \qquad 1 \text{ and } 5 \\\\ 6 = 2 \cdot 3\\ \!\ \varphi(6)}=6\cdot (1-\frac{1}{2})( 1-\frac{1}{3} )}=2$$

Now I do get why phi(6)=2

But what is it about from 6=2.3

What is the relvance of the brackets.  How can this be used on other examples?

Melody  Feb 23, 2015
#6
+20549
+5

$$\\\mathbf{How\ to\ calcultate\ the\ \textit{Euler phi function} \ \phi(n):}\\  We have the prime factorization of n = p_1\cdot p_2\cdot p_3 \cdots\\ \phi(n) = n \cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2}) \cdot (1-\frac{1}{p_3}) \cdots$$

$$\\\mathbf{Example\ 1: n = 6 } \\ The prime factorization of 6 = 2 * 3 = p_1*p_2 \\ \phi(6) = 6 \cdot (1-\frac{1}{2}) \cdot (1-\frac{1}{3}) \\ \phi(6) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} \\ \phi(6) = \frac{6}{3} \\ \phi(6) = 2$$

$$\\\mathbf{Example\ 2: n = 9 } \\ The prime factorization of 9 = 3^2 = p_1^2 \\ \phi(9) = 9 \cdot (1-\frac{1}{3}) \\ \phi(9) = 9 \cdot \frac{2}{3} \\ \phi(6) = 3 \cdot 2 \\ \phi(6) = 6$$

$$\\\mathbf{Example\ 3: n = 7 } \\ The prime factorization of 7 = 7 = p_1 \qquad 7  is a prime number! \\ \phi(7) = 7 \cdot (1-\frac{1}{7}) \\ \phi(7) = 7 \cdot \frac{6}{7} \\ \phi(7) = 6$$

$$\\\mathbf{Example\ 4: n = 11 } \\ The prime factorization of 11 = 11 = p_1 \qquad 11  is a prime number! \\ \phi(11) = 11 \cdot (1-\frac{1}{11}) \\ \phi(11) = 11 \cdot \frac{10}{11} \\ \phi(11) = 10$$

$$\boxed{\text{ In general  \phi(p) = p-1 , if p is a prime number }}\\\\ \begin{array}{lr} p = 2: &\phi(2) = 1 \qquad =(2-1)\\ p = 3: &\phi(3) = 2 \qquad =(3-1)\\ p = 5: &\phi(5) = 4 \qquad =(5-1)\\ p = 7: &\phi(7) = 6 \qquad =(7-1)\\ p = 11: &\phi(11) = 10 \qquad =(11-1)\\ p = 13: &\phi(13) = 12 \qquad =(13-1)\\ \cdots & \phi(p) = p-1 \end{array}$$

The first 99 values of the Phi function are:

+0+1+2+3+4+5+6+7+8+9
0+ 112242646
10+41041268816618
20+812102282012181228
30+8301620162412361824
40+16401242202422461642
50+20322452184024362858
60+16603036324820663244
70+24702472364036602478
80+32544082246442564088
90+24724460467232964260

heureka  Feb 23, 2015
#7
+94088
+3

Thank you Heueka, you are a gem.

Melody  Feb 23, 2015