Discrete Mathematics — Module 1
Number Theory & Relations — Practice Set with Solutions
1. Partial Order & POSET
Q1. Is R = 'divides' on A = {1, 2, 4, 8} a partial order? Verify all properties.
Solution:
• Reflexive: 1|1, 2|2, 4|4, 8|8 ✓
• Antisymmetric: If a|b and b|a then a = b. No two distinct elements divide each other here ✓
• Transitive: 1|2 and 2|4 → 1|4 ✓, 2|4 and 4|8 → 2|8 ✓
Result: Yes, (A, divides) is a POSET.
Q2. In A = {1, 2, 3, 6} with R = divides, are 2 and 3 comparable?
Solution: No. 2 does not divide 3, and 3 does not divide 2. They are INCOMPARABLE.
Q3. Find all pairs of comparable elements in A = {1, 2, 3, 6} with R = divides.
Solution: (1,2), (1,3), (1,6), (2,6), (3,6) — and reflexive pairs (1,1),(2,2),(3,3),(6,6).
2. Hasse Diagram
Q1. Draw the Hasse diagram for A = {1, 2, 3, 6, 12} with R = divides.
Solution:
Place: 12 at top, 6 and 4(=missing here, just 6) below, then 2 and 3, then 1 at bottom.
Edges (direct only, no transitive): 1→2, 1→3, 2→6, 3→6, 6→12
Remove: 1→6, 1→12, 2→12 (these are transitive, covered by chains)
Q2. In a Hasse diagram, why is the line 1→6 removed when 1→2→6 exists?
Solution: Hasse diagrams remove transitive edges to keep the diagram clean. Since 1→2 and 2→6 already
imply 1→6, drawing 1→6 directly is redundant.
3. Equivalence Relation & Equivalence Classes
Q1. Is R = 'same remainder mod 4' on A = {1,2,3,4,5,6,7,8} an equivalence relation?
Solution:
• Reflexive: Every number has same remainder as itself ✓
• Symmetric: If a ≡ b (mod 4) then b ≡ a (mod 4) ✓
• Transitive: If a ≡ b and b ≡ c (mod 4) then a ≡ c (mod 4) ✓
Result: Yes, it is an equivalence relation.
Q2. Find all equivalence classes for the above relation.
Solution:
[1] = [5] = {1, 5} — remainder 1
[2] = [6] = {2, 6} — remainder 2
[3] = [7] = {3, 7} — remainder 3
[4] = [8] = {4, 8} — remainder 0
Q3. Show that [3] = [7] in the above example.
Solution: 3 mod 4 = 3 and 7 mod 4 = 3. Same remainder, so they belong to the same class. Hence [3] = [7]
= {3, 7}.
4. Division Algorithm
Q1. Find q and r when a = 37, b = 6.
Solution: 37 = 6 × 6 + 1. So q = 6, r = 1.
Q2. Find q and r when a = 100, b = 13.
Solution: 100 = 13 × 7 + 9. So q = 7, r = 9. Check: 13×7 = 91, 91+9 = 100 ✓
Q3. Is 101 prime? Use the sqrt method.
Solution: sqrt(101) ≈ 10. Check primes 2, 3, 5, 7:
101/2 = no, 101/3 = no, 101/5 = no, 101/7 = no. So 101 is PRIME.
5. GCD & Euclidean Algorithm
Q1. Find GCD(84, 36) using Euclidean Algorithm.
Solution:
84 = 36 × 2 + 12
36 = 12 × 3 + 0
GCD(84, 36) = 12
Q2. Find GCD(105, 45).
Solution:
105 = 45 × 2 + 15
45 = 15 × 3 + 0
GCD(105, 45) = 15
Q3. Find GCD and LCM of 48 and 72 using prime factorization.
Solution: 48 = 24 × 3, 72 = 23 × 32
GCD = 23 × 3 = 24
LCM = 24 × 32 = 144
6. Fundamental Theorem of Arithmetic
Q1. Find prime factorization of 360.
Solution: 360 = 23 × 32 × 5
360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1
Q2. Find prime factorization of 252.
Solution: 252 = 22 × 32 × 7
252÷2=126, 126÷2=63, 63÷3=21, 21÷3=7, 7÷7=1
7. Linear Diophantine Equations
Q1. Does 5x + 10y = 15 have a solution? Find it.
Solution:
GCD(5,10) = 5. Does 5|15? Yes ✓
Divide by 5: x + 2y = 3. One solution: x=1, y=1
Check: 5(1) + 10(1) = 15 ✓
Q2. Solve 3x + 7y = 1 using Extended Euclidean.
Solution:
Forward: 7 = 3×2 + 1
Backward: 1 = 7 - 3×2
So x = -2, y = 1. Check: 3(-2) + 7(1) = -6+7 = 1 ✓
Q3. Solve 4x + 9y = 1.
Solution:
Forward: 9 = 4×2 + 1
Backward: 1 = 9 - 4×2
So x = -2, y = 1. Check: 4(-2) + 9(1) = -8+9 = 1 ✓
8. Linear Congruences
Q1. Solve 5x ≡ 3 (mod 7).
Solution:
GCD(5,7) = 1, 1|3 ✓
Find inverse of 5 mod 7: 5×3=15, 15 mod 7 = 1. Inverse = 3
x ≡ 3×3 = 9 ≡ 2 (mod 7)
Check: 5×2 = 10, 10 mod 7 = 3 ✓
Q2. Solve 6x ≡ 4 (mod 10).
Solution:
GCD(6,10) = 2, does 2|4? Yes ✓
Divide by 2: 3x ≡ 2 (mod 5)
Inverse of 3 mod 5: 3×2=6, 6 mod 5=1. Inverse = 2
x ≡ 2×2 = 4 (mod 5). So x = 4, 9, 14...
Q3. Does 4x ≡ 3 (mod 6) have a solution?
Solution: GCD(4,6) = 2. Does 2|3? No. So NO SOLUTION exists.
9. Chinese Remainder Theorem
Q1. Solve: x ≡ 2 (mod 3), x ≡ 3 (mod 5).
Solution:
GCD(3,5) = 1 ✓ (pairwise coprime)
M = 3×5 = 15
M1 = 15/3 = 5, M2 = 15/5 = 3
Inverse of 5 mod 3: 5 mod 3=2, 2×2=4, 4 mod 3=1. y1=2
Inverse of 3 mod 5: 3×2=6, 6 mod 5=1. y2=2
x = 2×5×2 + 3×3×2 = 20+18 = 38 mod 15 = 8
Check: 8 mod 3=2 ✓, 8 mod 5=3 ✓
Q2. Solve: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5).
Solution:
GCD(2,3)=1, GCD(3,5)=1, GCD(2,5)=1 ✓
M = 2×3×5 = 30
M1=15, M2=10, M3=6
y1: inverse of 15 mod 2 = inverse of 1 mod 2 = 1
y2: inverse of 10 mod 3 = inverse of 1 mod 3 = 1
y3: inverse of 6 mod 5 = inverse of 1 mod 5 = 1
x = 1×15×1 + 2×10×1 + 3×6×1 = 15+20+18 = 53 mod 30 = 23
Check: 23 mod 2=1 ✓, 23 mod 3=2 ✓, 23 mod 5=3 ✓
Q3. Solve: x ≡ 3 (mod 4), x ≡ 1 (mod 3).
Solution:
GCD(4,3)=1 ✓, M=12, M1=3, M2=4
y1: inverse of 3 mod 4: 3×3=9, 9 mod 4=1. y1=3
y2: inverse of 4 mod 3: 4 mod 3=1. y2=1
x = 3×3×3 + 1×4×1 = 27+4 = 31 mod 12 = 7
Check: 7 mod 4=3 ✓, 7 mod 3=1 ✓
End of Module 1 Practice Set — Good luck! ■