Information about Project 1
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?
Information about Project 2
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...