Remainder Question with Multiplicative Order

Find remainder when 13^400 is divided by 187.

I can only tell you the general solution.

I am note sure whether this is shortest or the best.

I have tried some trial and error in the end to arrive at solution fast but it looks unlikely to work in an exam.

First let me write the result I’ll use.

a^(p-1) = 1 (mod p)
provided a is not a multiple of p

or a and p don’t have a common factor

and p is a prime.
Say 5^(7-1) =1 (mod 7)

5^6 = 1 (mod 7)

Here 7 is the prime

And 5 is not a multiple of 7 and they don’t have a common factor as well

so the equation holds
A simple example is 7^(3-1) =1 (mod 3)

7^2 = 1 (mod 3)

Or 49 =1 (mod 3)

We know 49 will leave remainder 1 when divided by 3 so it holds.

Now let us get back to problem.
13^400

Let us forget 400 for the moment
we have to work with are 13 and 187

Unfortunately 187 is not a prime

187 =11*17

So we cannot say 13^186=1 (mod 187) …This would be incorrect

So we have to take recourse to similar theorem

It says a^(phi(n)) =1 (mod n)

Provided a is not a multiple of n

Or n and a don’t have a common factor.

Where phi(n) is Euler number of n.

Luckily 13 is not multiple of 187 neither they do have a common factor…..

Next step we write

13^(phi(187)) = 1 (mod 187)

All we have got to do is to find phi(187)

Now 187=11*17

Therefore phi(187)= 187(1-1/11)*(1-1/17)

= 187*10/11 *16/17 = 160

We can write

13^160 =1 (mod 187)
As 400=160*2+80

Therefore 13^400 = (13^320)*(13^80)

As 13^320=(13^160 )*(13^160) =1*1 =1

Therefore 13^400 = (13^320)*(13^80)= 1* (13^80)=13^80 (mod 187)

We have to work with 13^80

And we don’t have any magic bullets left so we try to start from scratch

Idea is to construct 80 as sum of powers of 2….


We have 13 =13 (mod 187)

13*13 =13^2 = 169 = -18 (mod 187)

Reduce 169 to -18 by subtracting 187

Now 13^4 = (13^2)*( 13^2)

Replace 13^2 by -18

13^4 = -18*-18 = 324 = 137 = -50 (mod 187)

Here we reduce 137 to -50 by subtracting 187 so that we get a smaller number to work with.
13^8 = (-50)*(-50) =2500 = 69 (mod 187)

13^16 =69*69= 4761 = 86 (mod 187)

Similarly we get

13^32 = 103 (mod 187)

13^64=137 (mod 187)
Since 80 = 64+16

13^80 = (13^64)*(13^16)= 137*86 = 11782 =1 (mod 187)

Answer is 1
However this is very lengthy process

Can we simplify it a bit….
We return to 13^160 =1 (mod 187)

There’s a very important theorem which might save the day

It says if there’s a smaller number say k

Such that 13^k = 1(mod 187)

Then k must divide 160

It is a general theorem it says if we have a^(phi(n)) =1

Then for any smaller number k if it holds

a^k = 1 (mod n)

Then k must divide phi(n)
We may try divisors of 160

Say we take 10 =8+2

So 13^10 = 13^8 * 13^2= 69* -18 = -1242 = 67

It is not 1

Let us try 20

13^20=13^10 * 13^10 = 67*67=4489 =1 (mod 187)

It works

So it follows any power which is multiple of 20 will leave remainder 1

Therefore 13^400 =1 (mod 187)



Now let us return to

if we have a^(phi(n)) =1

Then for any smaller number k if it holds

a^k = 1 (mod n)

Then k must divide phi(n)
Why do you think this works
We have to return to group theory.

All numbers relatively prime to 187 and smaller than it form a group…

And order of group is phi(187)

I,e phi(187) elements are present in group.

Lagrange theorem says that if there’s subgroup of this group

Then order of subgroup must divide order of the original group.


Now if we have k

a^k = 1 (mod n)

Then a k order group exist which os sub group of the original phi(n) order subgroup.
k is also called multiplicative order of a mod n

k is minimum number for which a^k =1 (mod n) holds