I would like to know what is the correct way to approach the problem?
Try using miller rabin primality test.
As ani94 pointed it out, Miller Rabin Primality Test is the go about for such problems. But before reading and understanding it, I think it would be better if you read about Fermat’s little theorem, and the “issues” with it. Meanwhile, the following text, and links should be helpful! Take a look.
"Suppose p was prime, and y was a non-trivial square root of 1 mod p.
Then we must have that y2=1modp and so (y−1)(y+1)=0modp. This implies that either y=1modp or y=−1modp, which implies that y is a trivial square root.
Thus, if there is a non-trivial square root of 1 mod p, then p has to be composite.
For an example of a non trivial square root of a composite, consider p=15. We have that 42=16=1mod15. Thus 15 is composite.
Note that the witness in the primality test is not necessarily a non-trivial square root of 1 mod p.
The fact about non-trivial square roots can be used to prove that if p is prime, then for any a relatively prime to p, some power of a from a given set of powers (the powers are based on the even factors of p−1) must be −1 or a specific odd power of a (again based on factor of p−1) must be 1.
If for some a none of the above set of powers is −1 and the specific odd power is not 1, then it must be the fact that p is composite.
It can also be shown that for composite p, the chances of finding such a is atleast 3/4. This a is the witness in the primality test and is not necessarily a non-trivial square root of 1 mod p.
The squaring that is done is to get the powers described above which are based on the factors of p−1.
The wiki page has really got a lot of good information (including the exact powers of a that need to be taken)" - http://math.stackexchange.com/questions/4597/simple-explanation-and-examples-of-the-miller-rabin-primality-test
Also, you may try reading this: https://docs.google.com/viewer?a=v&q=cache:pcBEzTliZ2kJ:www.math.uic.edu/~marker/math435/rm.pdf+&hl=en&gl=in&pid=bl&srcid=ADGEESho0Ovr4aYe6TJNjR1-s2a8fLfjNRI7RuxirPPoHXb1izcO9_l4ebEil72XeVuYr92VVENF2M19BLfD9PAGaLPPf4T0tTCTHhf_j48ER5KaRIFtqGtFQ1M7DR0wkxGsTg58F_9y&sig=AHIEtbR4HXXFeTni3O8saLip-a2xSA2X3A