Since, it is my first post, I’ll keep it about my most favourite subject – Mathematics. This blog is about how we can use prime numbers to check if a given number is prime or not.
I was going through an old book I had acquired to learn Math after 12th (Guess who forgot about it after 12th though. Correct, 10 points to your house!). This book is called ‘Challenge and Thrill of Pre-college Mathematics’ and is written by four mathemticians.
There I learnt that “A positive integer n is a prime if GCD(n,p)=1 for every prime integer p<=n1/2“. So, basically what they were telling me is that, if I have number say 23, all I have to do is check the GCD of primes that were lesser than square root of 23. So, root of 23 is lies between 4 and 5. Primes lesser than 5 are 2 and 3. GCD(23,2)=1 and GCD(23,3)=1. Hence, I can say that 23 is a prime number already.
Why do I think this is amazing?
- Can you imagine the amount of time I’ll save while wondering if a number is prime or not?
- It’s something that seems trivial, something that feels natural yet something we rarely learn about.
- I just love that its a weird proof for a weird fact that has such rare use in our daily life. (Go figure)
Now, it has a proof –
Let n be the positive integer, rn be the roof n and p be the prime lesser than rn.
Let GCD(n,p)=1, for all p<rn. Suppose, n is not a prime, then there exists positive integers, say a and b, such that p=a*b, 1<a<b<p. Hence a<rn. Now, we know that every positive integer can be factorised into prime numbers. So there exits a p<a that divides a, and hence should also divide n as p<a<rn; but this is against our first assumption, thus we can say that n is a prime positive integer.
Now, you’ll surely be wondering where will I ever use this. If you’re a mathematician or if you are somebody who likes math – I wish you didnt ask me this question but anyway, use it the next time you want to make numerical sums easy. If you aren not somebody who likes Math, make this your next road trip game, check if the vehicle numbers are prime or not, fastest one gets a point.