Discrete Mathematics – Lecture 9: The Integers and Division

Vocabulary flashcards covering key terms and concepts from Lecture 9 on integers, division, modular arithmetic, and basic cryptology.

Divides (a | b)

The relation where a non-zero integer a divides an integer b if there exists an integer c such that b = a c.

Factor

A number that divides another number exactly; if a | b, then a is a factor of b.

Multiple

A number produced by multiplying a given integer by another integer; if a | b, then b is a multiple of a.

Not-Divides Symbol (a ∤ b)

Indicates that a does NOT divide b (no integer c satisfies b = a c).

Theorem 1 (Divisibility Properties)

(i) If a | b and a | c, then a | (b + c). (ii) If a | b, then a | b c for any integer c. (iii) If a | b and b | c, then a | c.

Corollary 1 of Divisibility

If a | b and a | c, then a divides every linear combination m b + n c for all integers m,n.

Division Algorithm

For any integer a and positive integer d, there exist unique integers q (quotient) and r (remainder) with 0 ≤ r < d such that a = d q + r.

Divisor (d)

The positive integer by which another integer (dividend) is divided in the Division Algorithm.

Dividend (a)

The integer being divided by the divisor in the Division Algorithm.

Quotient (q)

The integer result of division in the Division Algorithm; q = a div d.

Remainder (r)

The non-negative integer less than the divisor that ‘remains’ after division; r = a mod d.

div Function

Notation a div d gives the quotient q in the Division Algorithm.

mod Function

Notation a mod d gives the remainder r in the Division Algorithm.

Modular Arithmetic

Arithmetic system where numbers ‘wrap around’ a fixed modulus; operations use remainders after division by the modulus.

Modulus (m)

The positive integer specifying the wrap-around value in modular arithmetic and congruences.

Congruence Modulo m

Integers a and b are congruent modulo m (a ≡ b (mod m)) if m divides a − b; they have the same remainder on division by m.

Remainder Criterion for Congruence

a ≡ b (mod m) if and only if a mod m = b mod m.

Application: Pseudorandom Number Generation

Uses modular arithmetic to produce sequences that mimic randomness for simulations.

Application: Hashing Functions

Employs modular arithmetic to map data to fixed memory locations efficiently.

Application: Cryptology

Relies on modular arithmetic for encrypting and decrypting messages.

Cryptology

The study of secret communication, encompassing encryption and decryption methods.

Encryption

The process of converting a message into a secret (cipher) form.

Decryption

The process of transforming an encrypted message back to its original form.

Caesar Cipher

A classical encryption scheme that shifts each alphabet letter three positions forward; mathematically f(p) = (p + 3) mod 26.

Shift Cipher

Generalization of the Caesar cipher that shifts each letter by k positions: f(p) = (p + k) mod 26.

Inverse Function of Shift Cipher

f⁻¹(p) = (p − k) mod 26; used to decrypt a message encrypted with a shift cipher.

12-Hour Clock

Everyday example of modular arithmetic with modulus 12 (e.g., 10 + 5 ≡ 3 (mod 12)).