EECS 203: Discrete Mathematics

Winter 2026 Homework 4

Due Thursday, Feb. 12, 10:00 p.m.

No late homework accepted past midnight.

Number of Problems: 11 Total Points: 100

• Match your pages! Your submission time is the time you upload the file, so the time
you take to match pages does not count against you.

• Submit this assignment (and any regrade requests later) on Gradescope.

• Justify your answers and show your work (unless a question says otherwise).

• By submitting this homework, you agree that you are in compliance with the Engi-
neering Honor Code and the Course Policies for 203, and that you are submitting your
own work.

• Check the syllabus for full details.

1
Reminders
• A number x is positive if x > 0, or negative if x < 0. The number 0 is neither positive
nor negative.

• An integer k divides an integer x, written k | x, if there exists an integer j with x = jk.

• A real number x is rational if there exist integers a and b (where b ̸= 0) with x = ab .

Otherwise, x is irrational.

• In your proofs, you may always use the following facts without further justification:
– The sum, difference, or product of two integers is an integer.
– The square of a real number is non-negative.
– The usual laws of algebra work.
• You may use closure properties of the integers without proof, such as:
integer · integer = integer, integer + non-integer = non-integer, etc.

• You may use any facts about modular arithmetic without justification, such as the
rules of modular addition and multiplication. This includes algebraic facts about even
and odd numbers, such as even + odd = odd, even · odd = even, etc. (since these
are equivalent to addition and multiplication modulo 2).
• An integer m divides an integer x, written m | x, if there exists an integer k with
x = mk. We also say that x is a multiple of m. The greatest common divisor of two
integers a, b, written gcd(a, b), is the largest integer that divides both a and b.

• The set Z = {. . . , −2, −1, 0, 1, 2, . . . } is the integers. The set Z+ = {1, 2, . . . } is the
positive integers. The set Q is the rational numbers; that is, the numbers that can
be written in the form a/b for integers a and b. The set Q+ is the positive rational
numbers. The set ∅ is the empty set.

• Fermat’s Little Theorem states that for any prime p and any integer a, ap ≡ a (mod p).
For any prime p and any integer a that is not divisible by p, ap−1 ≡ 1 (mod p).

2
1. Reflection [14 points]
Carefully read and understand the posted solutions to the previous homework. Identify one
part of a question (for example, part (a) of Question 3) where you think your own solution
has the most room for improvement. This could be the solution for which you lost the most
points (self-grade, since official grades are not out yet), felt you had unsound reasoning,
needed better organization, or any other metric of your choice.
Copy or screenshot your solution. Then in a few sentences, explain why you chose this
question and how your solution could be improved.
Notes:
• You must complete this question even if you anticipate getting full credit on the previ-
ous homework: just because you may get all the points doesn’t necessarily mean that
there isn’t something that could have been improved! If this applies to you, we encour-
age you to be creative about what metric or axis you use to measure improvement.

• If you did not do last week’s homework, choose a problem from it that looks challenging
to you, and in a few sentences, explain the key ideas behind its solution in your own
words.

Mechanical Problems

2. How low can you go? [9 points]

Suppose a ≡ 8 (mod 9) and b ≡ 7 (mod 9). In each part, find c such that 0 ≤ c ≤ 8 and
(a) c ≡ 2a3 + b2 (mod 9)

(b) c ≡ b20 + 1 (mod 9)

(c) c ≡ a9999 (mod 9)

Show your work! You should be doing the arithmetic/making substitutions without using
a calculator. Your work must not include numbers above 100 (excluding the exponent in
part (c)).

3. Triskadecaphobia [8 points]
Solve the linear congruence 7x ≡ 613 (mod 13) using Fermat’s Little Theorem.

3
4. Multiplication Demonstration [6 points]
Prove that if a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n).

5. Odd Mod [9 points]

Prove or disprove the following:
(a) For all integers n, if n is odd then n2 ≡ 1 (mod 8).
(b) For all primes p > 3, p2 ≡ 1 (mod 24).
Note: You may use your results from part (a) in part (b)

6. Modular Inverse [5 points]

Determine if 25−1 (mod 68) exists. If so, find it using the Extended Euclidean Algorithm.

7. An Equation With No Solutions [6 points]

Prove that the equation x2 + y 2 = 2027 has no integer solutions.

Hint: Try analyzing this equation modulo 4.

Bad Proofs
Each of the following propositions may or may not be true, but we have given an incorrect
“proof” that attempts to show that it is true. Identify the specific logical error made in each
proof by citing a sentence, equation, step, or missing part of the proof, and briefly explain
why it is wrong.

8. A Modest Mistake [6 points]

Compute 2101 (mod 7).

Incorrect Calculation. The following equivalences are all taken mod 7:

2101 ≡ 23 (since 101 ≡ 3)
≡8
≡1

4
Therefore 2101 ≡ 1.

9. Opposite Day [6 points]

Solve the linear congruence 3x ≡ 21 (mod 72) using the modular inverse of 3 (mod 72)

Incorrect Solution. The following equivalences are all taken mod 72:
3x ≡ 21
−1
3 · 3x ≡ 21 · 3−1
x≡7

Discovery Problems

10. What’s your (credit card) Number? [16 points]

Luna wants to validate credit card numbers using a key she created called the Luna key,
which consists of a single digit from 0 − 9.
To compute the Luna key for a number, she uses the following steps:
1. Starting from the rightmost digit and moving left, double every even-positioned
digit, and let the rightmost digit be position 0 .
2. If doubling a digit produces a value ≥ 10, replace that value by the sum of its digits
(equivalently, subtract 9).
3. Let s be the sum of the resulting value from each digit
4. Find the key k by using the formula: k = (10 − (s mod 10)) mod 10.
(a) Find the key k to turn the following numbers into Luna numbers.
(i) 912
(ii) 9012
(iii) 9021
(iv) 9201
(b) Let a and b be distinct digits in a number such that a, b ∈ {0, 1, . . . , 9}. Prove that
swapping two adjacent digits a and b does not change the Luna key if and only if a
and b are congruent to: mod

5
11. Grouped Work [15 points]
Let n and m be integers. We say that n and m are grouped if, for all primes p and natural
numbers k, we have n ≡ m (mod pk ).
(a) What is the relationship between two grouped integers? Your answer should not simply
be a rephrasing of “grouped”, but instead be a different way of thinking about grouped
integers. Fill in the blank below with your answer.
The integers n and m are grouped if and only if .

(b) Prove your claim from the previous part.