+0  
 
0
355
7
avatar

what is Φ6?

Guest Feb 22, 2015

Best Answer 

 #6
avatar+19480 
+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:

\varphi(n)+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
avatar+19480 
+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
avatar+92623 
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
avatar+19480 
+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}
\textcolor[rgb]{1,0,0}{1}& gcf(6,1) = \textcolor[rgb]{1,0,0}{1}\\
2& gcf(6,2) = 2\\
3& gcf(6,3) = 3\\
4& gcf(6,4) = 2\\
\textcolor[rgb]{1,0,0}{5}& gcf(6,5) = \textcolor[rgb]{1,0,0}{1}\\
6& gcf(6,6) = 6\\
\end{array}
$
}}\\
6 \text{ has } \textcolor[rgb]{0,0,1}{2} \text{ relative primes } 1 \text{ and } 5 \text { see the red color. So } \phi(6) = \textcolor[rgb]{0,0,1}{2}$$

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

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

heureka  Feb 23, 2015
 #4
avatar+92623 
0

Thank you Heureka,  that explains it beautifully 

Melody  Feb 23, 2015
 #5
avatar+92623 
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
avatar+19480 
+5
Best Answer

$$\\\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:

\varphi(n)+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
avatar+92623 
+3

Thank you Heueka, you are a gem. 

Melody  Feb 23, 2015

14 Online Users

avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.