Discrete Structure · Unit 6
Number Theory and Modular Arithmetic
Exam-focused notes for Number Theory and Modular Arithmetic (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Divisibility and division algorithm
- Greatest common divisor
- Euclidean algorithm
- Extended Euclidean algorithm
- Congruence modulo
- Arithmetic modulo m
- Multiplicative inverse
- Chinese Remainder Theorem
- Prime numbers and trial division
Chinese Remainder Theorem
State division theory.Add two integers 13578 and 45730 using Chinese Remainder Theorem.[2+8]
--- Division Algorithm (Division Theory): For any integer $a$ and any positive integer $n$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $$a = q \cdot n + r, \qquad 0 \leq r < n$$ where $q = \lfloor a/n \rfloor$ and $r = a \bmod...
Full solved answer →Solve the system of following congruences using Chinese Remainder theorem: x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7) [5]
$$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}$$ Remainders: $a1 = 2,\ a2 = 3,\ a3 = 2$ Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ The moduli are pairwise coprime, so CRT guarantees a unique solution modulo their product. --- $$M = 3 \t...
Full solved answer →How do you solve computer arithmetic with large integers using Chinese remainder theorem? Give an example. [5]
Modern computers have a fixed word size (e.g., 32-bit or 64-bit). When performing arithmetic on very large integers, the numbers may exceed the machine's word size, causing overflow. The Chinese Remainder Theorem (CRT) provides an elegant solution by breaki...
Full solved answer →Extended Euclidean algorithm
Find the multiplicative inverse of 6 in $\mathbb{Z}_{25}$ using Extended Euclidean Algorithm. [5]
- Modulus: $n = 25$ - Element whose inverse is sought: $a = 6$ - Ring: $\mathbb{Z}{25}$ - Goal: find $x$ such that $6x \equiv 1 \pmod{25}$ $$25 = 4 \times 6 + 1$$ $$6 = 6 \times 1 + 0$$ So $\gcd(25, 6) = 1$. Since the gcd is $1$, the inverse exists. From th...
Full solved answer →Arithmetic modulo m
Compute the value of $8 \text{ MOD } 8$, $-9 \text{ MOD } 4$, $7 \text{ MOD } 17$, $6 \text{ MOD } 7$ and $-8 \text{ MOD } 3$. [5]
Expressions to evaluate: - $8 \bmod 8$ - $-9 \bmod 4$ - $7 \bmod 17$ - $6 \bmod 7$ - $-8 \bmod 3$ For integers $a$ and modulus $b 0$: $$a \bmod b = a - b \times \left\lfloor \frac{a}{b} \right\rfloor$$ This yields a result satisfying $0 \le (a \bmod b) < b$...
Full solved answer →What is arithmetic modulo $m$? Use the definition of addition and multiplication in $\mathbb{Z}m$ to find $7 +{11} 9$ and $7 *_{11} 9$. [5]
Given data: - Modulus: $m = 11$ - Set: $\mathbb{Z}{11} = \{0, 1, 2, \ldots, 10\}$ - Compute $7 +{11} 9$ - Compute $7 {11} 9$ All required data present. --- Arithmetic modulo m is arithmetic carried out on the finite set $$\mathbb{Z}m = \{0, 1, 2, \ldots, m-...
Full solved answer →Congruence modulo
What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5. [5]
- Check 1: Is $20 \equiv 8 \pmod{6}$? - Check 2: Is $25 \equiv 17 \pmod{5}$? All values present; no missing data. Two integers $a$ and $b$ are congruent modulo $n$ (written $a \equiv b \pmod{n}$) if $n$ divides their difference: $$a \equiv b \pmod{n} \iff n...
Full solved answer →Prime numbers and trial division
Explain trial division with example? Using trial division, show that 101 is prime. [5]
- Number to test: $n = 101$ - Method required: trial division - Marks: 5 Trial division is a primality-testing method. To determine whether an integer $n 1$ is prime, we attempt to divide $n$ by successive integers starting from $2$. If any of them divides ...
Full solved answer →Euclidean algorithm
Explain Euclidean algorithm. Use Euclidean algorithm to find the greatest common divisor of 414 and 662. [5]
- Two integers: $414$ and $662$. - Task: find $\gcd(414, 662)$ using the Euclidean algorithm. The Euclidean Algorithm finds the Greatest Common Divisor (GCD) of two integers using the division property: If $a = b \cdot q + r$ (where $0 \le r < b$), then $\g...
Full solved answer →Make Unit 6 stick
Practice BIT152 with flashcards & quizzes