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

• Feb 21st 2010, 12:53 AM
heldrida
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
• Feb 22nd 2010, 09:07 AM
qmech
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