Homework

General Rules

Please write your solutions tidily, and don’t forget your name. I don’t require LaTeX but I much prefer it. I will collect these in class. If you forget them in your dorm room, get them to my office (under the door is fine) by 4 pm at the latest.

Honor Code Rules

• Research/Working Phase: You may use resources and collaboration of all sorts while thinking and working, but you must cite them when handing in your homework (explicit URLs, page numbers, names of people).
• Writing Phase: When writing up your solutions, you cannot have any of these external resources, even including your own notes from the working/research phase, with you any longer. The exception is that you may use your textbook and class notes. In this sense, the writeup phase is “closed book” (except text/classnotes). The purpose of this is to force you to understand any help you got, not just trust or copy it. You must be able to “recreate” it from your understanding, not using notes.
• You can switch back and forth between the phases repeatedly, but not more than say every 15 minutes. The point is to dig into understanding, then dig into writing.
• If you have any questions about the above, contact me, don’t assume.

LaTeX Examples

• LaTeX file for my linear diophantine equation example (note: the “cards” require package tcolorbox to be loaded in the header portion; and the newcommand \card that I defined).

Due Friday, Apr 26th

• Problem A: Compute phi(576) (this is the Euler phi function).
• Problem B: Solve the system of linear congruences:
  • x = 1 mod 3
  • x = 2 mod 5
  • x = 3 mod 7
• Problem C: Demonstrate how to solve x^3 -x + 1 = 0 modulo 35 by using the Chinese Remainder Theorem to break 35 into 5 and 7. (Mod 5 and 7 you can solve it by simply trying all possible roots to see if they work.)
• Problem E: Find the inverse of 7 modulo 1768 using the Chinese Remainder Theorem.
• Problem D: Compute 11^193 mod 1768 by hand. Hint: 1768 = 8*13*17; use Chinese Remainder Theorem.
• Problem F: Find all values of n so that that phi(n) is less than or equal to five. Prove your list is correct. Hint: Use the formula for phi(n) and consider different cases.

Due Friday, Apr 19th

• Problem A: Let p be a prime. Let g be an integer. Then show that g^((p-1)/2) is plus or minus 1 modulo p.
• Problem B: Let p be a prime that is 3 modulo 4. Let b be an integer. Let a = b^((p+1)/4). Show that a^2 is either plus or minus b modulo p.
• Problem C: Give an algorithm to compute the square root of something modulo p, when p is 3 modulo 4 (use the previous problem). Note: sometimes things don’t have square roots, so your algorithm should either return the square root or else inform you there is no square root. (Interesting note: when p is 1 mod 4, we don’t have any good algorithms.)
• Problem D: Show that x^5 = 3 mod 11 has no solutions (use Fermat-Euler Theorem).

Due Friday, Apr 12th

• Problem A: Find Alice and Bob’s secret number in Diffie-Hellman key exchange if g=5, p=103, A = 102, B = 94.
• Problem B: Draw the dynamics of multiplication by 4 modulo 15.
• Problem C: Compute the discrete log base 11 of 16, modulo 21. Do this by hand and show your work (just take powers of 11). Modulo what number does this discrete log live?
• Problem D: Compute the Euler phi function phi(3), phi(9), phi(27), phi(81).
• Problem E: Give a formula for the Euler phi function of a power of a prime, and prove it.
• Problem F: Prove that the Euler phi function is multiplicative, i.e. phi(nm) = phi(n)phi(m) for n coprime to m. Hint: Write out the natural representatives modulo mn in an n-by-m (n rows / m cols) grid (fill it like you read: left-to-right, row by row). There are whole columns of this table that consist of residues not coprime to mn. Why? Now for the remaining columns, how do these n numbers distribute mod n?

Due Friday, Apr 5th

• Chapter 6, #1, #2 (see Problem 6.13), #3, #6, #7 (typo: this only works for a and b odd), #9, #10, #12, #14

Due Friday, Mar 15th

• Chapter 5, #6, #7, #8, #10
• Problem A:
  • Part 1) Compute the powers of 3 modulo 7, in a table. Keep going until they repeat, then go a little further.
  • Part 2) Prove that for any integer a, modulo n, the sequence 1, a, a², a³, a⁴, … must be periodic, i.e. keeps repeating the same pattern over and over forever.
  • Part 3) Using the previous parts, find a slick way to compute 3²⁰¹⁸ modulo 7.
• Problem B. Solve the system of equations x = 3 mod 5 and x = 2 mod 3. In other words, find the full collection of integers satisfying both equations at the same time.

Due Friday, Mar 8th

• Chapter 3, #15 (Remember, we gave a transcendental number in class; the idea is the same but use 10 instead of 2.)
• Chapter 5, #1, #2 (show all steps, keep numbers small enough so it is all by hand; no calculators), #5, #9
• Problem A. Prove that x² + y² = 3 has no integer solutions by considering the equation (and a postulated solution) modulo 4.
• Problem B. Write up a proof that congruence modulo N is a transitive relation. (This was the only part of equivalence relation we hadn’t done in class.)

Due Friday, Mar 1st

• Chapter 3, Exercises #2, #3, #9 (just do 7/13 only), #10
• Problem A: Use the correspondence in Theorem 3.4 (or as done in class) to find six distinct Pythagorean triples with coprime entries. Be sure to show how you have to “scale” the triple to make the entries coprime integers.
• Problem B: Use the correspondence in Theorem 3.4 (or as done in class) to find a Pythagorean triple with b=11. Demonstrate how you found it, don’t just “guess and check”. You should be demonstrating a general process that could be used to find a triple with any given odd b.
• Problem C: Prove or disprove: If a is commensurable to a’ and b is commensurable to b’ then aa’ is commensurable to bb’.
• Problem D: Prove or disprove: If a is commensurable to a’ and b is commensurable to b’ then a+a’ is commensurable to b+b’.
• Problem E: Prove that “commensurability” is an equivalence relation on real numbers not including zero.
• Chapter 3, Exercise #8.

Due Friday, Feb 22nd

• Chapter 2, #7, #8, #10, #11
• Problem A: Prove that the log base 12 of 7 is irrational. Hint: Take exponents to get rid of the log, and then try to find a contradiction.
• Problem B: Find a sequence of irrational numbers that converges to a rational number.
• Problem C: Find a sequence of rational numbers that converges to an irrational.
• Problem D: Prove that if x is rational and non-zero, and y is irrational, then xy is irrational.
• Problem E: Consider the function f on the real numbers, defined as follows: it takes the value 1 if x is rational and 0 if x is irrational. Prove that f(x) is discontinuous everywhere.

Due Friday, Feb 15th

• Problem A: Prove that, for any positive integers a,b, and n, we have gcd(aⁿ,bⁿ) = gcd(a,b)ⁿ
• Problem B: Let p be a prime. Let a be a positive integer not divisible by p. Show that there exists some multiple of a which has remainder 1 when divided by p. Hint: rephrase this problem as a solution to a linear diophantine equation, then call on a theorem which asserts the existence of a solution.
• Chapter 2 Exercises, #1, #2, #4, #5, #6, #18.

Due Friday, Feb 8th

• Chapter 1 Exercises, #7, #8, #15, #21.
• Problem #6.4 from p.44 of A Friendly Introduction to Number Theory.
• Prove that a linear Diophantine equation a₁x₁ + … + a_nx_n = c has at least one solution if and only if the gcd(a₁,…,a_n) divides c. (We defined a more general gcd on the last homework set.)
• Optional: Problem 6.6 from the PDF above is fun, more open-ended and more like (guided) mathematical exploration and research. I will give a few bonus points to those who take a thoughtful stab at it.

Due Friday, Feb 1st

• Chapter 1 Exercises, #1, #2, #9, #10 (see defn of LCM on page 35), #11, #12.

Due Friday, Jan 25th

• Chapter 0 Exercises, #10, #11, #14, #17, #19, #21, #22. On #19, the ‘Challenge’ part is bonus.