# Thread: Equations involving Euler Totient function

1. ## Equations involving Euler Totient function

There are two little equations involving Euler's totient function which I'm not sure how to solve:

(a) Solve the equation $\displaystyle \phi(n)= 24$.

(b) Given that $\displaystyle n=3312913$ is a product of two primes and that $\displaystyle \phi(n)=3308580$, find the Prime factorisation of $\displaystyle n$ without using a factorisation algorithm.

Attempt:
For (a) I know that if $\displaystyle n=p^k$ then the totient function is given by $\displaystyle \phi(n)=p^k -p^{k-1}$. And if n has prime factorization $\displaystyle n=p_1^{\alpha_1}...p_r^{\alpha_r}$, then it is given by:

$\displaystyle \phi(n)=n \left(1- \frac{1}{p_1} \right)... \left(1- \frac{1}{p_r} \right)$

So in this case we have

$\displaystyle 24 =3.2^3=\phi(n)= n \left(1- \frac{1}{p_1} \right)... \left(1- \frac{1}{p_r} \right)$

So, how should I work backward to find n?

For (b), since $\displaystyle n=pq$ where p & q (the question doesn't say if they are distinct) are primes we'll have:

$\displaystyle \phi(3312913)=3312913 \left(1- \frac{1}{p} \right) \left(1- \frac{1}{q} \right)$

Now, how can I tell what p and q are without factorizing n?

Any guidance is greatly appreciated.

2. b)

Indicating with p and q the two prime factors of $\displaystyle 3312913$ we have that...

$\displaystyle \varphi(p\ q)= \varphi(p)\ \varphi (q) = (p-1)\ (q-1) = p\ q - p - q +1 = 3308580$ (1)

... and that leads us to write the 'twin equations'...

$\displaystyle p\ q= 3312913$

$\displaystyle p+q= 4334$ (2)

... that are equivalent to second degree equation...

$\displaystyle p^{2} - 4334\ p + 3312913 =0$ (3)

... the solutions of which are $\displaystyle p=991$ and $\displaystyle q= 3343$...

Kind regards

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

3. a)

You can use the 'product formula'...

$\displaystyle \displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... that can be wtitten as...

$\displaystyle \displaystyle n= \varphi(n) \ \prod_{p|n} \frac{p}{p-1}$ (2)

In out case is $\displaystyle \varphi(n)= 24$ and from (2) You derive that the possible primes deviding n are 2,3,5,7 and 13. In detail...

$\displaystyle \displaystyle p=2,3 \implies n= 24\ 2\ \frac{3}{2} = 72$

$\displaystyle \displaystyle p=2,3,5 \implies n= 24\ 2\ \frac{3}{2}\ \frac{5}{4} = 90$

$\displaystyle \displaystyle p=2,3,7 \implies n= 24\ 2\ \frac{3}{2}\ \frac{7}{6} = 84$

$\displaystyle \displaystyle p=2,3,13 \implies n= 24\ 2\ \frac{3}{2}\ \frac{13}{12} = 78$

$\displaystyle \displaystyle p=2,5,7 \implies n= 24\ 2\ \frac{5}{4}\ \frac{7}{6} = 70$

$\displaystyle \displaystyle p=2,7 \implies n= 24\ 2\ \frac{7}{6} = 56$

$\displaystyle \displaystyle p=2,13 \implies n= 24\ 2\ \frac{13}{12} = 52$

$\displaystyle \displaystyle p=3,5 \implies n= 24\ \frac{3}{2}\ \frac{5}{4} = 45$

$\displaystyle \displaystyle p=3,7 \implies n= 24\ \frac{3}{2}\ \frac{7}{6} = 42$

$\displaystyle \displaystyle p=3,13 \implies n= 24\ 2\ \frac{3}{2}\ \frac{13}{12} = 39$

$\displaystyle \displaystyle p=5,7 \implies n= 24\ \frac{5}{4}\ \frac{7}{6} = 35$

Kind regards

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