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$. Wh

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

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]

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, 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????

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.^[1][2]

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

Thank you Heureka :))

I have included this thread under [advanced number theory]

in our

"Reference Material" sticky thread     

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^k   is just  .... p, 2p, 3p, 4p......p^k-1p

Then, there must be p^k-1 positive integers that are not relatively prime to p^k ......{Notice that the last integer is just p^k itself}.......So, if this is true.....the number of positive integers that are relatively  prime  to p^k must just be  p^k - p^k-1.....or.....expressed another way......

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³ * 5³  ...so........  φ(1000)  = φ(2³ * 5³)  = φ(2³) * φ(5³)......then.....applying our "formula".....we have.......

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

Now......look at φ(5³)......our  "formula"  gives us  5³(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 are relatively prime to 125  !!!

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.....!!!

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