Bite-Sized Mathematics for Computer Science

Notes on MIT's 6.042J

Eda Eren
Table of Contents

Introduction

Prerequisites & Resources

Unit 1: Proofs

00. Introduction to Proofs

01. (Two) Proof Methods

02. The Well Ordering Principle

03. Logic & Propositions

04. Quantifiers and Predicate Logic

05. Sets

06. Binary Relations

07. Induction

08. State Machines — Invariants

09. Recursive Definitions

10. Infinite Sets

Unit 2: Structures

11. GCDs

13. Euler's Theorem

14. RSA Encryption

15. Digraphs: Walks and Paths

16. Directed Acyclic Graphs

17. Partial Orders and Equivalence

18. Degrees & Isomorphism

19. Coloring & Connectivity

20. Trees

21. Stable Matching

Unit 3: Counting

22. Sums & Products

23. Asymptotics

24. Counting with Bijections

25. Repetitions & Binomial Theorem

26. Pigeonhole Principle, Inclusion-Exclusion

Unit 4: Probability

27. Intro to Discrete Probability

28. Conditional Probability

29. Independence & Causality

30. Random Variables, Density Functions

31. Expectation

32. Deviation: Markov & Chebyshev Bounds

33. Sampling & Confidence

34. Random Walks & PageRank

Congruences

Take two integers aa and bb.

The notion of congruence is defined as:

ab (mod n) iff n(ab)a \equiv b \ (\text{mod } n) \text{ iff } n | (a - b)

where nn is considered to be greater than 11.

So, aa is congruent to bb mod n\text{mod }n iff nn divides aba - b.

A simple example: 2915 (mod 7)29 \equiv 15 \ (\text{mod }7). 291529 - 15 is 1414, and 7147 | 14.

Let's look at a more interesting one:
66666663788253 (mod 10)66666663 \equiv 788253 \ (\text{mod }10).

Both numbers have 33 in their units place, and because the result of their subtraction has 00 in its units place, it is divisible by 1010.

We can see that this is also true:

ab (mod n) iff rem(a, n)=rem(b, n)a \equiv b \ (\text{mod } n) \text{ iff } \text{rem}(a, \ n) = \text{rem}(b, \ n)

So, aa is congruent to bb iff both have the same remainder when divided by nn.

Applied to the first example, we have 2915 (mod 7)29 \equiv 15 \ (\text{mod } 7) iff rem(29, 7)=rem(15, 7)\text{rem}(29, \ 7) = \text{rem}(15, \ 7). It is true because rem(29, 7)\text{rem}(29, \ 7) is 11, and rem(15, 7)\text{rem}(15, \ 7) is also 11. Since they are equal to each other, 2915 (mod 7)29 \equiv 15 \ (\text{mod } 7).


There are some basic properties of congruences:

Reflexive Property aa (mod n)a \equiv a \ (\text{mod }n)
Symmetric Property ab (mod n)    ba (mod n)a \equiv b \ (\text{mod }n) \implies b \equiv a \ (\text{mod }n)
Transitive Property ab (mod n)bc (mod n)    ac (mod n)a \equiv b \ (\text{mod }n) \land b \equiv c \ (\text{mod }n) \implies a \equiv c \ (\text{mod }n)

A number is congruent to its own remainder mod n\text{mod }n:

arem(a, n)  (mod n)a \equiv \text{rem}(a, \ n) \ \ (\text{mod }n)

Why is that?

We can see that aa and the remainder of aa have the same remainder by taking the remainder of both sides:

rem(a, n)rem(rem(a, n), n)  (mod n)\text{rem}(a, \ n) \equiv \text{rem}(\text{rem}(a, \ n), \ n) \ \ (\text{mod }n)

Let's look at it with an example:

Let's say that aa is 77, and nn is 22.
7rem(7, 2)  (mod 2)7 \equiv \text{rem}(7, \ 2) \ \ (\text{mod } 2), so 71  (mod 2)7 \equiv 1 \ \ (\text{mod } 2).
Taking the remainder of both sides: rem(7, 2)rem(rem(7, 2), 2)  (mod 2)\text{rem}(7, \ 2) \equiv \text{rem}(\text{rem}(7, \ 2), \ 2) \ \ (\text{mod }2).
1rem(1, 2)  (mod 2)1 \equiv \text{rem}(1, \ 2) \ \ (\text{mod }2).
And, finally, 11  (mod 2)1 \equiv 1 \ \ (\text{mod }2).

One point to remember is that the remainder is between 00 and nn: 0rem(a, n)<n0 \leq \text{rem}(a, \ n) \lt n.


If ab  mod(n)a \equiv b \ \ \text{mod}(n), then a+cb+c  mod(n)a + c \equiv b + c\ \ \text{mod}(n).
And, why is that?
Since nn divides aba - b, it will also divide (a+c)(b+c)(a + c) - (b + c):

n  (ab)    n  ((a+c)(b+c))n \ | \ (a - b) \implies n \ | \ ((a + c) - (b + c))

If ab  mod(n)a \equiv b \ \ \text{mod}(n), then acbc  mod(n)a \cdot c \equiv b \cdot c\ \ \text{mod}(n).
And, why is that again?
Since nn divides aba - b, it will also divide (ac)(bc)(a \cdot c) - (b \cdot c):

n  (ab)    n  (ab)cn \ | \ (a - b) \implies n \ | \ (a - b) \cdot c

Therefore,

n  ((ac)(bc))n \ | \ ((a \cdot c) - (b \cdot c))

That seems like ordinary arithmetic so far. But, let's take a look at an example:
8232  mod(10)8 \cdot 2 \equiv 3 \cdot 2 \ \ \text{mod}(10)

If you want to cancel the 22's, guess what? You can't:
8≢3  mod(10)8 \not\equiv 3 \ \ \text{mod}(10)

Then, when can we cancel kk?

The answer is when it has no common factors with nn. In other words, gcd(k, n)=1\text{gcd}(k, \ n) = 1.

In order to cancel something, we have to have its inverse, a trivial example is 122\frac{1}{2} \cdot 2, we can cancel the 22's and get the result of 11.

Now, let's say that kk' is an inverse of k  mod(n)k \ \ \text{mod}(n):
kk1  mod(n)k' \cdot k \equiv 1 \ \ \text{mod}(n)

We can think of kk' as an integer that acts like 1k\frac{1}{k}.

What we know is that if gcd(k, n)=1\text{gcd}(k, \ n) = 1, that means we have a linear combination of kk and nn which is also 11: sk+tn=1sk + tn = 1.

Since sk+tnsk + tn and 11 are equal, they are congruent to each other mod(n)\text{mod}(n):
sk+tn1  mod(n)sk + tn \equiv 1 \ \ \text{mod}(n)

nn is congruent to 0  mod(n)0 \ \ \text{mod}(n), so we can write it as such:
sk+t01  mod(n)sk + t0 \equiv 1 \ \ \text{mod}(n)

Then, what we're left with is this:
sk1  mod(n)sk \equiv 1 \ \ \text{mod}(n)

And, that means ss is an inverse of kk.

So, ss was indeed the inverse of kk all along, it is kk'!


There is another way to cancel kk if it's relatively prime to nn:

If akbk  mod(n)a \cdot k \equiv b \cdot k \ \ \text{mod}(n) and gcd(k, n)=1\text{gcd}(k, \ n) = 1, then we can multiply it by the inverse:

(ak)k(bk)k  mod(n)(a \cdot k)k' \equiv (b \cdot k)k' \ \ \text{mod}(n)

Reorganize it a bit:
a(kk)b(kk)  mod(n)a \cdot (k \cdot k') \equiv b \cdot (k \cdot k') \ \ \text{mod}(n)

Which means:
a1b1  mod(n)a \cdot 1 \equiv b \cdot 1 \ \ \text{mod}(n)

Therefore:
ab  mod(n)a \equiv b \ \ \text{mod}(n)

The point is that kk is cancellable mod(n)\text{mod}(n) iff kk has an inverse mod(n)\text{mod}(n) iff gcd(k, n)=1\text{gcd}(k, \ n) = 1.

In other words, kk is cancellable iff kk is relatively prime to nn.