| Schedule
This is a tentative schedule for the course. If necessary, I might change it.
-
2 Feb -- 4 Feb:
Introduction, Mathematical induction, Well-ordering principle,
Division algorithm, Primes and Unique factorization.
Read: 1.2,1.3
-
9 Feb -- 11 Feb:
Euclid's algorithm, and Units and primes in a "System of numbers", and Euler's ϕ function:
Euler's theorem and Fermat's ``little'' theorem.
and modular arithmetic.
Read: 1.2 and 1.3 again, 2.1
-
16 Feb -- 18 Feb:
Mod m numbers. Chinese Remainder Theorem, Number
theory and public-key cryptography: the RSA algorithm.
Read: 2.2, 2.3, 2.5
-
23 Feb -- 25 Feb:
Solutions of polynomials modulo prime powers, Hensel's lemma.
Read: 2.6, 2.7
-
2 Mar -- 4 Mar:
Multiplicative order, Primitive roots, Quadratic residue.
Read: 2.8, 3.1
-
9 Mar -- 11 Mar:
Quadratic reciprocity, Midterm.
Read: 3.2
-
23 Mar -- 25 Mar:
Great integer function, Arithmetic functions, Convolution, and Möbius inversion.
Read: 4.1, 4.2, 4.3
-
30 Mar- 1 Apr:
Geometry of numbers, Sum of two squares.
Read: 6.4
-
6 Apr -- 8 Apr:
Cyclotomic polynomials and its relation with primitive elements mod p, Beatty sequence and its generalization, Continued fractions.
Read: 7.1, 7.2
-
13 Apr -- 15 Apr:
Continued fractions (continued).
Read: 7.3, 7.4, 7.5, 7.6
-
20 Apr -- 22 Apr:
Continued fractions (continued). Solutions to Pell's equation.
Read: 7.6, 7.7, 7.8
-
27 Apr -- 29 Apr:
Quadratic fields, Failure of unique factorization.
Read: 9.5, 9.6, 9.7
|
| Assignments.
- Due Feb. 11:
- Section 1.2: problems 47, 49, 51, 54;
- Section 1.3: problems 23, 36, 39;
- Due Feb. 18:
- Section 2.1: problems 10, 14, 20, 28.
- Find all the Pythagorean triples, i.e. all triples of natural numbers (a,b,c) such that a2+b2=c2. Hint:
- Use lines passing through (0,1) with rational slope.
- Rational points on the circle x2+y2=1.
- Use extra parameters, and give formulas for a, b, and c in terms of those extra parameters, e.g. one can write all the integer solutions of 3a+2b=1 as a=2t+1 and b=-3t-1, where t can be any integer number (convince yourself why?)
- How do you define a "prime" element in a "System of numbers"? (Any reasonable definition is fine as long as it passes the test for integers up to sign!) For which m's Z/mZ has only one prime element?
-
- Show that if p is prime and x2-1=0 in Z/pZ, then x is either 1 or -1. Is it true in Z/mZ where m is not prime?
- (Wilson's theorem) Show that (p-1)!=-1(mod p) if p is prime. Hint: Group any number from 1,..., p-1 with its inverse modulo p.
- Due Feb. 25:
- Section 2.1: problems 29, 30, 36, 49.
- Section 2.3: problems 3, 7, 9, 13, 18, 21, 37, 41, 47.
- Due Mar. 4:
- Section 2.5: Problems 3, 4, 5.
- Section 2.6: Problems 2, 7.
- Section 2.7: Problem 10.
- Show that there is no positive integer n for which 2n + 1 is divisible by
7.
- Let n>3 be an odd number. Show that there is p a prime number such that
- p | 2ϕ(n)-1,
- p does not divide n.
(Hint: Take a look at: Probem 35, section 2.3, Problem 49, section 1.2, and Problem 43, section 1.3.)
- Due Mar. 11:
- Section 2.7: Problem 12.
- Section 2.8: Problems 20, 24, 29.
-
- Let p be a prime number and k a positive integer. Show that Σi∈ Z/pZ ik is divisible by p if k is not divisilble by p-1 and it is congruent to -1 mod p if k is divisible by p-1. (Hint: Use existence of primitive elements mod p.)
- Let f be a polynomial in (Z/pZ)[x]. If degree of f is at most p-2, then p divides Σi∈ Z/pZ f(i)
-
- Let f be a polynomial in (Z/pZ)[x1,...,xn] whose degree is less than n. If x1i1...xnin is a monomial of f(x)p-1, then at least one of the ij's is less than p-1.
- 1-f(x)p-1 is either 0 or 1 mod p. It is zero if x is not a solution of f≡0 mod p and it is 1 otherwise.
- Let f be a polynomial in (Z/pZ)[x1,...,xn]. Show that if degree of f is less than n, then p divides|Vf(Z/pZ)|, where
Vf(Z/pZ):={a=(a1,...,an)∈ (Z/pZ)n| f(a)≡ 0 (mod p)}.
- Determine all integers n>1 such that (2n+1)/n2 is an integer.
- Due Mar. 25: No problem set.
- Due Apr. 1:
- Section 3.1, Problems 20, 21, 23.
- Section 3.2, Problems 15, 19, 20, 21, 24.
- Show that sum of quadratic residues mod p is divisible by p if p is an odd prime larger than 3.
- The last problem in the midtrem.
- Due Apr. 8: No problem set.
- Due Apr. 15
- Section 4.2, Problems 5, 10, 16, 19, 25.
- Section 4.3, Problems 15, 23, 25, 26, 28, 29.
- Section 7.1, Problem 3.
- Section 7.3, Problem 3.
- Section 7.4, Problem 1.
- a) Let p be prime larger than 3. For some integer x, p divides x2+x+1 if and only if p is of the form 3k+1.
b) Show that x2+xy+y2=1 is an ellipse. Its axis are lines y=x and y=-x, and find its area. (Hint: Rotate by angle 45 degree. So x=(X+Y)/Sqrt(2) and y=(Y-X)/Sqrt(2), and rewrite the equation.)
c) If p is a prime of the form 3k+1, then there are integers x and y such that p=x2+xy+y2. (Hint: Use parts a, b, and Minkowski's convex body.)
- Due Apr. 22 No problem set.
- Due Apr. 29
- Section 7.4, Problem 6.
- Section 7.5, Problem 3.
- Section 7.6, Problems 3, 4.
- Section 7.7, Problems 2, 3.
- Section 7.8, Problem 5.
- Is there a function f from Q the set of rational numbers to {A,B} a set with two elements such that:
- f(1/x)≠f(x) for any non-zero x.
- f(-x)≠ f(x) for any non-zero x.
- f(1-x)≠ f(x) for any x.
Can this map be extended to the real numbers?
- Let ξ=(m+
√D
)/q and ξ'=(m-
√D
)/q. If ξ has the following purely periodic simple continued fraction [a_0,...,a_n], then
-1/ξ'=[a_n,a_(n-1),...,a_0].
|
