Math 4181: Elementary Number Theory

Information about this course

• Text book: Elementary Number Theory and its applications 5th Edition by Kenneth H. Rosen
• Class times and place: MWF 2:40pm - 3:30pm, Locket 276.
• Office hours: MTWThF: Locket 210. 3:40pm - 4pm, or by appointment.
• Homework: There will be ungraded homework every week.
  Although this is ungraded, it is important to do the homework.
  We will go over the solutions in class.
  Exam questions will be variations on homework problems.
• Tests: (in class time)
  • test 1: Friday, September 18
  • test 2: Friday, October 16
  • test 3: Friday, November 13
• Final Exam: Friday, December 11, 12.30 - 2.30pm
• Computation of final grade:
  • 10% test 1
  • 30% test 2
  • 10% test 3
  • 50% final exam
• Grading scale: 85-100%=A, 70-85%=B, 55-70%=C, 40-55%=D.
• Course web page: http://www.math.lsu.edu/~verrill/teaching/math4181/index.html
  Handouts and notes and useful links will appear on the web page.
• Course outline:
  • Integers (chapter 1)
  • Primes (chapter 3)
  • Congruences (chapter 4)
  • Special congruences (chapter 6)
  • Multiplicative functions (chapter 7)
  • Cryptography (chapter 8)
  • Primative roots and applications (chapter 9 and 10) (as time allows)
  • Diophantine equations (chapter 13) (as time allows)

Class 1

• Overview of course
• Introduction to number theory
• Proof that square root of 2 is irrational
• Proof that the rationals are countatable

Class 2, Wednesday August 26

• Proof that the reals are uncountable
• Another example of counting rationals
• Quick introduction to sequences, in particular geometric and arithmetic
• See Sloanes web site for more sequences
  http://www.research.att.com/~njas/sequences/
• Discussion of rational approximations to Pi
• Discussion of Dirichlet's approximation theorem
• Definitions of greatest integer and fractional part of an integer
• Above all from section 1.1
• Very quick review of sums and products from section 1.2
• Next time we'll prove dirichlet's approximation theorem

Class 3, Friday August 28

• Proof of Dirichlet's approximation theorem
• Recall statment of mathematical induction
• Definition of Fibonacci sequence, and some properties
• exercises:
  Work through the proof of Dirichlet's approximation theorem with alpha=pi and n=10
  pg12-14, ex: 2,8,10,12,18,30,34
  pg 28, ex 32, 34
  pg 29 ex 35,36
  pg 34, ex 14
  pg 35, ex 39

Class 4, Monday August 31

• Went through an example of Dirichlet's approximation theorem
• Worked through exercises:
  pg12: 2,8,10
  pg28:32 (tower of Hanoi)
  Also went through an example of Fibonacci sequences and trains made of wagons of length 1 or 2.

Class 5, Wednesday September 2

• Went through a couple of examples involving integer and fractional part
• Covered section 5.1 on divisors of integers
• exercises: section 1.5, ex: 6,8,10, 26, 28, 30, 36

Class 6, Friday September 4

• Went over solutions to exercises given last time.
• Started chapter 3 on primes and GCD
• Defined primes
• Discussed the seive of Eratosthenes

Class 7, Wednesday September 9

• Finished 3.1: proof there are infinitely many primes.
• Discussion of largest primes and Mersenne primes and perfect numbers
• 3.2: Discussion of pi(x), the number of primes less than or equal to x, and the prime number theorem.
• homework 3.1 ex 7,14,20,23

Class 8, Friday September 11

• Went through suggested excersices from section 3.1
• Greatest common divisors, section 3.3
• Covered everything up to Theorem 3.6, and definition of linear combination of two integers
• homework 3.3, ex 3-15
  homework 3.4, ex 2(d), 4(d), 19,20, 24

Class 9 and 10, Monday September 14, Wednesday September 15

Class 12, Friday September 17

Class 13-15, Monday - Friday September 21 - 25

• Go over extended Euclidean algorithm
• Go over fundamental theorem of arithmetic on unique prime factorization
• Go through homework examples
• homework 3.5: 4d), 10, 14,15,16,18, 19-12,24, 25-28, 32 d), 39-41

Class 16 and 17 Monday and Wednesday September 28 and 30

• went through homework 3.5: 4d), 10, 14,15,16

Class 18 Monday October 5

• 3.6: Fermat Factorization method
• 3.7: Solving linear Diophantine equations
• Chapter 4: congruences. 4.1: definition

Class 19 Wednesday October 7

• Chapter 4: congruences. Basic results about congruences, arithmetic modulo m, and systems of residues
• Suggested homework: 4.1, page 149: 5, 6c), 7d), 8,9,10,14,16,17,19,20,21,22,24,226,28a,b, 38.

Class 20 Friday October 7

• Finished section 4.1, including examples of exponentiation modulo m
• handout giving test 2 guideline

Class 21 Monday October 12

Class 22 Wednesday October 14

Class 23 Friday October 16

Class 24 Monday October 19

• 4.1 and 4.2

Class 25 Wednesday October 21

• Finished 4.2
• 4.3 Chinese remainder theorem
• Start Section 4.4
• We'll probably look at some of the following homeworks on Monday:
• homework 4.2: 2, 3, 6, 16, 18
• homework 4.3: 5, 6, 7, 33, 34, 35

Class 26 Friday October 23

• Started Section 4.4,
• Did example of solving a polynomial mod 8 and mod 25 to get the solution mod 200, using CRT (Chinese remainder theorem)
• Did an example of using a solution mod 5 to find a solution mod 25
• Defined "lifts"
• Got up the immediately before the proof of Hensel's lemma.

Class 27 monday October 26

• Hensel's lemma.

Class 27 Wednesday October 28

• Applications and examples of Hensel's lemma.
• Homework: 4.4 ex 2, 4, 6, 8
• Started going through previous homework

Class 28 Friday October 30

• Went through a selection of the homework exercises
• Started going through previous homeworks, including
• solving linear congruences in one variable
• finding roots of 1 mod powers of 2
• using Hensel's lemma and the chinese remainder theorem to solve a polynomial congruence modulo some composite number.
• Next week we will start on section 4.6.
• The plan is to then cover check digits, 5.5, then go onto chapter 6

Class 29 Monday November 2

• 4.6: Factoring using Pollard rho. homework: 4.6 ex 1, 2, 3
• 5.5: check digits. homework: 5.5 ex 14 - 20
• Handout with list of possible test questions
• On Friday, we may go over some of these, and also give a handout of solutions.

Class 30 Wednesday November 4

• Section 5.5:
• Check digits: ISBN
• Credit card check digits: see wikipedia's explanation of the Luhn algorithm
• Started section 6.1: stated Wilson's theorem

Class 31 Friday November 6

• Handout with solutions to list of possible test questions
• Only one student came to class, so we just had some mathematical discussion and class was essentially cancelled.

Class 32 Monday November 9

• Went over a solution to one of the Pollard Rho questions.
  See here for more solutions.
• Proved Wilson's theorem (section 6.1)
• Proved Fermat's little theorem (section 6.1)
• Started proof of Eulers Theorem (section 6.3)
• Defined the Euler phi function (section 6.3)

• Breifly went over solutions to test guide
• Note that there were a couple of remarks or corrections to be made,
  which are on this handout
• Stated Eulers theorem, gave examples and applications. Proof next week.
• Defined multiplicative functions
• Proved that Euler's phi function is multiplicative

Class 34 Friday November 13

• Test 3 solutions

Class 35 Monday November 16

• Proof of Euler's theorem
• Chapter 7: Multiplicative functions
• Discussion of sum of divisors and number of divisor functions, sigma and tau.
• Proof of formulars for sigma and tau at powers of primes
• Proof that a sum of a multiplicatve function over divisors of n gives a new multiplicative function
• use of above result to prove that sigma and tau are multiplicative
• example of computing sigma and tau using above results
• Chapter 8
• Description of RSA cryptography
• Example of computing encryption with RSA cryptography

Class 36 Wednesday November 18

• Continuing example of RSA cryptography
• Chapter 13: Dipohantine equations.
• 13.1: Proof of a formula for giving all Pythagorean triples.
• Discussion of how to use the same method to find solutions to equations like x² + y² = 5z²
• Proof using congruences that x² + y² = 3z² has no integer solutions.
• Very brief discussion of Bezouts theorem and elliptic curves (for general knowledge, not for exam).

Class 37 Friday November 20

• Discussion of Fermat's last theorem (section 13.2) (not for exam!)
• 13.3: Sums of squares.
• Proved that if p is a sum of 2 squares then -1 is a square modulo p
• Defined the Legendre symbol (see chapter 11.1, page 404)
• Proved Euler's Criterion for computing the Legendre symbol (page 404)
• Proved that -1 is a square modulo p if and only if p is 1 modulo 4 (Theorem 11.5 page 406)
• Proved that if p is 1 modulo 4, then some mulitiple of p is a sum of two squares (Lemma 13.4, page 530).
• Started work on proving that for a prime p, p is a sum of two squares if and only if p is 1 modulo 4. Theorem 13.5; we'll finish this next time.

Class 38 Friday November 23

• Finished proof that for a prime p, p is a sum of two squares if and only if p=1 mod 4.
• Stated result about when an integer n is the sum of two squares. We'll come back to a proof.
• Gausian integers, chapter 14.
• Defined the norm, division, units, primes, greatest common divisor, associates in Gaussian integers
• Proved the division algorithm for Gaussian intgers.