This Saturday’s (9/27) Math Circle lecture by Dr. Bennett Harris on “Computer Data Encryption – Decrypted” promises to be a great combination of number theory and applied math. To warm up the students, Dr. Harris forwarded some problems that I will post in two parts. Feel free to offer solutions in the comments or to just work them on your own. Full solutions will be made available at the next Math Circle.
Problems
A solution for each of the following should either give the correct answer, or a technique for determining the answer in reasonable time with the assistance of a calculator.
1. How many prime numbers are there? Prove your answer.
2. What is the largest number you must test to demonstrate that 83 is prime?
3. What is the smallest 5-digit prime? How could you find this number?
4. Is 1234567890 prime? What about 123456789?
5. Assume an alphabet with 26 letters (plus a blank space). A substitution cipher is a one-to-one mapping of this alphabet onto itself. How many such substitution ciphers are there?
Metroplex Math Circle 
1. I have a proof that there are infinitely many prime numbers.
OK, suppose that some number N is the last prime number, that there are no prime numbers larger than it. Now suppose that some number M=(2*3*5*7*…*N)+1
Therefore, M is bigger than all primes. However, I claim that M is prime. Lets see if M is divisible by 5. 5 is obviously a factor of 2*3*5…*N, because there is a 5 in there. But wait… M=(2*3*5…*N)+1! And as we all know, 1 greater than a multiple of any number N (N does not equal 1 or -1 isn’t a multiple of N. Therefore, M is a prime number larger than N, thus there are infinetly many prime numbers.
2. 41
3. 10007
I know that all prime numbers past 5 end in either 1,3,7, or 9. I wrote a program to test for prime numbers, and I found that while 10001 and 10003 weren’t prime, 10007 was. My program just tests any number X with 2 and all odd numbers up to sqrt(X).
4. neither is prime, because 1234567890 is even and the digits in 123456789 add up to 45 (which is divisible by 9), so it is divisible by 9 and 3.
5. 25!, which is too big for me to calculate
Sorry, I was wrong about number 2. It should be 9
1. Infinite number (Obvious Answer)
2. 9
3. 10007
It is the smallest since 10006, 10005…are all divisible by some other numbers.
4. Neither is prime. The first is even. The second is divisible by 9 when you add up the digits.
5. 25! Which I can calculate myself by using TI-89