MATH 240 EXAM QUESTIONS AND
ANSWERS 100% PASS
Euclid's Algorithm - ✔✔If b = ax + r (a,b,x,r ∈ ; 0 < r < a) then gcd(b,a) = gcd(r,a)
Let a and b be integers. What numbers can be written as ma + nb (m,n ∈ ℤ) ? - ✔✔x =
ma + nb ⇒ gcd(a,b) | x
When are a,b∈ℤ relatively prime? - ✔✔gcd(a,b) = 1
Fermat's Little Theorem - ✔✔For any prime n and integer a, aⁿ≡a (mod n)
Fundamental Theorem of Arithmetic - ✔✔Every positive integer can be written as the
product of primes and this factorization is unique up to the order of the prime factors
When is x invertible mod m (x,m∈∈ℤ)? - ✔✔xy ≡ 1 (mod m) ⟺ gcd(x,m) = 1
Permutations - ✔✔A permutation of a set X of size n is a bijection f: X → X. X has are n!
permutations.
k-subset of an n-set - ✔✔Ordered: n(n-1)...(n-k+1) = n!/(n-k)!
100% Pass Guarantee Katelyn Whitman All Rights Reserved © 2025 1
, Unordered: Given a k-set, there are k! ways of ordering it. Thus, (# ordered sets)/(#
orderings/set) = # unordered. (n!/(n-k)!)/k! = n!/(k!(n-k)!)
How many ways are there to arrange an n-set around a circle? - ✔✔n!/n = (n-1)!
Principle of Inclusion-Exclusion - ✔✔|∪Ai| = ∑|Ai| - ∑|Ai∩Aj| + - ... + (-
1)ⁿ⁻¹|A₁∩A₂...∩An|
Erdos-Ko-Rado Theorem - ✔✔If F is an intersecting family of k-subsets of [n], n ≥ 2k,
|F| ≤ (n-1)!/((k-1)!(n-k)!)
What is the largest intersecting family of an n-set? - ✔✔The collection of all subsets
containing some fixed element, F. |F| = 2ⁿ⁻¹
Given n people, where everyone shakes hands with everyone else exactly once, how
many handshakes occur? - ✔✔Let each person be a node, and each handshake be an
edge. Then this is a complete graph on n vertices, Kn, so there are n(n-1)/2 handshakes.
Walk - ✔✔Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge
Path - ✔✔Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge, vi ≠ vj if i ≠ j
Closed walk - ✔✔Sequence v₀,v₁,....vk of vertices such that vi, v(i+1) share an edge, and
v₀ = vk
Euler Tour - ✔✔Sequence v₀,v₁,....vk of vertices in a graph G = (V,E) such that vi, v(i+1)
share an edge, v₀ = vk, and every edge in E is used exactly once
100% Pass Guarantee Katelyn Whitman All Rights Reserved © 2025 2
ANSWERS 100% PASS
Euclid's Algorithm - ✔✔If b = ax + r (a,b,x,r ∈ ; 0 < r < a) then gcd(b,a) = gcd(r,a)
Let a and b be integers. What numbers can be written as ma + nb (m,n ∈ ℤ) ? - ✔✔x =
ma + nb ⇒ gcd(a,b) | x
When are a,b∈ℤ relatively prime? - ✔✔gcd(a,b) = 1
Fermat's Little Theorem - ✔✔For any prime n and integer a, aⁿ≡a (mod n)
Fundamental Theorem of Arithmetic - ✔✔Every positive integer can be written as the
product of primes and this factorization is unique up to the order of the prime factors
When is x invertible mod m (x,m∈∈ℤ)? - ✔✔xy ≡ 1 (mod m) ⟺ gcd(x,m) = 1
Permutations - ✔✔A permutation of a set X of size n is a bijection f: X → X. X has are n!
permutations.
k-subset of an n-set - ✔✔Ordered: n(n-1)...(n-k+1) = n!/(n-k)!
100% Pass Guarantee Katelyn Whitman All Rights Reserved © 2025 1
, Unordered: Given a k-set, there are k! ways of ordering it. Thus, (# ordered sets)/(#
orderings/set) = # unordered. (n!/(n-k)!)/k! = n!/(k!(n-k)!)
How many ways are there to arrange an n-set around a circle? - ✔✔n!/n = (n-1)!
Principle of Inclusion-Exclusion - ✔✔|∪Ai| = ∑|Ai| - ∑|Ai∩Aj| + - ... + (-
1)ⁿ⁻¹|A₁∩A₂...∩An|
Erdos-Ko-Rado Theorem - ✔✔If F is an intersecting family of k-subsets of [n], n ≥ 2k,
|F| ≤ (n-1)!/((k-1)!(n-k)!)
What is the largest intersecting family of an n-set? - ✔✔The collection of all subsets
containing some fixed element, F. |F| = 2ⁿ⁻¹
Given n people, where everyone shakes hands with everyone else exactly once, how
many handshakes occur? - ✔✔Let each person be a node, and each handshake be an
edge. Then this is a complete graph on n vertices, Kn, so there are n(n-1)/2 handshakes.
Walk - ✔✔Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge
Path - ✔✔Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge, vi ≠ vj if i ≠ j
Closed walk - ✔✔Sequence v₀,v₁,....vk of vertices such that vi, v(i+1) share an edge, and
v₀ = vk
Euler Tour - ✔✔Sequence v₀,v₁,....vk of vertices in a graph G = (V,E) such that vi, v(i+1)
share an edge, v₀ = vk, and every edge in E is used exactly once
100% Pass Guarantee Katelyn Whitman All Rights Reserved © 2025 2
