Finding remainders using Euler's theorem

This method is very useful when the divisor and dividend are relatively prime numbers...

step 1: To calculate euler's no. of a divisor.

euler's no. can be practically taken as cyclicity in remainders by a divisor..

to find euler's no, express the divisor in terms of prime factors...

100 = 2^2 x 5^2.

powers of the prime nos. have no significance...its jus the prime no. that matters...

euler's no (e for convenience) = divisor x (1-1/first prime factor) x (1-1/second prime factor) x ... (1-1/last prime factor)

so, for 100, e = 100 x (1-1/2) x (1-1/5) = 100 x 1/2 x 4/5

= 40.

that means e for 100 = 40. or, in other words, 100 divisor will definetly show a cylicity of 40 in the remainders.

whenever the power of a relatively prime no. will be a multiple of 40, the expression wud show a remainder 1 with 100.

e.g. 3^120 % 100 = ?

we know e for 100 = 40.
3 n 100 are relatively prime nos.
hence, 3^40 % 100 = 1.

hence 3^120 % 100 = (3^40)^3 % 100 = 1^3 = 1.



7^100 % 45 = ?

45 = 3x3x5

e for 45 = 45 x (1-1/3) x (1-1/5) = 24


hence, 7^24 % 45 = 1

hence, 7^100 % 45 = 1^4 x 7^4 % 45

= 2401 % 45

= 16, the required answer...

Finding remainders using cyclicicty with remainders:

This approach is useful when the divisor is small or at times when it is a factor of 100.

3^327%7 = ?

3^1 % 7 = 3
3^2 % 7 = 2
3^3 % 7 = 6
3^4 % 7 = 4
3^5 % 7 = 4x3 % 7 = 5
3^6 % 7 = 5 x 3 % 7 = 1
3^7 % 7 = 1 x 3 % 7 = 3

remainder with first power is same as remainder with 7th power...hence v can say that cyclicity in remainders is 7-1 = 6.

so, 327 % 6 = 3, 

hence, effectively, the remainder is 3^3 % 7 = 6

For Example:

3003^9000%(9*1000)

3003^9000%9 = 0 -----> 9k1

3003^9000%125*8
3^9000%125 = 0 ----> 125a
3^9000%8 = 0 -------> 8b -----------> 1000k2

1000k2 = 9k1 ---> 9000%9000 = 0 
so rem = 0

TO FIND SQUARE OF A 3 DIGIT NUMBER

LET THE NUMBER WHOSE SQUARE IS TO BE CALCULATED BE XYZ.

Sq(XYZ) is calculated like this

STEP 1. Last digit = last digit of SQ (Z)
STEP 2. Second Last Digit = 2*Y*Z +  carryover from STEP 1.
STEP 3. Third Last Digit 2*X*Z+ Sq(Y) +  carryover from STEP 2.
STEP 4. Fourth last digit is 2*X*Y +  carryover from STEP 3.
STEP 5. In the beginning of result will be Sq(X) + any carryover from Step 4.

EXAMPLE:

SQ (421)

STEP 1. Last digit = last digit of SQ (1) =1
STEP 2. Second Last Digit = 2*2*1 + any carryover from STEP 1= 4
STEP 3. Third Last Digit 2*4*1+ Square (2) + any carryover from STEP 2.= 2*4*1 +4= 12

  so 2 would be the third last digit  and 1 carryover
STEP 4. Fourth last digit is 2*4*2 + any carryover (which is 1)  = 16+1=17.

 So 7 and carry over 1.
STEP 5. In the beginning of result will be Sq (4) + any carryover from Step 4.

 So 16+1 =17.

So the result will be  177241.


Hope you enjoyed the concept.

Zeller's Rule

Today, I present before you a rule  that can solve your woes in calendar/dates kind of problems.

 With this technique named after its founder Zeller, you can solve any 'Dates and Calendars' problems.

Zellers rule can be used to find the day on any particular date in the calendar in the history. All you have to know is the formula given below and how to use it.

Zeller's Rule Formula:

F = K + [(13xM - 1)/5] + D + [D/4] + [C/4] - 2C

K = Date => for 25/3/2009, we take 25

In Zellers rule months start from march.

M = Month no. => Starts from March.

March = 1, April = 2, May = 3

Nov. = 9, Dec = 10, Jan = 11

Feb. = 12

D = Last two digits of the year => for 2009 = 09

C = The first two digits of century => for 2009 = 20

Example: 25/03/2009

F = 25 + [{(13 x1)- 1}/5] + 09 + 09/4 + 20/4 - (2 x 20)

= 25 + 12/5 + 09 + 09/4 + 20/4 - 2x20

=25+2+09+2+5-40

[ We will just consider the integral value and ignore the value after decimal]

= 43 - 40 =

Replace the number with the day using the information given below.

1 = Monday

2 = Tuesday

3 = Wednesday

4 = Thursday

5 = Friday

6 = Saturday

7 = Sunday

So it's Wednesday on 25th march, 2009.

If the number is more than 7, divide the no. by 7. The remainder will give you the day.

I hope you will find the above method very useful.

Quant Concepts-Square of Numbers

Over the next few weeks , I will be covering some essential quantitative ability concepts which are a must for cracking the QA/DI section of CAT.

Let me start by explaining the concept of calculating squares of numbers.

Say , a number 312

312^2.

Determine the closest power of  100/10 as the case may be which is called the base.

In this case we obtain a base of 300.

represent 312^2 as (300+12)^2. here, deviation=12.

 Now,

 follow the step

ldigit(s) before 0 in base x  (number  + deviation) | deviation^2 where | is a separating  line separating 2 parts of calculation.

 

Remember ,

no. of digits on right side of the imaginary line should be exactly same as the no. of zeros in our base.

 

So, our problem boils down to:

3 x (312 + 12) | 12^2

3x324 | 144

972 | 144

= 97344....1 of 144 carried .

Another example:

38^2

base 30

3x(38 + 8 ) | 8x8

= 138 | 64

= 1444( as only digit should be on the right side of the imaginary line as base has one zero)

So,the 6 in the imaginary part is added to 138.

Comments are welcome and in case of doubts just leave a comment. I will cover them and other concepts in the next blog.

 

.