+0

# 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

0
1473
8
+1796

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

Jun 22, 2015

#1
+20831
+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 &=& {2}^2\cdot {3}\\\\ \varphi(12) &=& 12\cdot (1-\frac{1}{{2}})\cdot (1-\frac{1}{{3}})\\ \varphi(12) &=& 12\cdot\frac12\cdot \frac23\\ \mathbf{ \varphi(12)} &\mathbf{=}& \mathbf{4}\\ \end{array} }$$

Jun 22, 2015

#1
+20831
+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 &=& {2}^2\cdot {3}\\\\ \varphi(12) &=& 12\cdot (1-\frac{1}{{2}})\cdot (1-\frac{1}{{3}})\\ \varphi(12) &=& 12\cdot\frac12\cdot \frac23\\ \mathbf{ \varphi(12)} &\mathbf{=}& \mathbf{4}\\ \end{array} }$$

heureka Jun 22, 2015
#2
+95177
+5

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]

Jun 23, 2015
#3
+20831
+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)} &=& {1} & \text{yes}\\ 2 & \gcd{(12,2)} &=& 2\\ 3 & \gcd{(12,3)} &=& 3\\ 4 & \gcd{(12,4)} &=& 4\\ 5 & \gcd{(12,5)} &=& {1} & \text{yes}\\ 6 & \gcd{(12,6)} &=& 6\\ 7 & \gcd{(12,7)} &=& {1} & \text{yes}\\ 8 & \gcd{(12,8)} &=& 4\\ 9 & \gcd{(12,9)} &=& 3\\ 10 & \gcd{(12,10)} &=& 2\\ 11 & \gcd{(12,11)} &=& {1} & \text{yes}\\ 12 & \gcd{(12,12)} &=& 12\\ \hline &&& \text{sum} &{4}\\ \hline \end{array} }$$

Jun 26, 2015
#4
+94526
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????

Jun 26, 2015
#5
+20831
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 ≤ kn for which the greatest common divisor gcd(n, k) = 1.[1][2]

Jun 26, 2015
#6
+95177
0

Thank you Heureka :))

in our

Jun 27, 2015
#7
+94526
+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 pk   is just  .... p, 2p, 3p, 4p......pk-1p

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

pk - pk-1  =     pk ( 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  = 23 * 53  ...so........  φ(1000)  = φ(23 * 53)  = φ(23) * φ(53)......then.....applying our "formula".....we have.......

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

Now......look at φ(53)......our  "formula"  gives us  53(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.....!!!

Jun 28, 2015
edited by CPhill  Sep 7, 2015
#8
+20831
+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

Jun 29, 2015