Math 25
An introduction to elementary number theory
Instructor: Carl Pomerance (carl.pomerance at dartmouth.edu)
CoInstructor: Nathan McNew (nathan.mcnew at dartmouth.edu)
Abstract  Classes  Tutorials  Staff  Textbook  Grading  News and current assignment  Past assignments  Exams  Honor Code
News and current assignment 
Have a happy holiday season!
 
Abstract 
An introduction to elementary number theory In this course we will learn many of the basic tools in number theory, including divisibility, congruences, numbertheoretic functions, and more. The course will have both theoretical and computational aspects. In particular, the xperiods will be met regularly, and computational exercises will be featured in them. Prerequisites: Calculus. Grading: There will be weekly written assignments, a midterm, and a final exam. In addition, there will be weekly computational assignments.  
Classes 
Room: 006 Kemeny We will meet regular classes and the xhours.  
Staff 


Textbook 
Elementary number theory, by Gareth A. Jones and J. Mary Jones  
Homework 
Homework is due at the start
of the class period on the due date.


Past assignments 
First computational work: By Friday Sept. 19 write sage functions wgcd(a,b) and rgcd(a,b) to implement Euclid's algorithm using a while loop and recursion respectively. Second computational work: By Friday Sept. 26th write a sage function checkprime(n) which uses trial division to check if n is prime and a function listprimes(m) which uses checkprime(n) to list the primes less than or equal to m. Third computational work: By Friday Oct. 3 write a sage function sieve(n) which uses the sieve of Eratosthenes to list the primes less than or equal to n. Submit by clicking on share, typing in m25f14 and clicking submit. Fourth computational homework due by Monday October 20th: Write functions binary(b) and squaresmod(a,m,l), which return lists containing the digits of b in binary, and the first l repeated squares of a (mod m) respectively. Use them to write a function powmod(a,b,m) which (quickly) computes a^b (mod m). To test your function try running: time powmod(17,987654321,107) It should return 88 and take less than a second.Fifth computational homework due by Friday October 24th: Write two functions fermat(n) and twopsp(m). fermat(n) should pick 20 random bases from [2,n2] and use them to run a Fermat primality test, returning "Composite" if one fails, and "Probably prime" if it passes all of them. twopsp(m) should return all composite numbers up to m which are base2 pseudoprimes. To test your function try running: time fermat(2^1991) It should return Composite and take less than a second. Computational homework due by Friday October 31st: Implement RSA. Write a function createkey(n) which generates 2 primes, p and q, with size around n and prints N=p*q as well as the exponent, c, and its multiplicative inverse, d, mod φ(n), the secret key. Write also two functions Encrypt(N,c,m) and Decrypt(N,d,e) to encrypt and decrypt a message M using the public and private keys. Computational homework due by Friday November 7th: Write functions isprimroot(a,p) and leastprimroot(p) to test if a is a primitive root modulo a prime p, and to find the least primitive root modulo p respectively. Use them to investigate the questions: Is the least primitive root modulo a prime always itself a prime number? Is the least primitive root modulo a prime p also a primitive root modulo p^2? Computational homework due by Friday November 14th: Write a function s(n) which returns the sum of the proper divisors of n. Write a function cycle(n) which lists all the perfect and amicable numbers less than n. Also write a function aliquot(n) which returns the aliquot sequence starting at n until it cycles, reaches 1 or gets too large. Investigate the sequences starting at n less than 250 as well as the special cases n=276 and n=2856. Homework due Monday, Sept. 22, at the start of class: In Chapter 1 of the text, exercises 1.2, 1.3, 1.7, and 1.8. Homework due Monday, Sept. 29:
We learned in class the "rational root criterion": If f(x) is a polynomial with integer coefficients
and a/b is a root, where a/b is a reduced fraction, then a divides the constant term of f(x) and
b divides the leading coefficient of f(x). Homework due Monday, Oct. 6: Homework due Monday, October 13: Homework due Wednesday, October 22:
Homework due Monday, October 27: Homework due Monday, November 3: Homework due Monday, Nov. 10: See this. Homework due Friday, November 14: See this. 

Exams 
There will be a midterm and a final exam. Here is the midterm examination held in class on Friday, October 17. The final examination will be held on Friday, November 21 at 8:00 AM
(till 11:00 AM), in 008 Kemeny, two rooms down from our classroom.  
Grading 
Grades will be based on homework and exams: 

Honor Code 
Collaboration on homework is definitely allowed and even encouraged. However, it is tempting to think that you understand something that was figured out by your friend. When you hand in a solution, you should know it well enough that you could explain it to others. Please name others you worked with when handing in homework papers. Merely copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code, even if attribution is made. You should understand what you turn in. 

Disabilities 
I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate. The Student Disabilities Coordinator, Nancy Pompian, can be reached at 62014 if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion. 