Reminder Theory
This chapter is incomplete
-
Basic Concepts
-
Fermat’s Theorems
-
Euler’s Theorems
-
Chinese Remainder Theorem
-
Discrete Logarithms
Examples :
1. What is the remainder of (7777...upto56 digits)/19 ?
Froum post : http://www.cat4mba.com/node/2971#comment-1378
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
==================================
METHOD2 (Stepwise Calculation)
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
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