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

1. ## 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

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