Too many people think Math is Dull.
Astounding Math Stories exists to show you
|
|
the kinds of weird things that happen when you do math.
These Astounding Stories also illustrate some important ideas in math,
so this blog also has a Secret Educational Agenda.
Finding factors, or not
4 August 2008
A report of a conversation
Gyr:
There are computer programs that can
tell if an integer is prime or composite (IsItPrime),
and there are programs that can find the divisors of an integer (IntegerFactor). The best IsItPrime
programs run quite a lot faster than the best IntegerFactor programs. Isn’t that Astounding?
Gimblos: That’s not astounding. Why should it be? Hold on… 
…
To tell if a number is composite you have find a proper divisor! How could IsItPrime?
work faster than IntegerFactor?? It has to do IntegerFactor’s
job first!
Gyr:
Well, that’s what’s astounding. IsItPrime?
can run faster than IntegerFactor because we
are able
to tell if an integer is composite without finding a factor.
Gimblos: But that’s The definition
of “composite” says you have to find a
proper divisor to show it is composite.
There can’t be any other way to prove compositeness. You have to show it fits the
definition!
Gyr: But that’s not what the definition says. To
prove a number is composite, you have to show that a proper divisor of the
number exists. You don’t have to find
a proper divisor. Let’s look at an example.
Is 1,537,519 composite?
Gimblos: Well, I want to find a proper divisor. I only have to try primes. Let’s see, it’s not even. 3 doesn’t divide it. 5 doesn’t divide it. 7 doesn’t divide it. [Time passes.] 521 doesn’t divide it… I’m tired of this. I bet 1,537,519 is a prime number.
Gyr: No, you don’t know that yet. (Note 2.)
There might be a prime bigger than 521 that divides 1,537,519. But there are other ways to tell if a number is composite. Fermat’s Little Theorem
says that if p is a prime, then
for any integer a. (If you don’t know about mod, this means that p must divide
). For example, 17 is prime, and
, and
. You can check that
,
, and so on, are all divisible by 17.
Gimblos: Well, so what?
Gyr: Well, calculate
it turns out that
. (You can do this with Mathematica). If 1,537,519 were a prime,
would have to be congruent to 2 (mod
1,537,519). It is not (see contrapositive),
so
(TA-DA) 1,537,519 is composite (END TA-DA)
and notice that this test gives us NO IDEA what the proper factors of 1,537,519 are.
Gimblos: But, but, You claim to show that 1,537,519
has a proper divisor without finding it.
Gyr: You know the maxim: Life is not fair. Well, Mathematics is even more
unfair. Mathematics is even downright MEAN.
Gimblos: Well, this is terribly upsetting. It completely violates common sense to be able to prove a number exists without saying what it is. ( Note 3.)
Gyr:
Even so, most mathematicians are completely blasé about this and are happy
to prove that things exist without being able to tell what they are. They may not like that happening and
sometimes try hard to construct whatever it is (in our case constructing a
proper factor of 1,537,519) but if they don’t succeed they still know the thing
exists.
Gimblos: Hey, wait a minute. Why couldn’t you analyze the proof of Fermat’s Little Theorem to see if it produces a proper divisor. Maybe it gives you some way to home in on it.
Gyr: Well, the proof isn’t hard if you know a
little modular arithmetic
and group theory.
There are p
1 nonzero remainders of a prime, and they form
a group on multiplication.
By Lagrange’s
Theorem, then, if a is a nonzero remainder of p, then
, which means
. If a = 0 then of course
. No one knows a fast way to use those facts (or
any others) to tell you the factors of a number anywhere near as fast as you
can tell it is prime. (Note 4).
Note 1
A positive integer n is composite by definition if there is an integer k satisfying
¨ 1 < k < n
¨ k divides n.
In this case, the number k is called a proper divisor or factor of n. For example, 3 is a proper divisor of 15, so 15 is composite. But 13 is not composite because none of the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 divide 13.
A positive integer bigger than 1 that is not composite is a prime. So 13 is a prime.
Suppose you wanted to prove that some large number n is composite. One way to do this would be to find a proper
divisor of n. For example, ,
so 37 and 43 are proper divisors of 1591, so 1591 is composite. Note that 37 and 43 are both primes, so if
you started dividing 2 in 1591, 3 into 1591, 5 into 1591, 7 into 1591, 11 into
1591, and so on, it would take you a little while to get to 37, which is the
smallest proper divisor of 1591.
Fermat’s Little Theorem gives another way to show 1591 is
composite: ,
but if 1591 were prime, we would necessarily have
.
Return
Note 2
To test the primality of a number by trying one divisor after another you have to try primes up to the square root of a number. In this case, Gimblos would have to try primes less than 1239. See primality testing in Wikipedia.
Note 3
Gimblos is in good company. Leopold Kronecker was a top nineteenth century mathematician and he had a hissy fit when other mathematicians started doing that. But most modern mathematicians are happy to prove something exists without knowing what it is, but they would rather find a way of calculating it, and sometimes with a lot more work they do find a way.
For example, Hilbert proved his finite basis theorem in 1888, upsetting Kronecker and a bunch of others. But most mathematicians accepted the proof (even Kronecker eventually). A way to calculate the finite basis had to wait till Buchberger showed how to do it (Gröbner basis theorem) in 1965.
Note 4
If there were a method for finding factors that was as fast as known methods for testing primality, the widely used RSA algorithm would become vulnerable. This was the subject of the movie Sneakers.
If you want to learn more: