Results 1 to 2 of 2

Math Help - How to solve "397^611 mod 1763" without calculator?

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    13

    How to solve "397^611 mod 1763" without calculator?

    hi,

    I've been trying to figure this one, trough Eulers theorem, but without
    success. I do know the answer, with the calculator, but I would like
    to know, how to solve it manually...

    Any tips and sugestions on solving this type of exercices, is appreciated!

    I'm sure I'll get more like this!

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    Barring any calculation errors, here's how to do it manually:

    Find x, where:

    x = 397^611 mod 1763

    Step 1.
    ----
    Note 1763 = 42^2 - 1 = 41*43.

    Step 2.
    ----
    You now have 2 problems:

    Find a, where:

    a = 397^611 mod 41, and

    Find b, where:

    b = 397^611 mod 43.

    Step 3:
    ----
    Note: 397 == -13 (41), so
    a = (-13)^611 (41).

    Use Fermat's little theorem to say for any y, y^40 == 1 (41) and
    note 611 == 11 (40), so

    a = (-13)^11 (41)
    a = 169^5 * 28 (41)
    a = 5^5 * 28 (41)
    a = 125 * 25 * 28 (41)
    a = 2 * 25 * 28 (41)
    a = 15 * 25 (41)
    a = 375 (41)
    a = 6 (41)

    Step 4:
    ----
    Note 397 == 10 (43), and 611 == 23 (42), as before:
    b = 10 ^ 23 (43)
    b = 1000 ^ 7 * 100 (43)
    b = 1000 ^ 7 * 100 (43)
    b = 11 ^ 7 * 14 (43)
    b = 121 ^ 3 * 154 (43)
    b = (-2) ^ 3 * 25 (43)
    b = -200 (43)
    b = 15(43)

    Step 5:
    ----
    Since 2*21==1(41), 43*21==1(41).
    Since (-2)*(-21)==1(43), 41*21==1(43)

    The number
    n = 6*43*21 + 15*41*21 satisfies both congruences in step 2.

    The Chinese remainder theorem says it also equals x.

    x = 21*(6*43+15*41) mod (41*43)

    x = 703 + 1763*k, with k any integer.

    QED
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  2. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  3. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  4. Replies: 2
    Last Post: August 6th 2010, 08:26 PM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum