Posted in Maths

Math: Why we check only till the square root of number to prove it’s prime

Now everybody knows what factors and divisibility means so I am not going to post about them rather, I would like to post an interesting property (I also used it in a previous post to check for prime via c++)  :

“If a number, say N, is not divisible by any number between 2 and K (inclusive), then it cannot be divisible by any number greater than ⌊N/K⌋.”

⌊⌋ stands for the greatest integer function and N,K are natural numbers.

Most of the people out there won’t be ready to accept it right away, so here is a complete explanations :

Let N be the given number and K be the number till which we have already checked the divisibility with N and haven’t found a divisor yet. Let us further assume on the contrary that a divisor greater than ⌊N/K⌋ be A (if possible). Then :

N/A must be a natural number which should also be a divisor of N. Further we know that :

N/K < A   ⇒    N/A < K

That is a divisor of N exists which is less than K. But we just have checked that no such number exists. Thus something is wrong with our assumption and hence the statement must be true.

Now consider an example. Let the number be 2021.

I have checked that no divisor of this number exists from 2 to 41 (because I don’t know tables any further and am too lazy to calculate). So I use the above statement and find that 2021/41 is around 50 (greatest integer).  So I now know that I must work a little more to find a factor if it exists and when I divide 2021 by 43, I now have one factor in my possession and can find all others now revealing that 2021 is actually 43 X 47.

This was a naive implementation but yes if we talk in terms of coding, it can definitely be useful for optimizing the conventional method of looking from 1 to n-1 searching every number for a divisor and even give the logic where in some books we check from 2 to n/2.

Now a real time application. Let’s see some further implications of this statement :

Let us assume that the smallest divisor of N, if exists be X. then the corresponding pair will be N/X and it’s easy to see that X times N/X is N.

As X is the smallest divisor, N/X has to be the greatest divisor.

So,

X  ≤ N/X

⇒X² ≤ N

⇒|X| ≤ √N

⇒−√N ≤ X ≤ √N

⇒1≤ X ≤ √N                                                (As X is a natural number)

All equality’s hold only when N is a perfect square.

Therefore the direct implication of the given statement is that in order to find factors of a number we only need to search till it’s square root. If we can’t find any then the number must be prime.

 

Advertisements

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