# Divisibility Tests and Factoring

• There are simple tests for divisibility by small numbers such as 2, 3, 5, 7, and 9. These tests involve performing operations on the decimal representation of the number to be tested for divisibility.
• Fermat factorization attempts to factor a number by representing it as the difference of two squares.
• The Fermat numbers are numbers of the form .

First, I'll discuss quick ways for deciding whether a number is divisible by various small integers. In what follows, I'll assume that numbers are represented as strings of decimal digits (i.e. in base 10) as usual.

Proposition. (a) An integer is divisible by 2 if and only if its last digit is divisible by 2.

(b) An integer is divisible by 5 if and only if its last digit is 0 or 5.

Proof. The proofs for these two tests are nearly identical; I'll do the one for divisibility by 2 as an example.

Suppose the decimal representation of x is

That is, is the units digit, is the tens digit, and so on. For 1728,

Then

Since , it follows that for . Thus, if and only if --- that is, x is even if and only if the units digit is even.

Definition. The digital sum of an integer n is the sum of the digits in the decimal representation of n.

Example. The digital sum of 1728 is 18:

The digital sum of 278349 is 33:

Proposition. (a) An integer is divisible by 3 if and only if its digital sum is divisible by 3.

(b) An integer is divisible by 9 if and only if its digital sum is divisible by 9.

Proof. I'll prove the test for divisibility by 9 as an example. Suppose the decimal representation of x is

Then

The sum of the digits of x is

Observe that

The right side is divisible by 9, because

That is,

Hence, if , then , and if , then .

Note that you can continue to sum the digits of the numbers that you get until you get something that is obviously divisible by 3 or 9. For example, start with 893948083:

Since 7 is not divisible by 3 or by 9, neither is 52. Since 52 is not divisible by 3 or by 9, neither is 893948083.

The next result can be proved by a method similar to that used to prove the test for divisibility by 9. Since the proof is a little more complicated, I'll merely state the result and give an example.

Proposition. To test divisibility by 7, remove the last (units) digit, double it, and subtract it from the remainder of the number. The original number is divisible by 7 if and only if the result is divisible by 7.

Example. 9423242 is divisible by 2 and by 9. Here's how the divisibility by 7 test looks for this number:

86 is not divisible by 7, so 9423242 is not divisible by 7.

It is difficult to factor a large, arbitrary integer in a reasonable amount of time. You can use simple divisibility tests like those above to deal with "obvious" cases, but the general problem is the object of current research. Here's a useful idea which is called Fermat factorization.

Proposition. Let n be an odd integer. There is a one-to-one correspondence

Proof. If , n is odd so a and b are odd. Then and are even, so and are integers. Now

expresses n as a difference of two squares.

Conversely, suppose n is written as as difference of squares: . Then

is a factorization of n.

You can check that these two procedures --- factors to difference and difference to factors --- "undo" one another.

Example. Use Fermat factorization to factor 4819.

The idea is to try to write 4819 as . I will form and increase s till I get a perfect square. What s's do I need to use?

First, . Since , s must be at least as big as .

On the other hand, the factorization with the biggest factor is . By the proof of the last result, this would produce an s of the form . So I need to try s for .

On the very first try,

Thus, and . , , and .

Example. Use Fermat factorization to factor 779.

, so I need . , so .

The factors are and : .

The Fermat numbers are numbers of the form

Fermat thought that all the were prime. However, it turns out that . Note that

Therefore,

On the other hand, , so

This proves that .

Here are some properties of the Fermat numbers.

Proposition. If p is prime and , then for some k.

I won't prove this result, since the proof requires some stuff about quadratic residues which I won't discuss for a while. Here's how it can be used.

Example. . Here , so all prime divisors must have the form . There are around 1024 numbers less than 65537 of this form, but I only need to check numbers up to the square root . (For if a number has a prime factor, it must have a prime factor less than its square root.)

(The next value of is 257, which is larger than .) Conclusion: 65537 must be prime!

Proposition. for .

Proof. and , so . The result is true for .

Take , and assume the result is true for n; I'll try to prove it for . By assumption,

Now

That is,

This is the statement for , so the proof is complete, by induction.

Proposition. If , .

Proof. Assume (if not, switch m and n). Suppose p is prime and and . Also, since implies that occurs in this product. But

Since p divides both of the terms on the right, , so . This is impossible, since all the 's are odd.

Therefore, there is no prime dividing both and , and hence .

Contact information