# Thread: Prime factorization phi question

1. ## Prime factorization phi question

What is the 5th solution of ?

This is of the form where $\displaystyle \phi$ x = x (1 - 1/p1 ).... (1 - 1/pr)

where p1....pr refer to the prime factorization of x

2. Originally Posted by sirellwood
What is the 5th solution of ?

This is of the form where $\displaystyle \phi$ x = x (1 - 1/p1 ).... (1 - 1/pr)

where p1....pr refer to the prime factorization of x
The 'equation' can be written as...

(1)

From (1) is evident that no prime factors >3 of x exist and 2 is not prime factor so that the only solution is x=3...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

3. Thanks! yeah this is what i found last nite before i went to bed.... i found that 3 was an answer so mayb assumed it was numbers of the form 3^a prime factorization were answers or something :-s

4. iv just been informed that there are more answers than just 3.... and that there is a numerical solution to this question?

5. Originally Posted by sirellwood
iv just been informed that there are more answers than just 3.... and that there is a numerical solution to this question?
... effectively the equation...

(1)

... indicates that 3 is the only prime factor of x and that means that any is solution of (1)...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

6. ok maybe i am missing something fundamental here because thats what i assumed you had meant originally.... but if any 3^k is a solution, then take 3^2 = 9 for example....

we get p1=3 and p2=3

so (1) = (3-1)(3-1)/9 = 4/9 which does not equal 2/3 as required?

7. Originally Posted by sirellwood
ok maybe i am missing something fundamental here because thats what i assumed you had meant originally.... but if any 3^k is a solution, then take 3^2 = 9 for example....

we get p1=3 and p2=3

so (1) = (3-1)(3-1)/9 = 4/9 which does not equal 2/3 as required?
The 'Fundamental Theorem of Arithmetic'm extablishes that any n>1 can be written as...

(1)

... so that...

(2)

... depends only from the 'prime factors' and not from the 'exponents' . In Your example is...

... because 9 and 3 have both the only prime factor 3...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

8. $\displaystyle \varphi(p^k)$ is not $\displaystyle k\varphi(p) = k(p-1)$, but rather $\displaystyle (p-1)p^{k-1}$