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
A conversation recorded by the Six Winged Seraph, a certified member of the Society of Recording Angels
Revised 18 December 2008
Gyr:
There are computer programs that can
tell if an integer is prime
or composite (PrimeQ in Mathematica), and there are programs that can
find the divisors of an integer (IntegerFactor). The best PrimeQ
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 PrimeQ
work faster than IntegerFactor?? It has to do IntegerFactor’s
job first!
Gyr:
Well, that’s what’s astounding. PrimeQ
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 a number is composite.
There can’t be any other way to prove compositeness. You have to show the number 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. (See Note 3).
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 4.)
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… Like, the proof that a cubic has to have a real root works because a cubic goes off to negative infinity one way and positive infinity the other way, so it has to cross the x axis. So you find a point where the curve is positive and another where it is negative and use bisection!
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 5).
Notes
added by the Six Winged Seraph
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
.
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
You can’t always show a large number
is not prime by trying 2 it can happen that for some composite numbers n,
for lots of numbers a
or even for all numbers a -- so fast primality tests have to use
use generalizations of Fermat’s Little Theorem and other deeper theorems in
number theory. See Carmichael numbers.
Note 4
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, which showed that a certain kind of ring has a finite basis without showing how to find it. This upset 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.
Finding a finite basis for an infinite ring requires checking an infinite number of possibilities, but finding a proper factor for an integer requires checking a possibly horribly large but finite number of possibilities. The methods we have for primality testing, based on properties such as Fermat’s Little Theorem, cuts down the number of things you have to try a whole lot. But the Gröbner basis theorem cuts it down from an infinite number of things to a finite number of things! So the Gröbner basis theorem is really considerably more astonishing than the speedup given by fast primality testing.
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:
If you like Astounding Math Stories, you might like abstractmath.org.