Results 1 to 3 of 3

Thread: Equations involving Euler Totient function

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    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$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Nov 5th 2010, 01:04 AM
  2. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Jul 12th 2010, 09:41 AM
  3. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Jun 3rd 2010, 05:38 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 12th 2009, 06:11 PM
  5. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 28th 2009, 07:16 PM

Search Tags


/mathhelpforum @mathhelpforum