Ultimate Quant Marathon Blog For IIM CAT

For All Your Quant Queries

Concept 4 Prime Numbers

with 5 comments


I was recently reading a blog by one MIT student, wherein he quotes one of his professors, ” Mathematicians are annoyingly Precise” and he further adds, ” think deeply of simple things“. So thats what we will do, be precise and rigorous in our deep thinking of simple things, that is exactly what CAT wants us to do. Lets roll!

Theorem 4.1 Prime numbers are odd, except for 2, and they have exactly two factors, the number and 1 itself.

You would be wondering, why I have started with this, but whole prime number theory is based on this only.

From here, I will formulate something, which I use excessively in problem solving !. But first lets solve an example. This question is taken from My quant problem set III, the link of which can be found,” free material for cat”.

Example 4.1 Let a,b,c,d be distinct prime numbers satisfying :

2a+3b+5c+7d=162

11a+7b+5c+4d=162

Given that abcd=k. Find the number of distinct values of k?

A)  0                   B) 1                  C)  2                   D) 3                 e) 4

How we go about this? We were told in school, that n variables need n equations, but we have n-2 here. A road-block? No, a call to think deeply. Just see how we can reduce variables or increase equations🙂 .

We subtract the two equations and get 9a+4b=3d => 4b=3(d-3a)

RHS is divisible by 3, so should be LHS and therefore b=3

put this in the initial equations, and we are sure the max value of a can be =7 ( i leave it to u to figure out how, a hint: all prime numbers are distinct, and we have used 3, we are left with the two smallest as 2 and 5🙂 ).

Back again 3a=d-4=>d=3a+4 gives us (a,d)=(5,19),(11,37)..  but clealry the second set wont work, very large values. We found the set, just by using the constraint, all are distinct primes and 3 has been used.

so we have b=3,a=5 d=19, there is no further need to go as we need the no of values of k which will obviously be 1. But for the sake of completeness we can check c=2🙂

Seems like a marathon, but no its a 3-4 minute problem, once you start doing what I want you to !

Now, if you have understood this concept, you should be able to get the practice problem, which is taken from one of the simcats.

Practice Problem 4.1 A boy spends Rs. 81 in buying some pens and pencils. If a pen costs Rs.7 and a pencil Rs 3, What is the ratio of pens to pencils when the maximum number of pens are purchased such that no extra money is given to the shopkeeper?

A) 3:2    B) 2:1   C) 5:4   D) 7:2   E) none of these1

The next concept which I am going to take up is Prime squares:)

Theorem 4.2 : All prime squares ( p>3) are of the form 6k+1, i.e , p^2=6k+1, for all primes p>3.

Lets try to prove this,  any three numbers  (p-1)p(p+1) will be divisible by 6. but as p is a prime greater than 3, it would neither be divisible by 2 nor 3, hence p^2-1=6k so p^2=6k+1.

Some purists will say, that as p is a prime greater than 3, then, p^2-1=24k+1, yupp I agree, but 24k+1 becomes cumbersome to handle sometimes. The proof is simple again, p is odd so both will be divisible by 2 and one by 4. also one of them by 3. hence p^2-1=24k so p^2=24k+1

But, I have always used 6k+1, may be just used to it. You may pick the one that suites you.

Kindly note, this is a necessary condition not a sufficient one, means all prime square will be of form 6k+1, but all no of 6k+1 cant be prime square🙂

Lets handle our next example based on this.

Example 4.2 : Find the number of primes p, such that p^2+3p-1 is also a prime?

A quick check will tell 2 does not satisfy and 3 does.

now we check for higher primes

p^2+3p-1=6k+1+3p-1=3(2k+p) hence divisible by 3, not  a prime

So, only one prime p=3 . We are done here !

More to follow, do tell us how you like this, press the rating button on the left🙂 !

Written by Implex

September 19, 2008 at 2:55 pm

5 Responses

Subscribe to comments with RSS.

  1. what is the answer to the question on prime no.s …pen and pencils…is it 3:2

    Aayush Madhogaria

    October 4, 2008 at 4:26 pm

  2. yupp

    outtimed

    October 4, 2008 at 4:27 pm

  3. Nice solution to abcd problem. Keep up the good work !!

    Gaurav Jain

    September 6, 2009 at 6:22 am

  4. Lucid explanation… kudos!!!!!!!!!

    Bharadwaj

    August 24, 2010 at 12:54 pm

  5. awesome concept bhai.

    ujjawal kumar

    September 25, 2010 at 11:36 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: