Results 1 to 5 of 5

Math Help - eulers theorme

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    eulers theorme

    Use eulers theorem to find the least nonnegative residue modulo m of integer n

    n=79^79, m=9
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Note that: 79 \equiv 7 \ (\text{mod }9), i.e. 79^{79} \equiv 7^{79} \ (\text{mod } 9)

    By Euler's theorem:
    \begin{array}{rcll}7^{\varphi (9)} & \equiv & 1 & (\text{mod } 9) \qquad \varphi (9) = \varphi (3^2) = 3 \cdot 2 = 6 \\ 7^6 & \equiv & 1 & (\text{mod } 9) \\ \left(7^6\right)^{13} & \equiv & 1^{13} & (\text{mod } 9) \\ & \vdots & & \end{array}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    98
    s
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by o_O View Post
    Note that: 79 \equiv 7 \ (\text{mod }9), i.e. 79^{79} \equiv 7^{79} \ (\text{mod } 9)

    By Euler's theorem:
    \begin{array}{rcll}7^{\varphi (9)} & \equiv & 1 & (\text{mod } 9) \qquad \varphi (9) = \varphi (3^2) = 3 \cdot 2 = 6 \\ 7^6 & \equiv & 1 & (\text{mod } 9) \\ \left(7^6\right)^{13} & \equiv & 1^{13} & (\text{mod } 9) \\ & \vdots & & \end{array}

    could u possibly finish out the problem and explain it as like an example problem. The book only talks about this topic and just dives into problem set without any examples. Also, why is it not 79^6 but rather 7^6??
    Follow Math Help Forum on Facebook and Google+

  5. #5
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Well we want to find: 7^{79} \equiv a \ (\text{mod } 9) for some a.

    We have that \left(7^6\right)^{13} = 7^{78} \equiv 1 \ (\text{mod }9)

    Not too hard to see how we get to 7^{79}.

    As for calculating \varphi (m), you need to find its prime power decomposition. With this, use the fact that:
    (1) \varphi (p^n) = p^{n-1} (p-1)
    (2) \varphi (m) is multiplicative which means \varphi (p_{1}^{e_{1}} \cdot p_{2}^{e_{2}}) = \varphi (p_{1}^{e_{1}}) \cdot \varphi (p_{2}^{e_{2}})

    where p is prime.

    For example: \varphi (20) = \varphi (2^2  \cdot 5) = \varphi (2^2) \cdot \varphi (5) = 2^1 (2 - 1) \ \cdot \ 4 \ = 8
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Eulers Method
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 12th 2011, 02:36 AM
  2. Eulers Totient
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 1st 2011, 08:56 AM
  3. Eulers formula
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: January 10th 2010, 07:27 AM
  4. eulers
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 7th 2009, 11:46 PM
  5. Eulers theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2006, 10:50 PM

Search Tags


/mathhelpforum @mathhelpforum