M328K: Elementary Number Theory, Fall 2012
unique number 56020
MWF 11-12, RLM 5.118
Daniel Allcock, RLM 9.112, phone 1-1120
my office hours: M1-2 and W2-3
(my last name)@math.utexas.edu.

This is where I will post homework assignments and other announcements. For general information, see the first-day handout.

HW 1 (due Fri Sep 7)
1.1: 2, 8, 10, 16, 24
1.2: 8, 10, 18, 20, 28 (on 8 give a picture-proof like in 6 or 7 rather than a formal proof)
1.3: 4, 8, 14, 16

HW 2 (due Fri Sep 14)
1.3: 26, 30, 34. (On 30, be sure that your proof uses n>4 in an essential way. On 34 it may help to prove a lemma using induction before attacking the problem itself: the 2ⁿx2ⁿ square, minus any one of its four quadrants, can be covered by L-shaped pieces. Also to be clear: throughout this problem the L-shaped pieces are not to overlap.)
1.4: 4, 8, 34, 40 (For interest: one way to discover the formula you prove in 40 is to use the result of 34 and diagonalize the matrix, which makes computing its powers easy.)
1.5: 2, 14, 16, 28, 38, 40. (16 is a "does there exist?" question, which means you must either prove such numbers exist, perhaps by giving examples, or prove that they don't; in particular, the answer will be a proof. And the point of 28 is to remind you that "if and only if" means you have to prove two things: that one statement implies the other, and that the other implies the one.)

HW 3 (due Fri Sep 21)
3.1: 2, 4, 5, 11, 18, 28 (On 28, only treat the cases n=0,..,10 and 29. That's enough to fulfil the purpose of the problem.)
3.2: 22a
3.3: 2, 4, 24, 30 (On 4, give a formal proof of your answer.)
also: For each pair of positive integers m and n that are relatively prime, and both less than or equal to 10, compute m²+n² and then factor it into primes. List the primes that occur this way. Work out which ones have the form 4a+1 and which have the form 4a+3 with a an integer. What do you notice? (Yes this problem really does require 100 cases, but this gets cut down by symmetry and the relative primality condition.)

HW 4 (due Fri Sep 28)
3.3: 14, 16, 22
3.4: 2, 4, 10

HW 5 (due Fri Oct 5)
3.5: 4, 8, 10, 12, 14, 16, 28, 30, 70

EXAM 1 scale:
A: 90+
B: 79+
C: 67+
D: 56+

HW 6 (due Fri Oct 12)
3.5: 34, 40
3.7: 2, 8, 10
4.1: 5, 22, 24, 30, 36, 42

HW 7 (due Fri Oct 19)
4.1: 12, 13, 14, 32, 34, 48
4.2: 2, 8, 9, 10, 12, 16
And one problem I meant to assign when we were doing 3.5: show that x₀=sqrt(3)+sqrt(5) is irrational. (Hint: find a polynomial f(x) such that f(x₀)=0 and then use theorem 3.18.)

HW 8 (due Fri Oct 26)
4.2: 18
4.3: 2, 4abc, 13
4.4: 2, 4, 6
And one more problem: Suppose r,s are integers with s not 0. Show that 2^r/s is irrational unless r/s is an integer. (Hint: this is another one where theorem 3.18 is useful. This problem is a bit different from last week's though.)

HW 9 (due Fri Nov 2; mostly a review hw set)
4.1: 28, 35 (On 35 you can use Hensel but don't need to.)
4.2: 6
4.3: 6, 34 (On 34 you can assume a₀=0 for simplicity. Note: even though this is section 4.3, to me the natural solution uses Hensel's lemma from 4.4.)
4.4: 8, 10 (Note: you can solve 10 without finding all the solutions, saving quite a bit of work.)



EXAM 2 scale:
A: 86+
B: 73+
C: 56+
D: 49+

HW 10 (due Fri Nov 9)
5.5: 2, 6, 8, 10, 12, 22 (doing 11 on your own might help with 12)
6.1: 16, 22, 24, 28, 34
6.3: 2, 6, 7, 9, 10
And two extra problems. In both cases you should show that there are no integer solutions.
(1) x²+3y²=2,999,999,999
(2) x²+y²+4z²=100,000,000,000,003
(Hint: these problems aren't on current material. They're the problems I promised you back when I used congruences to show that x²+y²=100,000,000,000,003 has no integral solutions. The trick was to choose the right modulus.)

HW 11 (due Mon Nov 19)
6.2: 1, 2
6.3: 3, 4, 8, 12
7.1: 4, 8, 12, 18, 20
8.4: 4, 6, 18

HW 12 (due Fri Nov 30)
8.4: 1, 2, 7
9.1: 2, 5, 6, 8, 12, 16, 18
9.2: 3, 6, 8, 10
AND: factor 2669, 2627, 2747 and 2881, and raise 997 to the 150th power modulo each of these numbers. The point of this is for you to gain fluency factoring reasonable numbers quicky with your calculator, and modular exponentiation (pp. 151-2). You can use your calculators on the exam, and you will need to for RSA problems, but unless you practice, even with your calculator you will go painfully slowly. If you know the primes of small size (each of these numbers is less than 54²) and are used to the keypresses and memory storage/recall on your calculator then you can find factors quickly. And modular exponentiation is again a skill your fingers learn. If you still feel slow after doing these exercises then make up some more and do them.

HW 13 (due Fri Dec 3)
9.1: 10, 14
9.2: 12, 16

EXAM 3 scale:
A: 80+
B: 68+
C: 56+
D: 47+ Office hours for finals week: M 11-12 and 2-3, and Tuesday 2-3:30.

FINAL EXAM scale:
A: 84+
B: 73+
C: 60+
D: 54+