Results 1 to 3 of 3

Thread: [SOLVED] Two questions about Euler

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    4

    [SOLVED] Two questions about Euler

    1. find $\displaystyle 3^{51204}$($\displaystyle \bmod 74800$)
    i got $\displaystyle \phi(74800) $= 29760 & (3,74800) =1
    so, $\displaystyle 3^{\phi(74800)}$ $\displaystyle \equiv 1$ ( $\displaystyle \bmod 74800 $)
    but what shall i do next? 51204-29760 = 21444, it's still a big number.


    2. find all n such that $\displaystyle \phi(n) $= 6.
    i really have no idea about this one.
    i try $\displaystyle \phi(X) = \phi(m) \phi(n)$ where (m.n) = 1 & $\displaystyle \Sigma(\phi(d) ) $= m where d|m. but got nothing usefull.

    any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    1) Note that: $\displaystyle
    74800 = 2^4 \cdot 5^2 \cdot 11^1 \cdot 17^1
    $

    Now by Euler's Theorem, separately: $\displaystyle
    \left\{ \begin{gathered}
    3^{\phi \left( {2^4 } \right)} \equiv 1\left( {\bmod .2^4 } \right) \hfill \\
    3^{\phi \left( {5^2 } \right)} \equiv 1\left( {\bmod .5^2 } \right) \hfill \\
    3^{\phi \left( {11^1 } \right)} \equiv 1\left( {\bmod .11^1 } \right) \hfill \\
    3^{\phi \left( {17^1 } \right)} \equiv 1\left( {\bmod .17^1 } \right) \hfill \\
    \end{gathered} \right.
    $ (*)

    Consider $\displaystyle
    \rho = {\text{lcm}}\left( {\phi \left( {2^4 } \right);...;\phi \left( {17^1 } \right)} \right) = 80
    $ (least common multiple). THis number satisfies $\displaystyle
    \left\{ \begin{gathered}
    3^\rho \equiv 1\left( {\bmod .2^4 } \right) \hfill \\
    3^\rho \equiv 1\left( {\bmod .5^2 } \right) \hfill \\
    3^\rho \equiv 1\left( {\bmod .11^1 } \right) \hfill \\
    3^\rho \equiv 1\left( {\bmod .17^1 } \right) \hfill \\
    \end{gathered} \right.
    $ by using (*) and knowing that $\displaystyle \rho$ is multiple of each of the exponents there.

    That is: $\displaystyle
    \left\{ \begin{gathered}
    2^4 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\
    5^2 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\
    11^1 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\
    17^1 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\
    \end{gathered} \right.
    $ now since each of the divisors on the LHS are coprime to each other this implies that the product of them divides $\displaystyle
    {\left( {3^\rho - 1} \right)}
    $ that is: $\displaystyle
    74800\left| {\left( {3^\rho - 1} \right)} \right.
    $

    So we have: $\displaystyle
    3^{80} \equiv 1\left( {\bmod .74800} \right)
    $ and $\displaystyle
    51204 \equiv 4\left( {\bmod .80} \right)
    $ thus $\displaystyle
    3^{51204} \equiv 3^4 \left( {\bmod .74800} \right)
    $

    2) Remember that $\displaystyle
    \phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
    {p}} \right)} =6
    $ ( the product goes over the prime numbers dividing n)

    Then we may write: $\displaystyle
    \frac{n}
    {{\prod\limits_{\left. p \right|n} p }} = \frac{6}
    {{\prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} }}
    $ (1)

    So that: $\displaystyle
    \left. {\prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} } \right|6
    $ (2) now if: $\displaystyle
    p > 2 \Rightarrow 2\left| {\left( {p - 1} \right)} \right.
    $ and since $\displaystyle 4\not|6$ it follows that $\displaystyle n$ can have at most one odd prime divisor.

    Thus: $\displaystyle
    n = 2^\alpha \cdot q^{\beta}
    $ where $\displaystyle q$ is an odd prime

    If $\displaystyle \beta>0$ then our (2) turns into $\displaystyle
    \left. {\left( {q - 1} \right)} \right|6
    $ thus: $\displaystyle
    q = 3 \vee q = 7
    $

    Consider firsrt $\displaystyle \alpha>0$

    The LHS of (1) is: $\displaystyle
    2^{\alpha - 1} \cdot q^{\beta - 1}
    $ if (see (1) ) $\displaystyle
    q = 7 \Rightarrow 2^{\alpha - 1} \cdot 7^{\beta - 1} = 1 \Rightarrow \alpha = \beta = 1
    $ and if $\displaystyle
    q = 3 \Rightarrow 2^{\alpha - 1} \cdot 3^{\beta - 1} = 3 \Rightarrow \alpha = 1 \wedge \beta = 2
    $

    So we have got the solutions $\displaystyle
    n = 14;n = 18
    $

    If $\displaystyle \alpha=0 $ then $\displaystyle
    \Rightarrow \phi \left( n \right) = \left( {q - 1} \right) \cdot q^{\beta - 1} = 6
    $ and so either $\displaystyle \beta=1$ and then $\displaystyle n=7$ or $\displaystyle \beta>1$ and so $\displaystyle q=3$ (since q|6) and then $\displaystyle n=9$

    It remains to check what happens when n is a power of 2. In this case (1) turns into $\displaystyle
    2^{\alpha - 1} = 6
    $ which is impossible. ANd so we have all the possible solutions
    Last edited by PaulRS; Apr 17th 2009 at 10:15 AM. Reason: Misread the second question
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    4

    Thx

    thx~~u really help me a lot~
    besides, i want to add that, the 1st one should be more easier~~
    i din't notice that 187 = 11 x 17~ToT~
    since $\displaystyle \phi(74800) = \phi (5^2) * \phi(2^4) * \phi(17) * \phi(11) = 25600$
    and $\displaystyle 3^{\phi(74800)} = 3^{25600} \equiv1(\bmod 74800)$
    $\displaystyle 51204 \equiv 4( \bmod 25600)$
    so, $\displaystyle 3^{51204} \equiv 3^4(\bmod 74800)$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a few questions on (Z/nZ)* and Euler's Totient Function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 25th 2011, 10:49 AM
  2. Euler's Theorem Questions
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Oct 7th 2010, 03:15 PM
  3. [SOLVED] Euler Method
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: Jul 14th 2009, 08:46 PM
  4. ODE solved using Euler's equation
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: Jan 20th 2009, 10:35 AM
  5. [SOLVED] Euler Expression
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Jan 16th 2009, 12:38 PM

Search Tags


/mathhelpforum @mathhelpforum