DIVISION AND EUCLIDEAN ALGORITHMS

# DIVISION AND EUCLIDEAN ALGORITHMS ## Objectifs et prérequis This chapter aims to provide a rigorous foundation in number theory essential for further mathematical study. Students will master the concepts of divisibility, greatest common divisor (GCD), least common multiple (LCM), prime factorization, and their applications in solving linear Diophantine equations, modular arithmetic, and congruences. The Euclidean algorithm will be developed as a computational tool for finding GCDs and solving Diophantine equations. Students will learn to represent integers in different bases (binary, octal, hexadecimal) including fractional parts, and apply the Fundamental Theorem of Arithmetic to analyze number structure. The Chinese Remainder Theorem and Fermat’s Little Theorem will be introduced as powerful tools for solving systems of congruences and simplifying modular exponentiation. **Prerequisites**: Proficiency in basic arithmetic operations, understanding of integers and their properties, familiarity with algebraic manipulation, and knowledge of set notation and logical implication. Comfort with fractions and decimals is assumed. --- ## I. The Greatest Common Divisor (gcd) and Least Common Multiple (LCM) of Integers ### Definition and Properties The **greatest common divisor** of two integers $a$ and $b$, not both zero, denoted $\gcd(a,b)$, is the largest positive integer that divides both $a$ and $b$. The **least common multiple** of two non-zero integers $a$ and $b$, denoted $\operatorname{lcm}(a,b)$, is the smallest positive integer that is divisible by both $a$ and $b$. > **Key Property**: For any two non-zero integers $a$ and $b$, > $$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |a \cdot b|$$ This identity holds because the product of the GCD and LCM captures the full prime factorization of both numbers without overlap. ### Examples **Example 1**: Find $\gcd(48, 18)$ and $\operatorname{lcm}(48, 18)$. Prime factorizations: $48 = 2^4 \cdot 3^1$ $18 = 2^1 \cdot 3^2$ $\gcd = 2^{\min(4,1)} \cdot 3^{\min(1,2)} = 2^1 \cdot 3^1 = 6$ $\operatorname{lcm} = 2^{\max(4,1)} \cdot 3^{\max(1,2)} = 2^4 \cdot 3^2 = 16 \cdot 9 = 144$ Check: $6 \cdot 144 = 864 = |48 \cdot 18|$ ✓ **Example 2**: $\gcd(0, 5) = 5$, since every integer divides 0, and the largest divisor of 5 is 5. $\operatorname{lcm}(0, 5)$ is undefined (by convention, LCM is defined only for non-zero integers). ### Exercises and Solutions **Exercise 1**: Compute $\gcd(84, 36)$ and $\operatorname{lcm}(84, 36)$. *Solution*: $84 = 2^2 \cdot 3 \cdot 7$ $36 = 2^2 \cdot 3^2$ $\gcd = 2^2 \cdot 3^1 = 4 \cdot 3 = 12$ $\operatorname{lcm} = 2^2 \cdot 3^2 \cdot 7 = 4 \cdot 9 \cdot 7 = 252$ Verification: $12 \cdot 252 = 3024 = |84 \cdot 36|$ ✓ **Exercise 2**: If $\gcd(a,b) = 12$ and $\operatorname{lcm}(a,b) = 360$, find $a \cdot b$. *Solution*: Using $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |a \cdot b|$, $|a \cdot b| = 12 \cdot 360 = 4320$ Thus, $a \cdot b = \pm 4320$. Since $a,b$ are integers, product is $4320$ or $-4320$. Typically we consider positive unless specified. --- ## II. Bases Two, Eight, and Sixteen ### Definition and Representation Integers can be represented in any base $b \geq 2$ using digits $0,1,\dots,b-1$. The value of a number $(d_n d_{n-1} \dots d_1 d_0)_b$ is: $$\sum_{i=0}^{n} d_i \cdot b^i$$ - **Base 2 (binary)**: digits $\{0,1\}$ - **Base 8 (octal)**: digits $\{0,1,2,3,4,5,6,7\}$ - **Base 16 (hexadecimal)**: digits $\{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\}$ where $A=10, B=11, \dots, F=15$ > **Conversion Rule**: To convert from base $b$ to base 10, expand using powers of $b$. > To convert from base 10 to base $b$, repeatedly divide by $b$ and collect remainders in reverse order. ### Examples **Example 1**: Convert $(1101)_2$ to base 10. $$1\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 8 + 4 + 0 + 1 = 13_{10}$$ **Example 2**: Convert $27_{10}$ to octal. $27 \div 8 = 3$ remainder $3$ $3 \div 8 = 0$ remainder $3$ Reading remainders backwards: $(33)_8$ Check: $3\cdot8^1 + 3\cdot8^0 = 24 + 3 = 27$ ✓ **Example 3**: Convert $255_{10}$ to hexadecimal. $255 \div 16 = 15$ remainder $15$ → $F$ $15 \div 16 = 0$ remainder $15$ → $F$ So $(FF)_{16}$ Check: $15\cdot16 + 15 = 240 + 15 = 255$ ✓ ### Exercises and Solutions **Exercise 1**: Convert $(101101)_2$ to decimal. *Solution*: $1\cdot2^5 + 0\cdot2^4 + 1\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 32 + 0 + 8 + 4 + 0 + 1 = 45_{10}$ **Exercise 2**: Convert $156_{10}$ to hexadecimal. *Solution*: $156 \div 16 = 9$ remainder $12$ → $C$ $9 \div 16 = 0$ remainder $9$ So $(9C)_{16}$ Check: $9\cdot16 + 12 = 144 + 12 = 156$ ✓ **Exercise 3**: Convert $(3A7)_{16}$ to binary. *Solution*: Convert each hex digit to 4-bit binary: $3 = 0011$, $A = 1010$, $7 = 0111$ So $(0011\ 1010\ 0111)_2 = (1110100111)_2$ (leading zeros omitted) Alternatively, convert to decimal first: $3\cdot16^2 + 10\cdot16^1 + 7\cdot16^0 = 768 + 160 + 7 = 935_{10}$ Then $935_{10}$ to binary: $935 \div 2 = 467$ r1 $467 \div 2 = 233$ r1 $233 \div 2 = 116$ r1 $116 \div 2 = 58$ r0 $58 \div 2 = 29$ r0 $29 \div 2 = 14$ r1 $14 \div 2 = 7$ r0 $7 \div 2 = 3$ r1 $3 \div 2 = 1$ r1 $1 \div 2 = 0$ r1 Reading backwards: $1110100111_2$ ✓ --- ## III. Bases Having a Radix Point ### Definition and Representation Numbers with fractional parts can be represented in base $b$ using a **radix point** (analogous to decimal point). A number $(d_n \dots d_0 . d_{-1} d_{-2} \dots d_{-m})_b$ has value: $$\sum_{i=-m}^{n} d_i \cdot b^i$$ Digits to the right of the radix point represent negative powers of $b$. > **Conversion Rule**: > - Integer part: convert as before (repeated division). > - Fractional part: repeatedly multiply by $b$, take integer part as next digit, repeat with fractional part. ### Examples **Example 1**: Convert $(10.11)_2$ to decimal. Integer part: $1\cdot2^1 + 0\cdot2^0 = 2$ Fractional part: $1\cdot2^{-1} + 1\cdot2^{-2} = 0.5 + 0.25 = 0.75$ Total: $2.75_{10}$ **Example 2**: Convert $0.625_{10}$ to binary. $0.625 \times 2 = 1.25$ → digit $1$, remainder $0.25$ $0.25 \times 2 = 0.5$ → digit $0$, remainder $0.5$ $0.5 \times 2 = 1.0$ → digit $1$, remainder $0$ So $(0.101)_2$ Check: $1\cdot2^{-1} + 0\cdot2^{-2} + 1\cdot2^{-3} = 0.5 + 0 + 0.125 = 0.625$ ✓ **Example 3**: Convert $(0.3)_{10}$ to octal. $0.3 \times 8 = 2.4$ → digit $2$, remainder $0.4$ $0.4 \times 8 = 3.2$ → digit $3$, remainder $0.2$ $0.2 \times 8 = 1.6$ → digit $1$, remainder $0.6$ $0.6 \times 8 = 4.8$ → digit $4$, remainder $0.8$ $0.8 \times 8 = 6.4$ → digit $6$, remainder $0.4$ (repeats) So $(0.23146\dots)_8$ — a repeating octal fraction. ### Exercises and Solutions **Exercise 1**: Convert $(11.01)_2$ to decimal. *Solution*: Integer: $1\cdot2^1 + 1\cdot2^0 = 2 + 1 = 3$ Fraction: $0\cdot2^{-1} + 1\cdot2^{-2} = 0 + 0.25 = 0.25$ Total: $3.25_{10}$ **Exercise 2**: Convert $0.375_{10}$ to octal. *Solution*: $0.375 \times 8 = 3.0$ → digit $3$, remainder $0$ So $(0.3)_8$ Check: $3\cdot8^{-1} = 3/8 = 0.375$ ✓ **Exercise 3**: Convert $(0.1)_{2}$ to decimal. *Solution*: $1\cdot2^{-1} = 0.5_{10}$ This is a key example: $0.1_2 = 0.5_{10}$, not $0.1_{10}$. --- ## IV. Relatively Prime Numbers and Prime Numbers ### Definitions Two integers $a$ and $b$ are **relatively prime** (or **coprime**) if $\gcd(a,b) = 1$. A **prime number** is an integer $p > 1$ whose only positive divisors are $1$ and $p$. An integer $n > 1$ that is not prime is **composite**. > **Key Property**: If $a$ and $b$ are relatively prime, then there exist integers $x,y$ such that $ax + by = 1$ (Bézout’s identity, a consequence of the Euclidean algorithm). ### Examples **Example 1**: $\gcd(8, 15) = 1$ → $8$ and $15$ are relatively prime. Indeed, $8\cdot2 + 15\cdot(-1) = 16 - 15 = 1$. **Example 2**: $\gcd(12, 18) = 6 \neq 1$ → not relatively prime. **Example 3**: Prime numbers less than 20: $2,3,5,7,11,13,17,19$. Note: $2$ is the only even prime. ### Exercises and Solutions **Exercise 1**: Are $21$ and $55$ relatively prime? *Solution*: $21 = 3 \cdot 7$ $55 = 5 \cdot 11$ No common prime factors → $\gcd = 1$ → Yes, relatively prime. **Exercise 2**: Find all primes $p$ such that $p^2 + 2$ is also prime. *Solution*: Try small primes: $p=2$: $4+2=6$ → not prime $p=3$: $9+2=11$ → prime $p=5$: $25+2=27$ → not prime $p=7$: $49+2=51=3\cdot17$ → not prime For $p>3$, $p$ is odd → $p \equiv \pm1 \mod 6$ → $p^2 \equiv 1 \mod 3$ → $p^2+2 \equiv 0 \mod 3$ → divisible by 3 and $>3$ → composite. Only $p=3$ works. **Exercise 3**: Show that if $a$ and $b$ are relatively prime, then $\gcd(a^2, b^2) = 1$. *Solution*: If $\gcd(a,b)=1$, then $a$ and $b$ share no prime factors. Then $a^2$ and $b^2$ also share no prime factors → $\gcd(a^2,b^2)=1$. Alternatively, by Bézout: $ax+by=1$ → square both sides: $a^2x^2 + b^2y^2 + 2abxy = 1$ → not directly helpful, but prime factor argument is sufficient. --- ## V. The Theorem $a/b$ and $a/c \Rightarrow a/(bx \pm cy)$ and the Division Algorithm ### The Divisibility Theorem > **Theorem**: If $a \mid b$ and $a \mid c$, then $a \mid (bx \pm cy)$ for any integers $x,y$. **Proof**: Since $a \mid b$, $b = a k_1$ for some integer $k_1$. Since $a \mid c$, $c = a k_2$ for some integer $k_2$. Then $bx \pm cy = (a k_1)x \pm (a k_2)y = a(k_1 x \pm k_2 y)$. Since $k_1 x \pm k_2 y$ is an integer, $a \mid (bx \pm cy)$. ### The Division Algorithm > **Division Algorithm**: For any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that > $$a = bq + r \quad \text{and} \quad 0 \leq r < b$$ This is foundational for the Euclidean algorithm. ### Examples **Example 1**: Apply division algorithm to $a = 29$, $b = 5$. $29 = 5 \cdot 5 + 4$ → $q=5$, $r=4$ (since $0 \leq 4 < 5$) **Example 2**: $a = -17$, $b = 5$. We need $0 \leq r < 5$. $-17 = 5 \cdot (-4) + 3$ → because $5 \cdot (-4) = -20$, $-20 + 3 = -17$, and $0 \leq 3 < 5$ → $q=-4$, $r=3$ (Not $q=-3$, $r=-2$ because remainder must be non-negative.) **Example 3**: Use the theorem: if $6 \mid 18$ and $6 \mid 24$, then $6 \mid (18\cdot3 - 24\cdot2)$. $18\cdot3 = 54$, $24\cdot2=48$, $54-48=6$, and $6 \mid 6$ ✓ ### Exercises and Solutions **Exercise 1**: Use the division algorithm to write $a = -47$, $b = 9$ in the form $a = bq + r$, $0 \leq r < 9$. *Solution*: $-47 \div 9 = -5.222...$ → try $q = -6$: $9 \cdot (-6) = -54$, then $-47 - (-54) = 5$ → $r=5$ Check: $-47 = 9 \cdot (-6) + 5$, $0 \leq 5 < 9$ ✓ So $q=-6$, $r=5$ **Exercise 2**: If $7 \mid 35$ and $7 \mid 49$, show that $7 \mid (35\cdot4 + 49\cdot(-3))$. *Solution*: $35\cdot4 = 140$, $49\cdot(-3) = -147$, sum = $140 - 147 = -7$ $7 \mid -7$ since $-7 = 7 \cdot (-1)$ ✓ **Exercise 3**: Prove that if $a \mid b$ and $b \mid c$, then $a \mid c$. *Solution*: $a \mid b$ ⇒ $b = a k$ $b \mid c$ ⇒ $c = b m = (a k) m = a (k m)$ Since $k m$ is integer, $a \mid c$ ✓ (Note: This is a special case of the theorem with $x=0$, $y=m$, and using transitivity.) --- ## VI. Fundamental Theorem of Arithmetic (FTA) and Representation in Different Bases ### Fundamental Theorem of Arithmetic > **Fundamental Theorem of Arithmetic (FTA)**: Every integer $n > 1$ can be expressed uniquely as a product of prime numbers, up to the order of the factors. > That is, $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where $p_i$ are distinct primes and $e_i \geq 1$ integers, and this representation is unique. > **Note**: Proofs are not required, but the theorem underpins GCD, LCM, and prime-based reasoning. ### Representation of Integers in Different Bases (Revisited via FTA) While base representation is positional, FTA ensures that the prime factorization of a number is unique, which underlies why GCD and LCM computations via prime factors are well-defined and consistent across bases. ### Examples **Example 1**: Prime factorization of $360$. $360 = 36 \cdot 10 = (6^2) \cdot (2\cdot5) = (2\cdot3)^2 \cdot 2 \cdot 5 = 2^2 \cdot 3^2 \cdot 2 \cdot 5 = 2^3 \cdot 3^2 \cdot 5^1$ Unique: $2^3 \cdot 3^2 \cdot 5$ **Example 2**: Use FTA to find $\gcd(100, 150)$ and $\operatorname{lcm}(100, 150)$. $100 = 2^2 \cdot 5^2$ $150 = 2^1 \cdot 3^1 \cdot 5^2$ $\gcd = 2^{\min(2,1)} \cdot 3^{\min(0,1)} \cdot 5^{\min(2,2)} = 2^1 \cdot 3^0 \cdot 5^2 = 2 \cdot 1 \cdot 25 = 50$ $\operatorname{lcm} = 2^{\max(2,1)} \cdot 3^{\max(0,1)} \cdot 5^{\max(2,2)} = 2^2 \cdot 3^1 \cdot 5^2 = 4 \cdot 3 \cdot 25 = 300$ Check: $50 \cdot 300 = 15000 = |100 \cdot 150|$ ✓ ### Exercises and Solutions **Exercise 1**: Write the prime factorization of $840$. *Solution*: $840 = 84 \cdot 10 = (7 \cdot 12) \cdot (2 \cdot 5) = 7 \cdot (2^2 \cdot 3) \cdot 2 \cdot 5 = 2^3 \cdot 3 \cdot 5 \cdot 7$ So $2^3 \cdot 3^1 \cdot 5^1 \cdot 7^1$ **Exercise 2**: If $n = 2^4 \cdot 3^2 \cdot 5^1 \cdot 7^3$, find the number of positive divisors of $n$. *Solution*: Number of divisors = $(4+1)(2+1)(1+1)(3+1) = 5 \cdot 3 \cdot 2 \cdot 4 = 120$ **Exercise 3**: Show that $\sqrt{2}$ is irrational using FTA. *Solution*: Assume $\sqrt{2} = p/q$ in lowest terms → $2 = p^2/q^2$ → $2q^2 = p^2$. By FTA, prime factorization of $p^2$ has even exponents. Left side: $2q^2$ → exponent of 2 is $1 + 2k$ (odd) if $q$ has $2^k$. Contradiction: left has odd exponent of 2, right has even → impossible. Thus $\sqrt{2}$ irrational. (This is a classic application.) --- ## VII. Solving Linear Diophantine Equations ($ax + by = c$) ### Definition and Existence Condition A **linear Diophantine equation** in two variables is of the form: $$ax + by = c$$ where $a,b,c$ are integers, and we seek integer solutions $x,y \in \mathbb{Z}$. > **Existence Theorem**: The equation $ax + by = c$ has integer solutions if and only if $\gcd(a,b) \mid c$. If solutions exist, there are infinitely many, given by: If $(x_0, y_0)$ is a particular solution, then general solution is: $$x = x_0 + \frac{b}{\gcd(a,b)} t, \quad y = y_0 - \frac{a}{\gcd(a,b)} t, \quad t \in \mathbb{Z}$$ ### Method: Extended Euclidean Algorithm Use the Euclidean algorithm to find $\gcd(a,b)$ and express it as $ax + by = \gcd(a,b)$, then scale to match $c$. ### Examples **Example 1**: Solve $6x + 9y = 15$. $\gcd(6,9) = 3$, and $3 \mid 15$ → solutions exist. First, solve $6x + 9y = 3$. Euclidean algorithm: $9 = 6 \cdot 1 + 3$ $6 = 3 \cdot 2 + 0$ → $\gcd=3$ Back-substitute: $3 = 9 - 6 \cdot 1$ → so $x=-1$, $y=1$ for $6x+9y=3$ Multiply by $5$: $6(-5) + 9(5) = -30 + 45 = 15$ → particular solution: $x_0=-5$, $y_0=5$ General solution: $x = -5 + \frac{9}{3}t = -5 + 3t$ $y = 5 - \frac{6}{3}t = 5 - 2t$, $t \in \mathbb{Z}$ Check: $t=0$: $-30+45=15$; $t=1$: $6(-2)+9(3)=-12+27=15$ ✓ **Example 2**: Solve $4x + 6y = 7$. $\gcd(4,6)=2$, but $2 \nmid 7$ → no integer solutions. **Example 3**: Solve $3x + 5y = 1$. $\gcd(3,5)=1 \mid 1$ → solutions exist. Euclidean: $5 = 3 \cdot 1 + 2$ $3 = 2 \cdot 1 + 1$ $2 = 1 \cdot 2 + 0$ Back: $1 = 3 - 2 \cdot 1$ $2 = 5 - 3 \cdot 1$ → $1 = 3 - (5 - 3) = 2\cdot3 - 1\cdot5$ So $x_0=2$, $y_0=-1$ for $3x+5y=1$ General solution: $x = 2 + 5t$ $y = -1 - 3t$, $t \in \mathbb{Z}$ ### Exercises and Solutions **Exercise 1**: Solve $8x + 12y = 4$. *Solution*: $\gcd(8,12)=4$, $4 \mid 4$ → solutions exist. Solve $8x+12y=4$ → divide by 4: $2x+3y=1$ Solve $2x+3y=1$: $3 = 2\cdot1 + 1$ $2 = 1\cdot2 + 0$ $1 = 3 - 2\cdot1$ → so $x=-1$, $y=1$ for $2x+3y=1$ Thus for original: multiply by 4? Wait: we divided by 4, so solution to $2x+3y=1$ is $x=-1,y=1$ → then $8(-1)+12(1)=-8+12=4$ ✓ So particular: $x_0=-1$, $y_0=1$ General: $x = -1 + \frac{12}{4}t = -1 + 3t$ $y = 1 - \frac{8}{4}t = 1 - 2t$, $t \in \mathbb{Z}$ **Exercise 2**: Solve $15x + 25y = 10$. *Solution*: $\gcd(15,25)=5$, $5 \mid 10$ → solutions exist. Divide by 5: $3x+5y=2$ Solve $3x+5y=1$: from earlier, $x=2,y=-1$ So for $=2$: $x_0=4$, $y_0=-2$ General: $x = 4 + \frac{25}{5}t = 4 + 5t$ $y = -2 - \frac{15}{5}t = -2 - 3t$, $t \in \mathbb{Z}$ Check: $t=0$: $15\cdot4 + 25\cdot(-2)=60-50=10$ ✓ **Exercise 3**: Find all integer solutions to $7x - 11y = 29$. *Solution*: Rewrite as $7x + (-11)y = 29$ $\gcd(7,11)=1 \mid 29$ → solutions exist. Solve $7x - 11y = 1$ first. Euclidean: $11 = 7\cdot1 + 4$ $7 = 4\cdot1 + 3$ $4 = 3\cdot1 + 1$ $3 = 1\cdot3 + 0$ Back: $1 = 4 - 3\cdot1$ $3 = 7 - 4\cdot1$ → $1 = 4 - (7-4) = 2\cdot4 - 1\cdot7$ $4 = 11 - 7\cdot1$ → $1 = 2(11-7) - 7 = 2\cdot11 - 2\cdot7 - 7 = 2\cdot11 - 3\cdot7$ So $7(-3) + 11(2) = -21 + 22 = 1$ → thus $x=-3$, $y=2$ for $7x+11y=1$ But we have $7x -11y = 29$ → $7x + (-11)y = 29$ So from $7x + 11y' = 1$ with $y' = -y$, we have $x=-3$, $y'=2$ → $y = -2$ Thus particular solution to $7x -11y=1$: $x=-3$, $y=-2$? Check: $7(-3) -11(-2) = -21 +22=1$ ✓ So for $=29$: multiply by 29: $x_0 = -3\cdot29 = -87$, $y_0 = -2\cdot29 = -58$ Check: $7(-87) -11(-58) = -609 + 638 = 29$ ✓ General solution: $x = -87 + \frac{11}{1}t = -87 + 11t$ $y = -58 - \frac{7}{1}t = -58 - 7t$, $t \in \mathbb{Z}$ (Note: since $\gcd=1$, coefficients are $b/\gcd=11$, $-a/\gcd=-7$) --- ## VIII. Applications to Modular Arithmetic ### Definition For integers $a$, $b$, and $m > 0$, we say $a \equiv b \pmod{m}$ if $m \mid (a - b)$. This is read as “$a$ is congruent to $b$ modulo $m$”. > **Key Properties**: > - Reflexive: $a \equiv a \pmod{m}$ > - Symmetric: if $a \equiv b \pmod{m}$, then $b \equiv a \pmod{m}$ > - Transitive: if $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$ > - Compatible with addition/multiplication: if $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a+c \equiv b+d \pmod{m}$ and $ac \equiv bd \pmod{m}$ ### Examples **Example 1**: $17 \equiv 5 \pmod{6}$ because $17-5=12$, and $6 \mid 12$. **Example 2**: $-4 \equiv 2 \pmod{3}$ because $-4-2=-6$, $3 \mid -6$. **Example 3**: Compute $23 \mod 5$: $23 = 5\cdot4 + 3$ → $23 \equiv 3 \pmod{5}$ ### Exercises and Solutions **Exercise 1**: Reduce $47$ modulo $9$. *Solution*: $47 \div 9 = 5$ remainder $2$ → $47 \equiv 2 \pmod{9}$ (Or $47 - 5\cdot9 = 47-45=2$) **Exercise 2**: Solve $x \equiv 3 \pmod{4}$ and $x \equiv 1 \pmod{5}$ for $x \in \{0,1,\dots,19\}$. *Solution*: List numbers $\equiv 3 \pmod{4}$: $3,7,11,15,19$ Check which $\equiv 1 \pmod{5}$: $3\mod5=3$, $7\mod5=2$, $11\mod5=1$ → yes $15\mod5=0$, $19\mod5=4$ So $x=11$ is the solution in range. (We will generalize this with CRT.) **Exercise 3**: Compute $7^5 \mod 10$. *Solution*: $7^1 \equiv 7 \pmod{10}$ $7^2 = 49 \equiv 9 \pmod{10}$ $7^3 = 7\cdot9=63 \equiv 3 \pmod{10}$ $7^4 = 7\cdot3=21 \equiv 1 \pmod{10}$ $7^5 = 7\cdot1=7 \pmod{10}$ So $7^5 \equiv 7 \pmod{10}$ (Note: cycle length 4) ---