Math 414 Analysis II
Key Concepts
You should be comfortable with all of the key definitions.
You should be able to state and apply all of the key results.
You should be able to sketch the proof of the key results marked with (*).
Results marked with (#) are important results that you should know the
statement of but were not proved in this course.
Chapter 1: Divisibility
Key Definitions
Key Results
- The Division Theorem (*)
- The Euclidean Algorithm
- Bezout's Identity (*)
- Linear Diophantine Equations
Key Calcuations
- Finding gcds
- solving gcd(m,n)=am+bn
- solving linear Diophantine Equations
Chapter 2: Prime Numbers
Key Definitions
- prime numbers
- Pythagorean triples
Key Results
- Fundamental Theorem of Arithmetic (*)
- Euclid's proof there are infinitely many primes (*)
- Prime Number Theorem (#)
- Dirichlet's Theorem on Primes in Arithmetic Progressions (#)
- Sieve of Eratosthenes
- There are infinitely many primitive Pythagorean triples
- Finding rational solutions to X^2+Y^2=1
Chapter 3: Congruences
Key Definitions
Key Results
- Chinese Remainder Theorem (*) and applications
- Solutions to X^2=1 (mod n)
Key Calcuations
- Solving linear congruences
- Solving systems of congruences using CRT
- Solving congruence mod n for n composite using CRT
Chapter 4: Congreuence mod p
Key Results
- Fermat's Little Theorem (*)
- Wilson's Theorem (*)
- Lagrange's Theorem: Polynomials of degree d where not all coefficients
are divisible by p have at most d roots in Z_p
- -1 is a square mod p iff p=1 (mod 4) (*)
- Hensel's Lemma
Key Calcuations
- Simplifying a^n using Fermat's Theorem
- Using Hensel's Lemma to solve equations mod (p^n)
Chapter 5: Euler's Function
Key Definitions
Key Results
- Euler's Theorem (*)
- phi(p^n)=p^n-p^{n-1} (*)
- phi(mn)=phi(m)phi(n) for m,n relatively prime
- addition formula for phi
- RSA public key cryptography
- Rabin-Miller primality test
Key Calcuations
- calcuating phi(n)
- calculating a^m using Euler's Theorem to simplify
- calculating a^n by succesive squaring
- Solving X^k=b (mod n) where i) gcd(k,phi(n))=1 and
ii) gcd(b,n)=1 or n=pq for p,q distinct primes
Chapter 6: The group of units
Key Definitions
- the order of an element
- primitive root
- cyclic groups
Key Results
- The order of a unit divides phi(n) (*)
- test for primitive roots
- There are always primitive roots in U_p for p prime
- U_n is cyclic if and only if n=2,4,p^m or 2p^m where p is an odd prime.
Key Calcuations
- Using primitive roots to solve X^k=a (mod p)
Chapter 7: Quadratic Residues
Key Definitions
- quadratic residues
- Legendre symbol
Key Results
- |Q_n|=phi(n)/M_n where M_n=|{x:x^2=1 (mod n)}|
- (g^i/p)= (-1)^i for g a primitive root
- Euler's criterion (*)
- Gauss's Lemma (*)
- 2 is a quadratic residue mod p if and only if p=1,-1 (mod 8) (*)
- Quadratic Reciprocity
- Quadratic residues mod p*n p odd, mod 2^n, mod composite N(*)
Key Calcuations
- Calculating (a/p) using Euler's criterion, Gauss's Lemma,
and Quadratic Reciprocity.
- Deciding if $aX^2+bX+c\equiv 0 \ (\mod N)$ has a solution (by completnig the square.
Chapter 9: Sums of Squares
Key Results
- The product of two elements of S_2 is in S_2 (*)
- When is a prime a sum of two squares? (*)
- When is N a sum of two squares(*)
- Every element of Z_p is a sum of two squares(*)
- The product of two elements of S_4 is in S_4
- Every element of N is the sum of four squares
Key Calcuations
- Using the method of descent to write a prime as the sum of two
Chapter 10: Fermat's Last Theorem
Key Results
- There are no solutions to X^4+Y^4=Z^2 and X^4+Y^4=Z^4 in the natural
numbers