$$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(12)$?$$ 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(12)$?

Mellie
Jun 22, 2015

#1**+15 **

$$\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(12)$?

\end{array}

}$$

$$\small{

\begin{array}{rcl}

\text{Prime Factorization: }$12 &=& \textcolor[rgb]{1,0,0}{2}^2\cdot \textcolor[rgb]{0,150,0}{3}$\\\\

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

\varphi(12) &=& 12\cdot\frac12\cdot \frac23\\

\mathbf{ \varphi(12)} &\mathbf{=}& \mathbf{4}$\\

\end{array}

}$$

heureka
Jun 22, 2015

#1**+15 **

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(12)$?

\end{array}

}$$

$$\small{

\begin{array}{rcl}

\text{Prime Factorization: }$12 &=& \textcolor[rgb]{1,0,0}{2}^2\cdot \textcolor[rgb]{0,150,0}{3}$\\\\

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

\varphi(12) &=& 12\cdot\frac12\cdot \frac23\\

\mathbf{ \varphi(12)} &\mathbf{=}& \mathbf{4}$\\

\end{array}

}$$

heureka
Jun 22, 2015

#2**+5 **

**I don't understand your answer Heureka.**

I think what you are just being asked is:

How many numbers less then 12 are relatively prime to 12, that is, that is the only common factor of the two numbers is 1

so the numbers will be 5,7 and 11. That is 3

So $$\phi(12)=3$$

Maybe I just don't understand the question.

[ I was supposed to include 1 as well]

Melody
Jun 23, 2015

#3**+5 **

Hallo Melody,

$$\small{\begin{array}{rcl}\mathbf{ \varphi(12)} &\mathbf{=}& \mathbf{4}$\\

\end{array}}$$,

because

$$\small{

\begin{array}{r|rcl|c}

\hline

\text{number} &\text{greatest common devisor} &&& \text{relative prime, if 1} \\

\hline

1 & \gcd{(12,1)} &=& \textcolor[rgb]{1,0,0}{1} & \text{yes}\\

2 & \gcd{(12,2)} &=& 2\\

3 & \gcd{(12,3)} &=& 3\\

4 & \gcd{(12,4)} &=& 4\\

5 & \gcd{(12,5)} &=& \textcolor[rgb]{1,0,0}{1} & \text{yes}\\

6 & \gcd{(12,6)} &=& 6\\

7 & \gcd{(12,7)} &=& \textcolor[rgb]{1,0,0}{1} & \text{yes}\\

8 & \gcd{(12,8)} &=& 4\\

9 & \gcd{(12,9)} &=& 3\\

10 & \gcd{(12,10)} &=& 2\\

11 & \gcd{(12,11)} &=& \textcolor[rgb]{1,0,0}{1} & \text{yes}\\

12 & \gcd{(12,12)} &=& 12\\

\hline

&&& \text{sum} &\textcolor[rgb]{1,0,0}{4}\\

\hline

\end{array}

}$$

heureka
Jun 26, 2015

#4**0 **

Heureka, I see what you did with that algorithm to find the relative primes to "n.' I've not seen that done before........but....it's pretty neat.......is there a proof of this????

CPhill
Jun 26, 2015

#5**0 **

Hallo CPhill,

In number theory, **Euler's totient function** (or **Euler's phi function**), denoted as φ(*n*) or ϕ(*n*), is an

arithmetic function that counts the positive integers less than or equal to *n* that are relatively prime to *n*.

(These integers are sometimes referred to as totatives of *n*.)

**Thus, if n is a positive integer, then φ(n) is the **

**number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) = 1**.

see more... https://en.wikipedia.org/wiki/Euler%27s_totient_function

heureka
Jun 26, 2015

#6**0 **

Thank you Heureka :))

I have included this thread under [advanced number theory]

in our

"Reference Material" sticky thread

Melody
Jun 27, 2015

#7**+10 **

Euler's Totient Function briefly explained.......I'm certainly no expert, but, after reading some about this, here is a "quick and dirty" explanation of "why it works".......

Let p be some prime number.......then the number of positive integers that are * not *relatively prime to p

Then, there must be p^{k-1} positive integers that are * not* relatively prime to p

p^{k} - p^{k-1} = p^{k} ( 1 - 1/p )........let's look at a simple example.....

Let's find φ(1000).........we are aking...."How many positive integers are relatively prime to 1000??"

Note that 1000 = 2^{3} * 5^{3} ...so........ φ(1000) = φ(2^{3} * 5^{3}) = φ(2^{3}) * φ(5^{3})......then.....applying our "formula".....we have.......

φ(2^{3}) = 2^{3}(1 - 1/2) = 8(1/2) = 4.........note that this is true......the number of positive integers that are relatively prime to 2^{3} = (8) are 1, 3, 5 and 7........seen another way.....p^{k} - p^{k-1} = 2^{3} - 2^{(3-1)} = 8 - 4 = 4

Now......look at φ(5^{3})......our "formula" gives us 5^{3}(1 - 1/5) = 125(4/5) = 100.....this means that there are 100 positive integers that are relatively prime to 125.....this is easy to see.......the one's that * aren't relatively prime *to 125 are.....all multiples of 5 from 1-125 = 25 of them.......that means that 100 positive integers

So.....the number of positive integers that are relatively prime to 1000 is just 4 * 100 = 400......Again, this is easy to see.......no * even* positive integers are relatively prime to 1000......this leaves a possible 500 that are......but all odd multiples of 5 aren't relatively prime to 1000, either, and there are 10 in each 100........for a total of 100 in all......so.... 500 - 100 = 400 positive integers that are relatively prime to 1000 !!!

Thanks again to Heureka for letting us in on this "trade secret"........this is a pretty neat theorem.....!!!

CPhill
Jun 28, 2015

#8**+5 **

Hallo CPhill,

here a easy proof about Euler Phi-Function: see in german: "Satz von Euler" from Prof. Christian Spannagel PH Heidelberg: https://www.youtube.com/watch?v=DU082wcr40A

heureka
Jun 29, 2015