MAT 421 Suggested HW Problems

Highlighted homework is due soon

Date

 Assignment
10 May 35.8, 36.1, 36.2, 36.4, 36.5
Also,
  • Show that 2 is irreducible in \(\mathbb Z[i\sqrt5]\).
  • The set \(\mathbb Z[\frac{1}{2}]\) consists of all numbers of the form \(a+\frac{1}{2^k}\cdot b\) where \(a,b\in\mathbb Z\) and \(k\in\mathbb N\). For example, \[\frac{1}{2},3+\frac{7}{4},8-3\cdot\frac{1}{128}\quad\in\quad\mathbb Z\left[\frac{1}{2}\right]\] while \[\frac{1}{3}, \frac{1}{12}, \frac{4}{3}, e, i, \pi\quad\not\in\quad\mathbb Z\left[\frac{1}{2}\right] .\] \(\mathbb Z[\frac{1}{2}]\) is a ring, like \(\mathbb Z\), \(\mathbb Z[i]\), and \(\mathbb Z[i\sqrt5]\).
    • First, perform some arithmetic with random elements of \(\mathbb Z[\frac{1}{2}]\), to get a little comfortable with it. Try addition, subtraction, and multiplication (the operations of a ring).
    • Show that 2 is a unit (has a multiplicative inverse) in \(\mathbb Z[\frac{1}{2}]\), while 3 is not.
    • In general, which elements of \(\mathbb Z[\frac{1}{2}]\) are units, and which will not?
    • Find some irreducible elements of \(\mathbb Z[\frac{1}{2}]\). Do you notice any pattern? (Be honest: “No” might be the right answer. Then again, it might not.)
    • Will the division algorithm work in \(\mathbb Z[\frac{1}{2}]\)? (It might help to try a few first. Keep in mind that that the remainder must be smaller than the divisor.)
    • Will you be able to work out Bézout identities in \(\mathbb Z[\frac{1}{2}]\)?
    • Will irreducibles also be prime in \(\mathbb Z[\frac{1}{2}]\)? If not, find a counterexample; if so, explain why.
1 MayVideo and handout on Fermat’s Last Theorem
Also, for extra credit (in homework): in class we showed that dividing \(8+7i\) by \(3+2i\) could have two legitimate results: \(q=3\) and \(r=-1+i\), or \(q=3+i\) and \(r=1-2i\). By “legitimate” we mean the remainder is smaller than the divisor, where “smaller” is measured according to the Euclidean norm \(\left\Vert a+bi\right\Vert=a^2+b^2\). Are there other legitimate remainders? If so, what are they? If not, why not? What is the maximum number of remainders Gaussian integer division can result in, and why?
Material for test 2, from here down
20 Apr
  • 18.1, 18.2
  • Use the El Gamal scheme to decrypt the message below that corresponds to the last digit of your USM ID.
    • The public key is \(p=43\), \(\alpha=19\), and \(\alpha^a=35\).
    • If the last digit of your USM ID is \(z\), use \(b=z+3\) as your private key.
    • The unencrypted message encodes \(0\rightarrow0,1\rightarrow1,\ldots,9\rightarrow9\), space as 10, and \(A\rightarrow11,B\rightarrow12,\ldots,Z\rightarrow36\).
      For instance, “R U OK 007” would encode as 28, 10, 31, 10, 25, 21, 10, 0, 0, 7. This is before encryption. Encryption changes the numbers to something else.
    USM IDmessage
    01, 25, 17, 10, 34, 40, 0, 40, 18, 2, 17, 1, 30, 17, 40, 29, 17, 2, 18
    135, 15, 36, 6, 29, 24, 11, 24, 28, 27, 36, 35, 18, 36, 24, 26, 36, 27, 28
    221, 9, 13, 38, 26, 23, 39, 23, 34, 42, 13, 21, 28, 13, 23, 7, 13, 42, 34
    34, 14, 25, 40, 7, 31, 5, 31, 29, 8, 25, 4, 34, 25, 31, 30, 25, 8, 29
    411, 17, 15, 24, 30, 10, 4, 10, 26, 22, 15, 11, 29, 15, 10, 18, 15, 22, 26
    541, 36, 9, 23, 18, 6, 3, 6, 7, 39, 9, 41, 26, 9, 6, 28, 9, 39, 7
    616, 13, 14, 31, 28, 38, 40, 38, 30, 32, 14, 16, 7, 14, 38, 34, 14, 32, 30
    71, 25, 17, 10, 34, 40, 28, 40, 18, 2, 17, 1, 30, 17, 40, 29, 17, 2, 18
    835, 15, 36, 6, 29, 24, 2, 24, 28, 27, 36, 35, 18, 36, 24, 26, 36, 27, 28
    921, 9, 13, 38, 26, 23, 25, 23, 34, 42, 13, 21, 28, 13, 23, 7, 13, 42, 34
  • For extra credit. Encrypt the message “Home alone” in the following way:
    • Use the same encoding of letters as above.
    • Group the numbers in pairs \((m_1,m_2),(m_3,m_4),\ldots\).
    • Turn each pair into one number in the following way: \((m_i,m_{i+1})\rightarrow41m_1+m_2\).
    • Use \(p=1693\), \(\alpha=5\), \(\alpha^a=312\), and \(b=13\) to generate the private key \(\alpha^{ab}\).
12 Apr 15.2, 15.3, 15.5, 16.1, 16.3, 17.1, 17.2, 17.4
Hint for 17.4: Factor out gcd, solve new problem, use to construct solution to original
10 AprRead Chapter 18
5 AprRead Chapter 17
Exercises 12.2, 12.3(a,b), 13.3, 14.1, 14.2
Also prove that any prime larger than 4 is congruent to 1 or 5, modulo 6.
Hints:
  • For 14.1, consider the case where \(n\) is odd, then when \(n\) is even, but not a power of 2.
  • For 14.2, try an example like \(m=3\) and \(n=4\), then \(m=3\) and \(n=5\). Look for a pattern to the division of \(F_{k-2}\) by \(F_m\). Then show that for any odd number \(\gcd(a,a-2)=1\).
3 AprRead Chapter 16
29 MarExercises 11.1, 11.2, 11.3, 11.5, 11.6
For participation points: 11.10
Material for test 1, from here down
8 MarExercises 10.1, 10.2
6 MarRead Chapter 11
Exercises 8.2, 8.3, 8.4(b-e), 8.5, 8.9, 9.1, 9.3
22 FebExercises 6.1, 6.2, 6.5, 6.6(a-c) Bonus 6.6(d-f)
7.1, 7.2, 7.6
20 FebRead Chapters 9, 10
15 FebRead Chapter 8
(pushed back due to illness) Exercises 3.1, 3.2, 3.3
Exercises 5.1, 5.3, 5.4
6 FebRead Chapters 6, 7
1 FebExercises 2.2, 2.6, 2.7
25 JanExercises 1.1, 1.2, 1.6
23 JanRead Chapters 1, 2