Discrete Structures · Unit 2 · 6 hrs
Integers and Matrices
Exam-focused notes for Integers and Matrices (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 11 solved past questions from this unit.
What this unit covers
- Integers
- Integers and Division
- Primes and Greatest Common Divisor
- Extended Euclidean Algorithm
- Integers and Algorithms
- Applications of Number Theory (Linear Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)
- Matrices
- Zero-One Matrices
- Boolean Matrix Operations
Extended Euclidean Algorithm
Find the GCD of 12 and 16 using Extended Euclidean Algorithm. [5]
- $a = 16$, $b = 12$ (arranged so larger is first) - Goal: find $\gcd(12,16)$ and integers $s, t$ such that $\gcd = s\cdot 12 + t\cdot 16$ --- Step Division Equation -------------------------- 1 $16 \div 12$ $16 = 1 \times 12 + 4$ 2 $12 \div 4$ $12 = 3 \tim...
Full solved answer →Find the multiplicative inverse of 4 in $\mathbb{Z}_{11}$ using extended euclidean algorithm. [5]
- Modulus: $n = 11$ - Element: $a = 4$ - Goal: find $x$ such that $4x \equiv 1 \pmod{11}$ We seek integers $s, t$ satisfying: $$s \cdot 4 + t \cdot 11 = \gcd(4, 11)$$ Since $\gcd(4,11) = 1$, the inverse exists, and $s \bmod 11$ is the inverse of 4. Step Div...
Full solved answer →Find the GCD of 24 and 32 using Extended Euclidean algorithm. [5]
- $a = 32$, $b = 24$ (arrange larger first) - Goal: find $\gcd(24, 32)$ and Bezout coefficients $s, t$ such that $\gcd = s \cdot a + t \cdot b$. Step Equation Quotient Remainder ------------------------------------- 1 $32 = 1 \cdot 24 + 8$ 1 8 2 $24 = 3 \cd...
Full solved answer →Boolean Matrix Operations
Discuss about meet and join operation between Boolean matrices. What are the values of 5 mod 75 and -5 mod 77? [5]
- Boolean matrices: entries from $\{0, 1\}$. - Modular values to compute: $5 \bmod 75$ and $-5 \bmod 77$. No matrices are supplied for the meet/join, so an illustrative example is used. --- A Boolean (zero-one) matrix has all entries in $\{0,1\}$. Meet and ...
Full solved answer →Applications of Number Theory
Using Chinese remainder theorem solve the following congruences.x = 1 (MOD 3), x = 3 (MOD 5), x = 6 (MOD 7) [5]
System of congruences: $$x \equiv 1 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$$ - Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ - Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ --- $3, 5, 7$ are distinct primes, so they are pairwise coprime. CRT guarantees ...
Full solved answer →Use Chinese remainder Theorem to find the value of x such that x = 0 (MOD 2), x = 2 (MOD 3), x = 3 (MOD 5). [5]
$$x \equiv 0 \pmod 2, \quad x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5$$ Moduli: $m1=2,\ m2=3,\ m3=5$. Residues: $a1=0,\ a2=2,\ a3=3$. $\gcd(2,3)=\gcd(2,5)=\gcd(3,5)=1$, so CRT applies. $$m = 2\times3\times5 = 30$$ $$M1=\frac{30}{2}=15,\quad M2=\frac{30}{...
Full solved answer →Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.[10]
$$x \equiv 1 \pmod 3,\quad x \equiv 1 \pmod 4,\quad x \equiv 1 \pmod 5,\quad x \equiv 0 \pmod 7$$ Moduli: $m1=3,\ m2=4,\ m3=5,\ m4=7$ Remainders: $a1=1,\ a2=1,\ a3=1,\ a4=0$ All pairs $(3,4),(3,5),(3,7),(4,5),(4,7),(5,7)$ have gcd $=1$, so a unique solution...
Full solved answer →Find the values of x such that x = 1 (mod 5) and x = 2 (mod 7) using Chinese remainder theorem. [5]
$$x \equiv 1 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$ So $a1 = 1$, $m1 = 5$; $a2 = 2$, $m2 = 7$. $\gcd(5, 7) = 1$, so CRT gives a unique solution mod $m = 5 \times 7 = 35$. $$m = 35$$ $$M1 = \frac{35}{5} = 7, \qquad M2 = \frac{35}{7} = 5$$ Find $y1$ with $M1 y1 \...
Full solved answer →Integers and Division
Find the value of $-2 \bmod 3$ and $3153^{15} \bmod 5$. Illustrate an example to show the join operation between any two Boolean matrices. [5]
- Expression 1: $-2 \bmod 3$ - Expression 2: $3153^{15} \bmod 5$ (the garbled text "3153^{15}315" is read as $3153^{15}$) - Task 3: Illustrate the join operation between two Boolean (zero-one) matrices with an example. --- Definition: For integer $a$ and po...
Full solved answer →What is congruent modulo? Determine whether 37 is congruent to 3 modulo 7 and whether -29 is congruent to 5 modulo 17. [5]
- Check 1: Is $37 \equiv 3 \pmod{7}$? - Check 2: Is $-29 \equiv 5 \pmod{17}$? If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is congruent to $b$ modulo $m$ if $m$ divides $(a - b)$. Notation: $$a \equiv b \pmod{m}$$ If they are not cong...
Full solved answer →Zero-One Matrices
Define zero-one matrix. Explain the types of function. [5]
--- Definition: A zero-one matrix (also called a Boolean matrix) is a matrix whose entries belong only to the Boolean domain {0, 1}. That is, every element of the matrix is either 0 or 1. Boolean matrices are used to represent binary relations between a pai...
Full solved answer →Make Unit 2 stick
Practice CSC165 with flashcards & quizzes