Friday, June 27, 2008

Solving Remainder Based Questions

Ok. Write it down. The next time you see a question on remainders while giving a test, you would feel really lucky. Because I am going to describe some very useful methods that can be used to this end.

Let us start with the basic ones - (note - in all the formulas below, x mod y means the remainder obtained after dividing x by y)

ab mod x = (a mod x) * (b mod x)

If a mod x = 1, then a^k mod x = 1 for any integer k > 1

If a = lx + 1, then a^k mod x = 1 for all k > 1

If a = lx -1, then a^k mod x = (-1)^k for all k > 1

Let us cover some examples

5^43 mod 13 = ?

Whenever you see such questions, try to get the base of the exponent as close to a multiple of the diviser as possible. We see that 5^2 = 26 - 1. Hence,

5^43 mod 13 = 5. 5^42 mod 13 = 5 mod 13 . 25^21 mod 13 = 5.(-1)^21 mod 13 = -5 mod 13 = 8 mod 13

The ones described above are the basic formulae related to modulo arithematic. Let now get a bit deep into it. We will cover two theorems here:

1) Chinese Remainder theorem
2) Euler's extension of Fermat's theorem

Chinese Remainder theorem: For a specific number N, if N mod a = k1, N mod b = k2, such that a and b are co-prime (gcd(a,b) = 1) then all solutions of M mod a = k1 and M mod b = k2 in the set of the natural numbers are equivalent modulo ab.

Too tough to understand? Well, it's not as tough if we take an example:

Let us say we have to find the remainder when

66666... 1730 times is divided by 45.

Since it is difficult to find the remainder when the number is divided by 45, we take the divide and conquer approach.

First divide 66666... 1730 times by 5, remainder is 1
Divide 66666.. 1730 terms by 9, remainder is 6*1730 mod 9 = 6*2 mod 9 = 3

Chinese remainder theorem states that if we are able to find a number < 45 that satisfies the above two conditions, then that number itself is the remainder when the big number is divided by 45. Let's list all numbers which are give a remainder of 3 when divided by 9. They are:

3,12,21 <- while listing, we have arrived at a number which leaves a remainder of 1 when divided by 5. And this number itself is the answer! Note: To increase your speed, you should start listing based on the greater of the two numbers, which in this case is 9.


Euler's extension of Fermat's theorem:

If a and n are co-prime (gcd(a,n)=1), then a^phi(n) mod n = 1, where phi(n) is the Euler Totient function of n, which can be obtained as n(1-1/p1)(1-1/p2)...(1-/1pn); p1, p2...,pn being the prime factors of n


OK. This also looks a bit convoluted. Let's take up an example instead.

What are the last 2 digits of 3^768?

We basically need to find 3^768 mod 100 here. We have phi(100) = 100(1-1/2)(1-1/5) = 40 (as 2,5 are the prime factors of 100).

Now since 3^40 mod 100 = 1, we have 3^768 mod 100 = (3^40)^19 mod 100 . 3^8 mod 100

= 1 mod 100 * 3^8 mod 100

= 3^8 mod 100 = 81^2 mod 100 = (100-19)^2 mod 100 = 19^2 mod 100 = 61.

Hope some of the concepts are clear to you by now. I will be updating this post as I post solutions to questions on remainders. If you have any, please send them across.

Word List!

Ok, now that I have been reading news and articles online for quite some time, I have gathered a good amount of typical words which I came across, whose meaning I either don't know or partially know. I am going to list all those words which I happened to save in my wordweb bookmarks. Here they are:

pygmy
clique
tautological
scuttled
faux pas
plaintive
miasmic
comeuppance
grouse
wrench
throes
scurrilous
ecumenical
verity
blindside
reprobate
barratry
athenaeum
compendious
pretermit
agrestic
yataghan
lineament
barrage
deracinate
cogent
forfend
misoneism
paraph
chimera
belch
Machiavellian
decree
fiat
enation
propitious
emend
quiescent
prelate
prolate
harangue
sanguinary
gloam
currish
cinch
jabberwocky
sardonic
reclamation
officious
vernacular
volubility
vertiginous
coda
hobble
limpid
teetotaller
ostentatious
apocryphal
prance
despodent
totempole
pulpit
precocity
abstemious
abrogate
abomination
smokescreen
foal
inoculate
yeomanry
yuppify
squalid
avow
avar
august
audacious
attenuate
astringent
assuage
arrant
arabesque
apropos
aprobation
amortise
ambrosial
aclove
blemish
pleonasm
apothecary
unguent
iconoclast
calumniate
malodorous
descry
bequeath
premonition
prurient
contrite
cognate
nettle
jocund
confect
comfit
concoction
exorcise
reconnaissance
abstruse
recondite
desideratum
sesquipedalian
fecund
ethereal
adjure
conjure
beseech
swivet
sequester
jangled
romp
diocese
irascible
pachyderm
demotic
dulcet
braggadocio
echelon
jitters
dystopia
mea culpa

.. There are many more, but I think these should suffice for now.

Thursday, June 26, 2008

AIMCAT 0818 Results

Yes! AIMCAT 0818 results are out - and I am extremely elated by my performance, though there are many areas which need improvement. Also, I have to be very cautious not to turn complacent. After all, this mock was really easy and was a high scorer, though the DI section appeared a tad bit tougher to me. Here is how attempted the paper:

Started with Quant. I had a little slow start. I wasted quite an amount of time on the question based on venn diagrams and on the max/min question. But again gathered momentum. Interpretted the question on area bounded by curves completely wrong, and also wasted some time on the time/work question with no result. Other than that, I was moving pretty fast, leaving questions wherever they appeared to be on the tougher side. By the time I reached the 15/16th question, 45 mins were already over! Couldn't resist the temptation to solve some more questions. Ended up spending a little less than an hour. Attempted 18 questions, got 15 right 3 wrong. I still have to get over making mistakes - I made a really bad mistake in the time/distance set and made a wrong guess in the last question, apart from interpretting the graph question completely wrong. Quant - 57

Till now, I had been doing VA after Quant, but I had come decided that I would change by strategy - I would do DI second and VA atlast. I realized that by the time I start doing DI at the end, I get already exhausted and it becomes really difficult to put my grey matter at work. Looked at the DI sets - one by one. Tried to approach the first one, but found that the set outwitted me. Raalizing it, I switched to the last one as it seemed familiar. Started doing the set, filling the values of flow in all pipes, assuming the flow in one of them as 'x'. But after a lot of time, I realized that I had made a mistake. So had to do the entire calculation again!! This one set ate away about 35 minutes of my time, and I had already alotted 1 hour for math - so that left with me with just one more hour. Decided to shift the burden of time on VA. Saw the set on cricket scores - but soon realized that it was logic intensive and if I am not able to solve it - I will waste a lot of time. Then switched to the set on the growth rate of vehicles. Realized that the first two questions were sitters and did them soon. Then wasted some time on the third question just to realize that it was not so easy and was even calculation intensive. Then saw the second set, just reading it took a lot of my time. Though I realized that it was an easy set, I couldn't attempt it as I had really had very less time left and any attempt from now would be suicidal for my VA section. Attempted seven, got all seven correct. Was satisfied by my accuracy, but should have not made mistakes in the first set. Also, I shouldn't have taken more time on QA as it put a lot of time pressure on me, and I ended up making mistakes.

By the time I started VA, I had a little more than 40 minutes left with me. Started reading the last passage on environment, as the topic interested me. Got all the answers correct, except one. Took 10 minutes to complete answering the passage. Then went on to the passage on happiness, took 10 more minutes to answer all questions. Got all questions correct except the one on the mood of passage. (I had a dilemma that it could be reflective, but marked something else). Now went on to read the last passage it took more time read this one. Took 12 minutes and answered all questions, with one wrong. (The one on why the author wants people to come to the protest). Now went on to the correct ending of passage questions and got 2 of the 3 correct. (Got the one on government surveillance wrong). In the last minute, attempted one question on restatement (the Rafael Nadal one) and got it correct. In total, attempted 19, got 4 wrong. Amazing accuracy - but this is not the actual CAT, where it is bound to be low.

So here are my scores in the end:

DI - 28 - 91.23
QA - 57 - 99.31
VA - 56 - 98.54

OA - 141 - 99.52 (AIR - 132)

Monday, June 23, 2008

First Post!

I am also one of those aspirants who want to get to the best business schools of India aka the IIMs. I will cover the happenings in my CAT journey here. If you have some good puzzles/problems, please send it to me at v dot 39312 at the rate of gmail dot com. I will try my level best to post the solutions here.