High school level question. Student asking.

To whom it may concern,

I have a bit of a math problem. It has to do with determining if a very large number is a prime. One method entails dividing the number by every smaller prime number. If any divide into it, it's not a prime. This would be a big job if the number was something like 400 digits long. Another way I read about was to take the square root of the number and test all the primes less than its square root. The explanation went like this: "When a number is divided by another number that is greater than its square root, the result is a number smaller than the square root. For example, the square root of 36 is 6. Dividing 36 by 2, a smaller number than 6, gives 18, a number that is larger than the square root. To prove that 37 is prime it is only necessary to divide it by primes less than 6, since if it had a prime factor greater than 6, it would have to have one less than 6 as well."

I understand the explanation, up to the last sentence. I fail to see the underlying logic. Why if a prime factor exists below the square does one have to exist above the square too? The number 40 can be divided by the prime 2, a number below its square root, but no other primes can do this above itsÊsquare root. Have I missed something? What's the logic here?

If you have any ideas, please let me know. Thanks,
Paul

The confusion you have is a common one. You have misread the last statement in the quote. It says

The logic is this.

A composite number can have very large prime factors; for instance the number 458759 has the prime number 65537 as a factor. But it is not the first one that you stumble upon when you try to divide 458759 by 2, then 3, then 5, ... you first find out that 458759 is divisible by 7. Then, dividing 458759 by 7, you get 65537, so that 458759 = 7*65537.

Now, to continue your factorisation (that is, find the other prime factors of 458759), you continue with trial division, but you do not need to divide 458759 by successive primes; just your quotient 65537. So you try dividing 65537 by 7 (no need to go lower than where you were), then 11, then 13, ... If you are very brave or stubborn, you can try to divide 65537 by all the primes up to 256, but all will leave a remainder. (Actually, the last prime before 256 is 251; which is not obvious at first sight. There are tables of primes up to the millions.) Now the next prime after 251 is 257, but this is already too large: If 65537 were divisible by some prime p at least 257, then the quotient 65537/p would also have to be at least 257, since no smaller numbers divide 65537. But multiplying two numbers larger than or equal to 257 will give an answer of at least 257*257 = 66049 so you cannot get 65537. This means that your quest for factors, both larger or smaller than 256, has indeed ended, and you can conclude that 65537 is prime.

Actually, 65537 = 2²⁴ + 1 is the fourth Fermat number. the smaller ones are 2²³ + 1 = 257, 2²² + 1 = 17, 2²¹ + 1 = 5 and 2²⁰ + 1 = 3. These are all prime. So this may lead someone to believe that the larger Fermat numbers should be prime as well. The next one on the list is 2²⁵ + 1 = 4294967297.

It would take a very long time to try to divide this number by all the primes up to the square root of 4294967297 (which is about 65536. For many years, nobody would dare to try it. Eventually, somebody found out that it was not necessary to try all the primes; only those that are one more than some multiple of 2^7 = 128. This restricted the choices: The first possible candidate is 128 + 1 = 129 which is not prime, so you can skip it. The next choice is 2*128 + 1 = 257 which is prime. So, you need to try to divide 4294967297 by 257; it takes a long time and you get a remainder of 1, so 257 is not a factor of 4294967297. The next candidate on the list is 3*128 + 1 = 385 which is not prime, so you can skip it. The next candidate is 4*128 + 1 = 513 which is not prime, so you can skip it. The candidate after that is 5*128 + 1 = 641 which is prime. The division of 4294967297 by 257 again takes time, but now you get 6700417 with a remainder of 0! So it turns out that 2²⁵ = 4294967297 is not prime after all, because it can be divided by 641.

The method called "modular arithmetic" allowed to restrict the factors to the list 129, 257, 385, 513, 641, and so on. It has gone a long way since. Nowadays, it is possible to determine that some really big numbers such as 2^(2^14) + 1 (with more than 5000 digits) are not prime, without using trial division, and without finding any prime factor of the number. There are websites on the factoring of Fermat numbers and other families of large numbers that you can access through the site http://search.netscape.com/Science/Math/Number_Theory/Divisibility/Tables