Math 55: Discrete Math – Fall 2025

Professor Francis Su
Section 1, Fall 2025

Meetings: MW 1:15pm – 2:30pm

Course Webpage: https://math.hmc.edu/su/math55/

My Email: (my last name) at math.hmc.edu

Grutors: August Loan (auloan) and Luke Wang (lukewang) can be reached at g.hmc.edu

Office Hours: Tuesdays 3pm.

Course Description

This course is an introduction to combinatorics, number theory, and graph theory with an emphasis on creative problem solving and learning to read and write rigorous proofs. Topics include: combinations, permutations, inclusion-exclusion, strong induction, recurrences, Bayes’ theorem, the Euclidean algorithm, unique factorization, modular arithmetic, Euler’s theorem, RSA encryption, planar and Eulerian graphs, and graph coloring. My goal is to create an inclusive classroom climate where everyone feels responsible for the participation and the joy that others experience in learning.

Text

There is no required textbook to buy.

We will use portions of Oscar Levin’s Discrete Mathematics: An Open Introduction (4th edition), which is available both as a PDF and in an interactive online ebook.

Coursework

There are weekly homeworks, one midterm and one final exam. Each component (homework, midterm, final) is worth at least 30% of your final grade, with the “best” component worth 40%.

Every assignment has an automatic 24 hour extension–you do not need to formally request this extension.

The learning you are doing in this class takes place in a larger framework of school and life. Sometimes life takes precedence. Similarly, ‘success’ by whatever measure is not the most important thing in this course either. Every assessment of your work in this class is a measure of mathematical progress, not a measure of your mathematical promise. Joy, wonder, and expanding your mind through struggle—these are more important!

Honor Code

The HMC Honor Code applies in all matters of conduct concerning this course. Though cooperation on homework assignments is encouraged, you are expected to write up all your solutions individually to ensure your own understanding. Your solutions should acknowledge the assistance of other people or resources of any kind.

AI Policy

(1) Online resources, including artificial intelligence, may be consulted for general learning that is not directly related to assigned problems. However, such resources, especially AI, should be viewed with a healthy skepticism–they can be wrong, or they may rely on ideas we have not covered in this class. Moreover, an over-reliance on them can be detrimental to your learning if the ideas do not “pass through your brain” or give you a deeper understanding.

(2) You should not use AI or other resources to locate solutions for any assigned work. You may check your answers using the ‘Activate’ button in the Levin e-text, but you may not use published solutions for the text. Doing any of these things will be regarded as a violation of the HMC honor code. In addition, you will miss the joy of discovering a solution for yourself, which is one of the best feelings in the world.

Lecture Notes and Zoom

I will not be recording lectures, but zoom link and lecture notes will be linked from the course Canvas site.

Homeworks

Homeworks will be assigned and due Wednesdays at 1:15pm via Gradescope.

Some of you may find LaTeX helpful in typesetting your homework. If so, there is a LaTeX class for homework here.

Read the syllabus above, and my handout on good mathematical writing. And this article if you haven’t seen it before.

Read Levin Sections 3.1-3.4.

Do the following:

Q1. Based on the handout, why is it important to write in complete sentences?

Q2. What qualities characterize a well-written solution?

Q3. Describe the difference in meaning between these three sentences:
“Let A=B.”
“Therefore A=B.”
“A=B.”

Also, do the following problems from Levin at end of each Section. The numbers refer to what Levin calls “Practice Problems”, unless it is marked with an “a” which refers to “Additional Problems”.

Levin 3.2 ( 2, a2 ) 3.3 ( 3, 7, 8, a2 )

(Note that the ebook version offers interactive opportunities to check your answers on some problems, but you will need to do more than just give answers. You will need to explain your reasoning well in order to get full credit. Caution: pressing the “Activate” button on a problem may change the problem, especially if you select ‘randomize’. But you should solve the original problem, which you can see by pressing ‘Reset’.)

Submit your homework on Gradescope.

Read Levin Sections 3.5-3.6.

Do the following:

Levin 3.1 ( 7, 10, a1 ) 3.4 ( 4, 8, a1 ) 3.6 ( a3, a9, a13 ).

Note on problem 3.4.8: the Board members are part of the group of businesspeople.

The ebook version of Levin offers interactive opportunities to check answers on many problems. You can use expressions like n! or * (times) or even C(n,k) for (n choose k) and it will evaluate them properly. But be sure to give more explanation than just the answers, you should justify each answer.

Read Levin Sections 3.5-3.6, 3.8.

Do the following:

Levin 3.5 ( 6, 9, a2 ) 3.6 ( a6, a8 ) 3.8 ( 2, 3, 8, a2 )

You may express answers in (n choose k) notation but do not leave answers in multichoose notation.

Read Levin Sections 4.5 and 4.6.

Do the following:

Levin 4.5 ( a6, a7, a9, a11, a12, a14 ) 4.6 ( a6, a8 ) and:

Question A. In just a few sentences, state 2 things you find notable or interesting about induction arguments that you hadn’t appreciated before.

Read Levin Section 4.1 and 4.4.

Do the following:

Levin 4.1 ( 4, a12) 4.4 ( 4, a3, a4, a7 ) and Questions B and C and D below:

Question B. Recall the field goals and touchdown problem from the last problem set (2.5.9).

a. Let $a_n =$ the number of ways to get $n$ points using just 3-point field goals. Explain why this sequence has generating function $A(x) = 1+ x^3 + x^6 + x^9 + \cdots$ and then explain why this expression is equal to $1/(1-x^3)$ .

b. Similarly, let $b_n =$ the number of ways to get $n$ points using 7-point touchdowns. Explain why this sequence has generating function $B(x)=1/(1-x^7)$ .

c. Let $c_n =$ the number of ways to get $n$ points using both field goals and touchdowns. This sequence has generating function $C(x)=A(x)B(x)$ . Use this Wolfram Alpha link to compute its power series. Under “Series Expansion at x=0” look for the button “More terms” and press it 3 times to see more of the series. Explain why the series is missing a term for $x^{11}$ and why the series has a coefficient of 2 for $x^{21}$ .

Question C. Write out the generating function $K(x)$ for the Fibonacci Sequence: $F_0=0, F_1=1$ , and $F_n=F_{n-1}+F_{n-2}$ . Then show $K(x) = x/(1-x-x^2)$ .

Question D. Sicherman dice are a pair of six-sided dice with non-standard numbers. One die has faces 1, 2, 2, 3, 3, 4, and the other has faces 1, 3, 4, 5, 6, 8. Use generating functions to explain why this pair of dice together behaves the same way as a pair of standard dice (i.e., the number of ways to get the sum N is the same for a pair of Sicherman dice as for a pair of regular dice). Feel free to use a computational tool (like Wolfram Alpha, which can multiply polynomials).

Problem 6A. For integers $a, b$ where $a<0$ , show that the set $A = \{ n \in {\mathbb Z} : a - n b \geq 0 \}$ is not empty by producing a specific integer $n$ that works for each case: $b<0$ and $b > 0$ . (This fact can be used to prove the division algorithm for the case where $a<0$ .)

Problem 6B. Consider the cubes: 1, 8, 27, 64, 125, 216 … When divided by 9, what remainders are possible? Show that a cube of the form $(3m+1)^3$ for an integer $m$ ) must have remainder 1 when divided by 9.

Problem 6C. Prove the Integer Combination Theorem that we discussed in class: If d|a and d|b, then for any integers x and y, show that d|(ax+by).

Hint: you’ll want to appeal to the definition of “divides”.

Problem 6D. Find gcd(300, 18) using the Euclidean algorithm. Then find integers x and y such that 300x + 18y = gcd(300, 18) using the method discussed in class.

Problem 6E. Use the Euclidean algorithm to find the gcd of consecutive Fibonacci Numbers: $\gcd(F_{n}, F_{n+1})$ .

Problem 6F. Prove that if N is a positive integer, make a conjecture about gcd(N, N+1) = 1, then prove it.

Problem 6G. A prime is a positive integer greater than 1 that has no other positive divisors besides itself and 1. Show that every number N > 1 can be expressed as a (finite) product of primes.

Hint: Do this by strong induction on N. Thus your inductive hypothesis will be: “Assume that this can be done for all N less than or equal to K.” Then in the inductive step, you’ll want to show that it can be done for N=K+1.

(We use this fact as a starting point for the proof that the factorization is actually unique.)

Problem 6H. The primes less than 15 are 2, 3, 5, 7, 11, 13. Use this list to determine whether the number 221 is prime by:
(a) checking if any prime on the list are divisors of 221, and
(b) explaining why you do not have to check if any other numbers are divisors of 221.
(Hint: if 221 had any factors >= 15, why would have to have a prime factor smaller than 15?)

Problem 6I. How many divisors does a prime power $p^n$ have? How many divisors does a product of $k$ distinct primes (like $p_1 p_2 \cdots p_k$ ) have? Explain why.

The exam will be available on Gradescope on Fri Oct 17. You will have 3 hours to do it (adjusted for any accommodations.) Once you check the exam out, there will be a 6 hour window to download and upload to Gradescope.

An 8.5×11 sheet of notes (front and back, prepared by you) will be allowed, but do not use anything else during the exam period (no internet, no AI, etc).

Problem 7A. Find gcd(300, 18) and lcm(300, 18) by first factoring 300 and 18 into primes to find the gcd, and then using the gcd-lcm theorem to find the lcm.

Problem 7B. Show that if a number $N$ is composite, then it must have a prime factor less than or equal to $\sqrt{N}$ . (Hint: if the conclusion were false, show that leads to a contradiction.)

Problem 7C. How many prime numbers are there between 1 and 100, inclusive? Between 1001 and 1100, inclusive? Between 10001 and 10100 inclusive? [Feel free to consult a list of primes.] How do the actual counts compare to the number of primes predicted by the Prime Number Theorem? Recall that the Prime Number Theorem says that the function $\pi(N)$ , the number of primes less than or equal to $N$ , is approximately $N/\ln(N)$ .

Problem 7D. Without a calculator, determine: (a) 2143 mod 10, (b) 2143 mod 5, (c) 2143 mod 7.

Problem 7E. Without a calculator, determine $2143^{2143} \mod 7$ .

Problem 7F. Without a calculator, determine the last digit of $2143^{2143}$ .

Problem 7G. You have 1205 crates of soda cans. Each crate has 16 soda cans in it. You have to repackage all the soda cans into packages of 12 cans each. After making as many complete packages as possible, how many soda cans will be left over? Solve this problem without a calculator, and make your life easy using (mod 12) arithmetic.

Problem 7H. Use Wilson’s theorem to help you find the remainder when 99! is divided by 101.

Problem 7I. Show that the equation $x^4 + 1 = 3 y^4$ can never be solved in integers x and y.
(Hint: if the equation cannot be solved in integers mod 5, it cannot be solved in integers. Also, 5 is prime.)

Problem 8A. (a) Fill out a multiplication table for numbers mod 6. Which numbers mod 6 have inverses? In which rows do all the numbers 0, 1, 2, … , 5 appear exactly once? Explain what you see.
(b) Fill out a multiplication table for numbers mod 7. Which numbers mod 7 have inverses? In which rows do all the numbers 0, 1, 2, … , 6 appear exactly once? Explain what you see.

Problem 8B. Fill out a table of powers of numbers mod 7, like so:

$\underline{ n | \ n^2 \ n^3 \ n^4 \ n^5 \ n^6 \ n^7}$
$0 |$
$1 |$
$2 |$
$3 |$
$4 |$
$5 |$
$6 |$
Then notice: which numbers mod 7 have some power equal to 1? And explain how one of the columns in your table shows the truth of Fermat’s Theorem.

Problem 8C. Fill out a table of powers of numbers mod 6, like so:

$\underline{ n | \ n^2 \ n^3 \ n^4 \ n^5 \ n^6}$
$0 |$
$1 |$
$2 |$
$3 |$
$4 |$
$5 |$
Then notice: which numbers mod 6 have some power equal to 1? And explain how one (or more) of the columns in your table show the truth of Euler’s Theorem.

Problem 8D. Mod 11, the inverse of 3 is 4. Solve the congruence $3 x \equiv 7 \mod 11$ by multiplying both sides of the congruence by 4 and finding $x$ .

Problem 8E. According to Euler’s theorem, if $(a,N)=1$ , then $a^{\phi(N)} \equiv 1 \mod N$ . This gives us a method for finding the inverse of a number $a$ as $a^{\phi(N)-1}$ . Mod 7, which column in the table of Problem BB gives the inverses of n? Verify that these are, in fact, inverses of the corresponding numbers.

Problem 8F. Look at this table of Euler’s totient function. For which $N$ is $\phi(N)$ an even number? Make a conjecture and prove it.

Problem 8G. The Google search function will find 66^2 mod 119 by typing it in the search box, like this. But it won’t compute 66^77 mod 119, because the power is too large. So compute 66^77 mod 119 by the method discussed in class to compute large powers, using the fact that 77 = 64+8+4+1, because the binary expansion of 77 is 1001101. (Feel free to use Google to compute squares mod 119 when needed.)

Problem 8H. Using N=119, determine $\phi(N)$ and verify that the public key E=5 is relatively prime to $\phi(N)$ . Then determine the corresponding private key D, where 0<=D< $\phi(N)$ , that corresponds to E. (You can find D from E the same way that you can find E from D as discussed in the class notes.)

Problem 8I. Using the N and the public key E in the prior problem, encrypt the message M=19 to get an encrypted message C. What is C? Then use the private key D you found in the prior problem to decrypt C and verify that you get M.

Read: Levin Sections 2.1 and 2.4.

Do the following:

Levin 2.1 ( a3, a5 , a13, a14, a15 ) and 2.4 ( a1, a3. a4, a10 )

Read Levin Sections 2.2 and 2.3

Do the following: (a reminder: you should not be using AI to solve your homework problems for you. If you use it to look up a definition or study some concept, be sure to indicate how you used it).

Levin 2.1 ( a7 ) You’ll need to read the section to learn the definition of bipartitite.
Levin 2.2 ( a3, a4, a7, a9 ).
Levin 2.3 ( a2, a3, a5, a11 ).

I’m not a fan of the minimal criminal terminology from the book. It refers to a minimal counterexample, as you can see from reading section 2.2.

Read Levin Section 2.5.

Problem Z. Answer the second “Investigate!” problem in the Section 2.5, about the math department’s 10 classes. Also do: Levin 2.5 ( a3, a6 parts acd, a10, a11 ). See the notes on the problems below:

2.5.a3: In addition to giving the chromatic number of each graph, exhibit a coloring with that number of colors and give a brief argument why it can’t be fewer.
2.5.a6: In part (a) color the tree with 2 colors. In part (c), use the fact that in a tree, paths between any 2 vertices are unique.
2.5.a10: A hint here is to notice there are odd cycles in the graph.
2.5.a11: You should assume G is a connected graph (the statement is false without this additional condition).

The exam will be on Gradescope.

Below this line, all homeworks are TENTATIVE. This means they are likely to be assigned, but there is no guarantee that they will until you see them moved above.