# MAT 311 Number Theory

Project 1 should be handed in by 03/04. Please select one of the topics or one of the programming projects listed below. You need to make your selection and also inform me of it by 2/19.

• A proof that the rational and algebraic numbers are countable and that the irrationals and transcendental numbers are not.
• A short (2 to 4 typed pages) biography of a prominent number theorist.
• Write a program to implement the 3n+1 algorithm' in exercise 5.6 (see also exercise 5.5). The user will input n and your program should return the length and the terminating value of the 3n+1 algorithm. Use your program to find the length and terminating value for all starting values 1.
• Write a program to find a solution (x,y) in integers to the equation ax+by=gcd(a,b). Write also a version of the program so that if a and b are positive, then the returned solution always has x>0.
• Write a program that finds all twin primes less than 20,000. Hardy and Littlewood conjectured that the number of twin primes not exceeding n is asymptotic to C n/(ln n)2 for a constant C, approximately equal to 0.66016. Determine how accurate this asymptotic formula is for values of n as large as you can compute.
• Exercise 11.6
• Compare the number of primes of the form 4n+1 and the number of primes of the form 4n+3 for a range of values of n. Can you make any conjectures about the relationship between these numbers?
• Write a program to find the number of zeroes at the end of the decimal expansion of n!.
• Write a program to find the prime factorization of n!.
• Show that if n is a Carmichael number then it is squarefree.
• Show that if n=p1p2...pn is a product of distinct primes such that pi-1|n-1 for all i, then n is a Carmichael number. Use this to show that 564651361 is a Carmichael number. Can you write a program to find other Carmichael numbers?

Project 2 should be handed in by 04/30. Please select one of the topics or one of the programming projects listed below. You need to make your selection and also inform me of it by 04/23.

• Write a program finding the primes p smaller than a given number n for which 2p-1 is congruent to 1 modulo p2.
• Find as many Charmichael numbers of the form (6m+1)(12m+1)(18m+1) as you can.
• Show that there are infinitely many psudoprimes to any base m.
• Lehmer has conjectured that n is prime if φ(n) divides n-1. Gather evidence for this conjecture, or find a counterexample if you can.
• Charmichael has conjectured that for every positive integer n there is a positive integer m distinct from n such that φ(n)= φ(m). Gather evidence for this conjecture.
• An integer n is called highly composite if τ(n)= τ(m) for all integers m<n. Find all highly composite numbers not exceeding 10,000.
• Exercises 20.10 and 20.11.
• Write a program encrypting and decrypting messages using the Caesar cipher.
• Write a program to decrypt messages which have been encrypted using Vigenere ciphers.
• The El Gamal Cryptosystem (Exercises 21.6, 21.7). Write a program to encrypt/decrypt messages using the El Gamal Cryptosystem. Show that if the same random number r is used to encrypt two plaintext messages P and Q using the El Gamal Cryptosystem, then Q can be found once the plaintext message P is known.
• Exercise 22.2
• Show that if p is a prime of the form 4k+3 and q=2p+1 is prime, then q divides the Mersenne number Mp=2p-1. (Hint: use Legendre symbols).
• A short (3 to 4 typed pages) paper on the mathematical contributions of a number theorist. Note: This is not a biography - you will need to describe mathematical results, their proofs, etc.
For any of the programming projects, please email me at sorin@math.sunysb.edu the program source code (in readable form -- indented and commented), and hand in the program outline and a reasonable amount of program output. You can use any programming language you like (within reasonable limits - i.e., a language for which there exist easily available compilers). Preferred ones are Maple, Mathematica (yes, they are programming languages), C, OCAML and Java, but you can also use C++, Pascal, Python, Fortran, Lisp, Turing machine...