Week 4 - Modular Arithmetic, Equivalence Relations & Binomial Coefficients

Question 1

c. What does congruence mean?

Answer 1

Well it means when integer a or b are “modded” it will return a remainder that is equivalent

Question 2

ii. Dealing with negative modulo

Answer 2

1. YOU CAN NEVER HAVE A NEGATIVE REMAINDER
2. If you have -43 ≡17 (mod 4), you would think -43/4 would equal to -3 right? Since 4 goes into 43, -10 times with a remainder of 3. WRONG. That would make it -37. The only way it would work is if mod 4 went into -43 eleven times (making -44, and then remainder is 1)
3. So the general rule to follow when getting a negative number you are modding is: Multiply the mod out to be “less” than the negative number you’re modding, and then add a remainder to that negative number you’re modding to see your result

Question 3

Let a,b,c∈Z and n∈N. If a≡b (mod n), then ?

Answer 3

ac≡bc (mod n).

Question 4

What two properties does congruence modulo n hold?

Answer 4

f. congruence modulo n is symmetric and transitive

Question 5

j. An equivalence relation defined on set S must satisfy:

i.

Answer 5

The symmetric property (if s1 ~ s2, then s2 ~ s1)

ii. The reflexive property (s ~ s), and
iii. The transitive property (if s1 ~ s2 and s2 ~ s3, then s1 ~ s3)
iv. Here the symbol ~ acts as the verb is equivalent to, just as ≡ represents is equivalent to

Question 6

l. The notation [a] means ?

Answer 6

“all the elements equivalent to a using some equivalence. i. So |1| and |3| are the same when (1+2k | k e Z), where k is the modulo, and |1| is the remainder

Question 7

m. The sets [a] and [b] are called ?

Answer 7

equivalence classes.

Question 8

What is a partition of a set?

Answer 8

i. In other words, a partition is when you take a set, and divide it up into smaller subsets that when added all up together equal the set

Question 9

What does the symbol C(n, k) stand for?

Answer 9

The symbol C(n / k) is pronounced “n choose k,” will be referred to as choice notation, and means the number of ways one can choose k things from a pile of n different things. The order in which the k things are chosen does not matter. (also called binomial coefficient)

Question 10

2. Choice notation identity ?

Answer 10

C(n, k) = C([n-1], [k -1]) + C([n -1],k)

Question 11

6. When this holds for two equivalence relations ~1 and ~2, we say ~1 is ___ than ~2 and ~2 is ____ than ~1
   a. The equivalence class for ~2 is formed by combining equivalence classes for ~1

Answer 11

6. When this holds for two equivalence relations ~1 and ~2, we say ~1 is finer than ~2 and ~2 is coarser than ~1
   a. The equivalence class for ~2 is formed by combining equivalence classes for ~1

Question 12

What properties does finer hold?

Answer 12

7. Note: that “finer” is reflexive, transitive, and antisymmetric
   a. ~1 f ~1
   b. ~1 f ~2, ~2 f ~3, means ~1 f ~3
   c. ~1 f ~2, ~2 f ~1 (not possible unless ~1 is equal to ~1)
   d. So this is a partial ordering of equivalence classes