# 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
• greatest common divisors
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
• congruences
• Z_n
• U_n
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
• units
• Carmichael numbers
Key Results
• Euler's Theorem (*)
• phi(p^n)=p^n-p^{n-1} (*)
• phi(mn)=phi(m)phi(n) for m,n relatively prime
• 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)

Key Definitions
• 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 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