News and current assignment

Have a happy holiday season!

Abstract

An introduction to elementary number theory

Number theory is one of the oldest and most accessible branches of mathematics. It deals with interesting properties of the integers, and generalizations. Long studied for its intrinsic interest, the field has helped to propel other branches of mathematics such as algebra and analysis. Some computational problems in number theory have been so difficult that efforts to solve them have had the fortunate effect of advancing the field of computer science. In addition, number theory plays a central role in the modern field of cryptography.

In this course we will learn many of the basic tools in number theory, including divisibility, congruences, number-theoretic functions, and more. The course will have both theoretical and computational aspects. In particular, the x-periods 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
Lectures: Monday-Wednesday-Friday 11:15 am--12:20 pm (11 hour)
X-hour: Tuesday 12:00 pm - 12:50pm

We will meet regular classes and the x-hours.

Staff

Instructor:

Carl Pomerance -- 339 Kemeny
Office hours: Tuesday and Thursday 9:00 AM--9:55 AM and by arrangement at other times.

Co-Instructor:

Nathan McNew -- 243 Kemeny
Office hours: Wednesday and Friday 2:00 PM--2:55 PM and by arrangement at other times.

Textbook

Homework

Homework is due at the start of the class period on the due date.
Homework will be generally due once per week on Mondays.
Assignments will be posted on this website, with extra problems and/or comments sometimes added as the week progresses.

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.

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,n-2] 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 base-2 pseudoprimes. To test your function try running: time fermat(2^199-1) 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).
We then used it to prove some numbers are irrational.
(1) Use the rational root criterion to address Ex. 2.4 in the book.
(2) Use the rational root criterion to decide if 2^(1/2)+3^(1/3) is rational.
(3) Do Exercises 2.6, 2.9, and 2.10 in the book. (For 2.9, assume that m>0.)

Homework due Monday, Oct. 6:
(1) If m, n are positive integers and m|n, show that a ≡ b (mod n) implies that a ≡ b (mod m), but not necessarily conversely.
(2) Work out by hand what the remainder is when 2^90 is divided by 91.
(You should use the repeated squaring algorithm discussed in class, so that this problem should be a lot less painful than it might first appear.)
(3) Do the same for 3^90.
(4) Write addition and multiplication tables for least non-negative residues mod 4 and mod 5.
(There's no reason to write brackets around each entry.)
(5) Suppose m, n are positive coprime integers and u, v are integers with um+vn=1.
For any integers a, b prove that both x ≡ a (mod m) and x ≡ b (mod n) if and only if x ≡ avn+bum (mod mn).

Homework due Monday, October 13:
(1) Find the multiplicative inverse of 10 modulo 23.
(2) Describe the set of integers x with
x²-1 ≡ 0 (mod 77). (Use the Chinese Remainder Theorem.)
(3) If p is a prime, a is an integer, and m, n are positive integers with m ≡ n (mod p-1),
show that a^m ≡ aⁿ (mod p).
(4) If a is an integer not divisible by the odd prime p, show that
a^(p-1)/2 ≡ ±1 (mod p).

Homework due Wednesday, October 22:
(1) In class we saw a proof that (4^p-1)/3 is a base-2 pseudoprime if p is a prime with p>3. Generalize this as follows: Let a be an integer at least 2 and let p be a prime that does not divide a(a²-1). Show that n=(a^2p-1)/(a²-1) is a base-a pseudoprime.
(2) Using the formula developed in class on Monday, Oct. 20, compute φ(999), φ(1000), and φ(1001).

Homework due Monday, October 27:
(1) Show that if n > 2, then φ(n) is even.
(2) Show that if gcd(a,210)=1, then a¹²≡1 (mod 210).
(3) Show that if n is squarefree and m≡1 (mod φ(n)), then a^m≡a (mod n).
(Hint: Consider the congruence separately for each prime p|n.)
(4) Let d₁,d₂,...,d_k be all of the positive divisors of the positive integer n.
Show that φ(d₁)+φ(d₂)+...+φ(d_k)=n.
(Hint: Take the fractions 1/n, 2/n, ..., n/n and reduce them all to lowest terms. How many end up with denominator d?)

Homework due Monday, November 3:
See this.

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.
The final exam will be comprehensive for the term.

Grading

Grades will be based on homework and exams:
10% - Computer exercises
20% - Written homework
30% - Midterm exam
40% - Final exam.

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 6-2014 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.