Home » Math e Book

Reminder Theory

Submitted by cat4mba on Thu, 2007-08-02 11:26

 

This chapter is incomplete

  1. Basic Concepts
  2. Fermat’s Theorems
  3. Euler’s Theorems
  4. Chinese Remainder Theorem
  5. Discrete Logarithms

Examples :

1. What is the remainder of (7777...upto56 digits)/19 ?

Froum post : http://www.cat4mba.com/node/2971#comment-1378

The basic funda is
Any number a repeated N times is divisible by P where P is a prime number and N is the recurring decimal of P

For example:
Recurring decimal of 7 is 6 since 1/7 = 0.142857 ( Repeats after six digits)
So 111111 (6 times) is divisible by 7
222222 (6 times) is divisible by 7
555555(6 times) is divisible by 7

Similarly for 19 the recurring decimal is 18
So 111111, 111111, 111111 (18 times) is divisible by 19
And 777777,777777,777777 (18 times) is divisible by 19
=> 7777(54 times) is divisible by 19
Now 7777( 56 times) = 7777( 54 times) 0 0 + 77
=>required reminder = reminder of 77 divided by 19 = 1

Now Big Question
How to find the recurring decimal for a prime number?
From my experience I found the number P-1 is always a multiple of recurring decimal and this information is enough to solve most of the questions.

For example 11  ,  1/11 = .0909 ; recurring decimal =2 and p-1=10 is a multiple of 2
13, 1/13 = 0.0769230; recurring decimal = 6 and p-1=12 is a multiple of 6.
Notes:
1. I have never tried to search/prove the above.
2. There are few exception like number 3 and 5 and I would love to know that if there z any more

==================================

Chinese Remainder Theorem is used to find integers x that simultaneously solve the following equation
x = a1 (mod m1)
x = a2 (mod m2)
. . . . .
x = an (mod mn)
 
For example : A number when divided by 4 gives a reminder 3, when divided by 3 gives a reminder 2 and when divided by 5 gives a reminder 4. Find the number
 
METHOD1 (Simple Logic)
x =3 (mod 4 ) ------- (eq1)
x =2 (mod 3) -------- (eq2)
x = 4 (mod 5) ------- (eq3)
 
The values of x which satisfy equation 1 are 7, 11, 15 and etc. Our first target is to find the value of x from this series which is divisible by both 3 and 5 (i.e by 15)
 
The first number in the series that is divisible by 15 is 15. So lets take n1 = 15.
 
Now we‘ll follow the same process for eq (2)
The series is 5, 8, 11, 14 . . . . . The first number which is divisible by both 4 and 5 (4. 5 = 20) and gives a reminder 2 when divided by 3 is 20 (n2).
 
Now we‘ll follow the same process for eq (3)
The series is 9, 14, 19. . . . . The first number which is divisible by both 4 and 3 (4. 3 = 12) and gives a reminder 4 when divided by 5 is 24 (n3).
 
Now the number which satisfy all the above three equation is
N = n1 + n1 + n3 = 15 + 20 + 24 = 59.
N = 59 + (4 * 3 * 5)p          where p is any number
 
 

METHOD2 (Stepwise Calculation)
Let
x = a1 (mod m1)
x = a2 (mod m2)
. . . . .
x = an (mod mn)
 
Step 1:
 Calculate M = m1 x m2 x m3. . . . . x mn
 
Step 2:
Calculate Z1 = M/m1
                Z2 = M/m2
                Z3 = M/m3
. . . . . . . . . .. . . ..
                Zn = M/mn
 
Step 3:
Calculate Y1 where Z1Y1 = 1 (mod m1)
                Y2 where Z2Y2 = 1 (mod m2)
. . . . . . . . . .. . . ..
                Yn where ZnYn = 1 (mod mn)
 
 
Step 4:
Calculate x where x = a1 y1 z1 + a2 y2 z2 + a3 y3 z3+ . . . . . . .
 
Example:
x =3 (mod 4 ) ------- (eq1)
x =2 (mod 3) -------- (eq2)
x = 4 (mod 5) -------- (eq3)
 
Step 1:
 Calculate M = m1 x m2 x m3. . . . . x mn
                      = 60
Step 2:
Calculate Z1 = M/m1 = 15
                Z2 = M/m2 = 20
                Z3 = M/m3 = 12
. . . . . . . . . .. . . ..
                Zn = M/mn
 
Step 3:
Calculate Y1 where Z1Y1 = 1 (mod m1)
15Y1 = 1 (mod 4)
Calculate it by trial and error method
For Y1= 1 ; 15 = 3 (mod 4)
For Y1= 2 ; 30 = 2 (mod 4)
For Y1= 3 ; 35 = 1 (mod 4)
So Y1=3 satisfy the condition
 
Similarly Calculate Y2
where Z2Y2 = 1 (mod m2)
20Y2 = 1 (mod 3)
=> Y2 = 2
. . . . . . . . .
Calculate Y3 where Z3Y3 = 1 (mod m3)
12Y3 = 1 (mod 5)
=> Y3 = 3
.. . . ..
                Yn where ZnYn = 1 (mod mn)
 
 
Step 4:
Calculate x where x = a1 y1 z1 + a2 y2 z2 + a3 y3 z3+ . . . . . . .
X = 3 * 3 * 15 + 2 * 2 *20 + 4 * 3 *12 = 135 + 80 + 144 = 359
359 = 59 mod (60)
And the number in generalized form = 59 + 60P

EXAMPLES

1. find out the last non zero digit of 37!
ANSWER:
From the post http://www.cat4mba.com/node/5310

I have come across this question many times in many places so thought of writing a detail solution.

Please go through it carefully and revert back if you have any problem at any step.

Initially it might seem lengthy but once you have the expertise it wont take more than couple of minutes.

STEP1  Find out the prime factors in the factorial

37! = 2 34 x 5 8 x 3 17 x 7 5 x 11 3 x 13 2 x 17 2 x 19 x 23 x 29 x 31 x 37

STEP2
37! Contains 8 zeros at the end as we have 8 fives in 37!. So we can get the first non-zero digit by dividing 37! With 109 but that is not an easy.
In stead of doing that we  ‘ll first divide 37! With 108 and then we ‘ll try to find out the reminder of the new number when divided by 10.
(Try to clearly understand what is the difference between above two)

STEP3

37!/108 = ( 234 x 58 x 317 x 75 x 113 x 132 x 172 x 19 x 23 x 29 x 31 x 37 )/108

= 226 x 317 x 75 x 113 x 132 x 172 x 19 x 23 x 29 x 31 x 37 = N

STEP4

We ‘ll find the reminder of N divided by 10.
226 = 2 x 225 = 2 x 25 = 2 x 2 = 4
317 = 3 x 316 = 3 x 34 = 3 x 1 = 3
75  = 7 x 492 = 7 x (-1)2 = 7 x 1 = 7
113 = 1
132 = 9
172 = 72 = 9

So reminder of N divided by 10 reduces to
4 x 3 x 7 x 1 x 9 x 9 x 19 x 23 x 29 x 31 x 37
Now multiply left to 2 digits get the reminder divided by 10 and then proceed to the right

4 x 3 = 2
2 x 7 = 4
4 x 9 = 6
6 x 9 = 4
4 x 19 (or 9)= 6
6 x 3( or 23) = 8
8 x 9 = 2
2 x 1 = 2
2 x 7 = 4

And that’s the answer 4

Related Articles: 

E Class Room Topics
Posted on: Mon, 2007-10-15 13:31 #1
Hi,  Under METHOD1 (Simple

Hi, 

Under METHOD1 (Simple Logic), shouldn't it be N = 59 + (4 * 3 * 5)p = 59 + 60p where p is any number instead of N = 59 + (4 * 3 * 12)p where p is any number.

 

Thank You.

 

With Regards,

Arun

 

Posted on: Thu, 2007-10-18 02:35 #2
CRT Discussions

www.cat4mba.com/node/2515#comment-929

Posted on: Thu, 2008-03-20 13:53 #3
Wilson's

Wilson's priciple

http://www.cat4mba.com/node/5270