Results 1 to 3 of 3

Math Help - Equations involving Euler Totient function

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    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 \phi(n)= 24.

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

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

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

    So in this case we have

    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 n=pq where p & q (the question doesn't say if they are distinct) are primes we'll have:

    \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
    5
    b)

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

    \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'...

    p\ q= 3312913

    p+q= 4334 (2)

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

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

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

    Kind regards

    \chi \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
    5
    a)

    You can use the 'product formula'...

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

    ... that can be wtitten as...

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

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

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

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

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

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

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

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

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

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

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

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

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

    Kind regards

    \chi \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: November 5th 2010, 01:04 AM
  2. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 09:41 AM
  3. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 05:38 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  5. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 07:16 PM

Search Tags


/mathhelpforum @mathhelpforum