Divisibility, modular arithmetic, and prime numbers from an intro discrete mathematics course.
30 cards · basic cards · AI-written, checked twice. Edit anything.
- What does it mean for integer a to divide integer b?
- There exists an integer k such that b = ak.
- Notation: what does 'a | b' mean?
- a divides b.
- Is divisibility reflexive? Does a | a for all nonzero a?
- Yes, a = a * 1, so a divides itself.
- Is divisibility transitive? If a | b and b | c, does a | c?
- Yes, b = ak and c = bm for some integers k, m, so c = a(km).
- If a | b and a | c, what can you say about a | (b + c)?
- a divides (b + c), since b = ak and c = am implies b + c = a(k + m).
- Define the greatest common divisor (GCD) of two nonzero integers a and b.
- The largest positive integer that divides both a and b.
- What does gcd(a, b) = 1 mean?
- a and b are coprime (mutually prime).
- State Bezout's identity for integers a and b.
- There exist integers x and y such that ax + by = gcd(a, b).
- What is the Euclidean algorithm for computing gcd(a, b)?
- Repeatedly divide: gcd(a, b) = gcd(b, a mod b), until the remainder is 0.
- Define a prime number.
- An integer p > 1 with no positive divisors other than 1 and p itself.
- Define a composite number.
- An integer n > 1 that is not prime, i.e., has a divisor other than 1 and itself.
- State the Fundamental Theorem of Arithmetic.
- Every integer n > 1 can be uniquely factored as a product of primes, up to order.
- What does 'a ≡ b (mod n)' mean?
- n divides (a - b), or equivalently, a and b have the same remainder when divided by n.
- Is congruence modulo n reflexive? Does a ≡ a (mod n)?
- Yes, n | 0 = (a - a).
- Is congruence modulo n symmetric? If a ≡ b (mod n), does b ≡ a (mod n)?
- Yes, if n | (a - b), then n | (b - a).