Results 1 to 2 of 2

Math Help - How to use Euler's theorem ?

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    17

    How to use Euler's theorem ?

    Can someone please check/comment on my work?

    1. Find the order of 7 modulo 172.
    I did this by trial and error
    7^1= 7(mod 172)
    7^2= 49(mod 172)
    7^3=171(mod 172) -----> 7^3 = -1(mod172)
    squaring it
    7^6 = (7^3)^2 = (-1)^2 = 1(mod 172)
    so the order is 6

    When I tried Euler method,
    m =172
    Φ(172) = Φ(2^2 * 43)
    By rules: If p is prime then a) Φ(p)=p-1 b) Φ(p^e)=(p^(e-1))(p-1)
    Φ(2^2 * 43) = 2*42 = 84
    7^84= 1 (mod 172) [Can this be simplified?How?]

    2. Prove that for any n, 33 divides (n^101) - n
    33 has factors of 3 and 11. so n^101 - n is divisible by 11 and 3
    I use fermat's theorem n^p = n (mod p)
    n^p-1 = 1(mod p)

    n= 1(mod 3)
    n^100 = 1(mod 3)
    n^100 * n= n(mod 3)
    n^101 - n = 0 (mod 3)

    n= 1(mod 11)
    n^100 = 1(mod 11)
    n^100 * n= n(mod 11)
    n^101 - n = 0 (mod 11)
    therefore n^101 - n divisible by 33.

    Im not too sure if the proof is correct.
    I would like to know how to do this problem with Euler's Theorem.

    3. Calculate Φ(5525)
    Φ(5525) = Φ(5^2 * 13 *17)
    By rules: If p is prime then
    a) Φ(p)=p-1 b) Φ(p^e)=(p^(e-1))(p-1)
    Φ(5^2) = 20 Φ(13)=12 Φ(17)=16
    Φ(5525) = 20*12*16 = 3840
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Find the order of 7 modulo 172.
    the order of a number "a" is the least number such a^r = 1 mod (certain number)

    but in Euler's theorem they did not say a^\phi(n)\equiv 1 (mod n) if (a,n)=1 but it is the not the least number

    Example

    5^2 \equiv 1 (mod 12)

    but \phi(12) = (2^2 -2)(2) = 4

    5^3 \equiv 1 (mod 31)

    \phi(31) = 30

    second question your proof is not correct since how do you know that

    n \equiv = 1 (mod 3)
    maybe n=5
    but you can prove it like this
    you have two cases for every case for 3

    if 3 divide n it is clear that n^101-n is divisible by 3

    if not (n,3)=1

    \phi(3) = 2

    n^{100} = (n^2)^{50}

    n^2 \equiv 1 (mod 3)

    (n^2)^{50} =1 (mod 3) multiply with 3

    n^{101} = n (mod 3)

    for 11 same
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 09:07 AM
  3. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 05:47 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 04:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum