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

A question of Counting

I am indebted to my friend Shekhar for helping me generate material for this blog.
How many 6-digit number contain exactly 4 different digits?

Solution.
In Short
10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!) - 1/10*(10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!))
=226800+100800-1/10(226800+100800)= 294840

The Detailed solution is as following
Start by picking
any four distinct digits from 0,1,2,3,4,5,6,7,8,9
Note I included 0

This can be done in 10C4 ways
Of these 4 digits I can choose 2 digits that will occur twice in the final number

Say I chose 1 2 3 4
then I can choose any two of them which will occur twice
say a number of form 1 2 3 4 3 2
Where in 3 and 2 repeat once each

Total ways in such a selection can be made is

10C4* 10C2

now suppsing I have 1 2 3 4 and I have 3 2 that will occur in duplicates
I can form any permutaion of them to get a new number

So total number of ways will be

number of selection multiplied by possible arrangements
which is just permutaion of 6 things where 2 things occur more than once
that is 6! (2! 2!)
gives me a total of

6! (2! 2!) * 10C4* 10C2

Is that all
No we can have a case wherein a digit is triplicate instead of two duplicates

again same rule applies

I choose 4 distinct digits in 10 C 4 ways
Then I choose one digit from these chosen 4 numbers which will occur thrice in 4C1 ways
total of
10C4*4C1 ways
and total number of numbers such formed as

10C4*4C1 * 6!/(3!)

Howver that is not all
I need to subtract cases where in 0 occurs as first digit
Howvere a 0 will be the first digit in one tenth of cases
This is becuase first place will be occupied by 1,2,3,4,6 etc equal number of times
So I subtract 1/10 of the sum of above two cases
which gives me the final result

A Distribution Problem

A Question sent to me by my dear friend

1. Six white and six black balls of the same size are distributed among ten urns so that there is at least one ball in each urn.
What is the number of different distributions of the balls?

The solution in short is

2*10C6 - (10C6 * 6C2) + (10C6* 10C1)*2+ (10C5*5C1)*5C1=18900-3150+4200+6300
=26250

The details are as following

First of all note this very follwoing important point.

Whenever I distribute the balls
Every case I consider should be completely disjoint
That is my cases should never oeverlap
It will get clearer as I proceed


Supposing I label the 10 urns as 1,2,3,4,5,6,7,8,9,10.
Observation one : Urns are distinguishable

I have 6 red and 6 black balls

Observation two : 6 blacks are not distinguishable among themselves
6 whites are not ditinguishable among themselves

The aim is to distribute the balls so as each distibution which
we count has to be different in some sense
1) Each Urn has a different number of balls
2) if the urn has same number of balls, for each urn in two different distributions , then colour of a ball must be different for at least one urn

Say number of balls in a distribution D1 and D2 urn
is such that 1,2,3,4,5,6,7,8,9,10 have exactly equal number of balls then
at least one of the urns must have ball of different colour
only then I can call D1 and D2 as different and count them.

Let us proceed

Supposing I distribute this way

Case 1

I choose ANY 6 urns then I fill them with black balls.
I get 6 filled and 4 empty
I fill the 4 remaining empty urns with 4 RED balls
So I have 2 RED balls left
I choose any 2 of the 10 urns each having a single red or black ball and place the remaining 2 red balls
I get for this
10C6 that is choosing 6 urns out of 10
4 urns are always empty I need not choose them.
But the 2 urns for remaining 2 Red Balls can be chosen in 10C2 ways
So I get for whole process
10C6*10C2
Now I started out with balck balls
What if I started out with RED balls.
I proceed identically and choose 6 urns for RED and then distribute the rest of 2 blacks among any 2 of 10 urns.
So I get 2* (10C6*10C2) for red and balck for 6 and 2 kind of distribution
But wait
Supposing I distributed 6 red in urns 1,2,3,4,5,6
And 4 blacks in 7,8,9,10
I have 2 blacks supposing I put them in urns 5,6
problem is that this kind of distribution was possible from other way around as well that is
I distribute 6 Black balls in urns 5,6,7,8,9,10
4 reds in 1,2,3,4 and remaining 2 reds I put in 5,6
There's a double counting I need to elimiante
the problem only occurs if I put remaining last two balls in urns containing ball of a different colour.
So I subtract
10C6*6C2 to eliminate double counting
because after I put 4 balls in urns of a particular colour the last two balls can be put in urn containing balls of different colur in 6C2 ways



Case 2

I put 6 red balls in any 6 urns
then 4 black in remaining 4 empty urns
and remining 2 black balls together in any of the 10 urns having 1 ball of any colour

this can be done in 10C6*10C1 ways
And since I can start with black instead of red I multiply by 2
to get
(10C6* 10C1)*2

there will be no double counting you can convince yourself.


Case 3

I choose 5 red balls and put them in any urns
Then I choose 5 black balls and put them in rest of 5 empty urns
Then I choose 1 remaining red ball and place it in urn having red ball
Then I choose 1 remaining black ball and place it in urn having black ball
that is red goes to red and black goes to black

5 black can be chosen 10C5 ways
rest 5 are automatically chosen I don't need to choose again for red
the one remaining black can be put in any of 5 urns containg black in 5C1 ways
and 1 remaing red can be put in any urn contain red in 5C1 ways

I get in total (10C5*5C1)*5C1


Finally

I add all of them
The point is that all of the distributions in Case 1,2,3 should be totally exclusive to any other
There cannot be way that a distribution belonging to Case 1 can be found in Case 2 or Case 3
Second point is case 1,2,3 exhaust all possible scenarios
There's no distribution possible which does not belong to any one of the cases
These two points should crack most of the tough problems
The difficult part is forming the cases.