CAT Preparation: Prime Numbers

by Suresh

One of those very important topics for every entrance exam and at the same time a bit nebulous topic too

Theorem 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 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 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 these

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

Theorem 2 : All prime squares ( p>3) are of the form 6k+1, i.e , 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 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 2 : Find the number of primes p, such that 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!