|
Numbers form the basis of much of the mathematics we study in school,
yet there are many unanswered questions about them. The most famous
of these, on the validity of Fermat's Last Theorem, was finally
answered only in the last decade after resisting three centuries of
challenges from mathematicians. Many of these problems, and their
solutions, are accessible to anyone who knows basic algebra.
This class will begin with straightforward algebra and progress to
more difficult and more interesting problems. One problem is
factoring: much of the security of the internet is based on the
presumption that this is difficult. For example, RSA, whose encryption algorithm
we will study, has cash prizes
for factoring large numbers that are the product of two primes. (A
whole number p>1 is prime if it is divisible only by
1 and itself.) A related problem is finding larger and larger
prime numbers. (There are also
prizes
for computing sufficiently large primes.) For example,
it is currently unknown whether or not the 32nd Fermat number
F32=2232+1
is prime.
Our approach is motivated by mathematics research. We will search for
patterns in hands-on examples and discover (and prove) rules based on
these patterns. The topic of number theory allows us to ground our
abstract results in terms of straightforward examples; that is, our
mathematically rigorous results will come from experimenting with
shapes via problem-solving, games, and computer programs.
This is the plot of the function y=pi(x), which gives the
number of prime numbers less than or equal to the number
x. This explains its jagged appearance -- the graph
"jumps" at each prime number. Two questions to think about:
first, what does this graph look like as x grows? Second,
if we start at a number x, how much must we increase
x to increase pi(x)? For example, pi(199) =
46 and pi(210)=46 as well. Thus pi was 46 for
all x from 199 to 210. (Since 211 is
prime, pi(211)=47.)
7,182,391
= 2677 × 2683
10,620,951,283
= 103049 × 103067
These were constructed to be easier to factor than similar products
of two prime numbers. How? These are products of nearby primes,
so there is a clever algorithm (due to Fermat) to find the factors.
|
|
|
|
|
|
|
|
|