Results 1 to 3 of 3

Math Help - [SOLVED] Two questions about Euler

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    4

    [SOLVED] Two questions about Euler

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


    2. find all n such that \phi(n) = 6.
    i really have no idea about this one.
    i try \phi(X) = \phi(m) \phi(n) where (m.n) = 1 & \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: <br />
74800 = 2^4  \cdot 5^2  \cdot 11^1  \cdot 17^1 <br />

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

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

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

    So we have: <br />
3^{80}  \equiv 1\left( {\bmod .74800} \right)<br />
and <br />
51204 \equiv 4\left( {\bmod .80} \right)<br />
thus <br />
3^{51204}  \equiv 3^4 \left( {\bmod .74800} \right)<br />

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

    Then we may write: <br />
\frac{n}<br />
{{\prod\limits_{\left. p \right|n} p }} = \frac{6}<br />
{{\prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} }}<br />
(1)

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

    Thus: <br />
n = 2^\alpha   \cdot q^{\beta}<br />
where q is an odd prime

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

    Consider firsrt \alpha>0

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

    So we have got the solutions <br />
n = 14;n = 18<br />

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

    It remains to check what happens when n is a power of 2. In this case (1) turns into <br />
2^{\alpha  - 1}  = 6<br />
which is impossible. ANd so we have all the possible solutions
    Last edited by PaulRS; April 17th 2009 at 11: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 \phi(74800) = \phi (5^2) * \phi(2^4) * \phi(17) * \phi(11) = 25600
    and 3^{\phi(74800)} = 3^{25600} \equiv1(\bmod 74800)
    51204 \equiv 4( \bmod 25600)
    so, 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: June 25th 2011, 11:49 AM
  2. Euler's Theorem Questions
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: October 7th 2010, 04:15 PM
  3. [SOLVED] Euler Method
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: July 14th 2009, 09:46 PM
  4. ODE solved using Euler's equation
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: January 20th 2009, 11:35 AM
  5. [SOLVED] Euler Expression
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 16th 2009, 01:38 PM

Search Tags


/mathhelpforum @mathhelpforum