D421 Discrete Math: Functions and Relations - Set 3 - Part 2

Correct Answer: The largest integer dividing both

The GCD is the largest positive integer that divides both numbers without a remainder.

Correct Answer: 6

The common divisors of 12 and 18 are 1, 2, 3, and 6; the greatest is 6.

Correct Answer: The Euclidean algorithm

The Euclidean algorithm computes the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller.

Correct Answer: The smallest positive integer divisible by both

The LCM is the smallest positive integer that is a multiple of both numbers.

Correct Answer: An integer greater than 1 divisible only by 1 and itself

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself.

Correct Answer: The remainder when a is divided by b

The modulo operation a mod b gives the remainder after dividing a by b, central to modular arithmetic.

Correct Answer: 2

17 divided by 5 is 3 remainder 2, so 17 mod 5 = 2.

Correct Answer: Their difference is divisible by n

a ≡ b (mod n) means n divides a − b, so a and b leave the same remainder when divided by n.

Correct Answer: An equation defining each term using previous terms

A recurrence relation defines a sequence by expressing each term as a function of preceding terms, such as the Fibonacci relation.

Correct Answer: The sum of the two preceding terms

Each Fibonacci number is the sum of the two before it: F(n) = F(n−1) + F(n−2), starting from 0 and 1.

Correct Answer: 0, 1, 1, 2, 3, 5

Starting from 0 and 1, each subsequent number sums the previous two: 0, 1, 1, 2, 3, 5.

Correct Answer: The growth rate of an algorithm's running time

Big O notation describes the asymptotic upper bound on how an algorithm's resource use grows with input size.

Correct Answer: O(2^n)

Exponential growth O(2^n) grows faster than polynomial or logarithmic rates as n increases, making it the least efficient here.

Correct Answer: O(log n)

Logarithmic growth O(log n) increases very slowly with input size, making it the most efficient of these.

Correct Answer: n(a + l)/2

The sum of an arithmetic series is n times the average of the first and last terms: n(a + l)/2.

Correct Answer: a(r^n − 1)/(r − 1)

The sum of a finite geometric series is a(r^n − 1)/(r − 1), a standard closed-form formula.

Correct Answer: Defining a set by a property its members satisfy

Set-builder notation defines a set by a describing property, such as {x : x is an even integer}.

Correct Answer: Sets with no elements in common

Two sets are disjoint when their intersection is empty, sharing no common elements.

Correct Answer: |A| + |B| − |A ∩ B|

Inclusion-exclusion gives |A ∪ B| = |A| + |B| − |A ∩ B|, subtracting the overlap counted twice.

Correct Answer: 15

By inclusion-exclusion, |A ∪ B| = 10 + 8 − 3 = 15.