Last updated April 10, 2022

Status: Tags: #archivedCards/macm101/settheory #archivedCards/macm101/numbertheory Links: Discrete Math Relations - Integers

Congruences

Principles

• Residues
• Linear Congruences

Definition in terms of notation ?

Define and prove in terms of euclidean algorithm ? a ≡ b (mod m) if and only if a = b + km for some integer k By definition, a ≡ b (mod m) if and only if a – b = km for some integer k. Then a = b + km

Integers a and b are congzruent modulo m iff they have same remainder when divided by m. If a-b = km, b = qm + r, then ? a = km + b = (k+q)m + r

Uses

• Caesar Cipher
• Psuedorandom Generators

Theorems

Prove if a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m) ?

Examples

12 = 5 (mod 7) 12 = 6 (mod 3) 12 = -3 (mod -15) 12 = 0 (mod 12)

Prove congruences are equivalent relations (k,a,b) ?

Congruences definition with integers k, a, b

• Example when k is 3 ?
• Refer to modulo in coding

___

Backlinks

1

list from Congruences AND !outgoing(Congruences)

References:

Created:: 2021-10-26 16:40