MAT102 Lecture 17B

$49 \equiv - 1 (\mod 10)$
$49 \equiv 9 (\mod 10)$
Definition
- $a \equiv b (\mod n) ⟺ n ∣ b - a$
Remainder
- $a \equiv b (\mod n)$ if they have the same remainder when you divide by $n$
- $49 \equiv 9 (\mod 10) \equiv 29 (\mod 10) \equiv 39 (\mod 10)$
Clock example
- 24 hours to 12 hours
- $49 \equiv 59 (\mod 10)$
- You can add and subtract $10$ anytime
- $49 \equiv 10 n (9) (\mod 10)$
- for $n \in N$
$52 (\mod 7)$
$7 \cdot 7 = 49$
$49 (\mod 7) = 0$
$49 + 3 (\mod 7) = 3$
1
- $4 x^{3} + 2 x + 1 \equiv 0 (\mod 5)$
- $5 ∣ 4 x^{3} + 2 x + 1$
- $4 (0)^{3} + 2 (0) + 1 = 1$
- $4 (1)^{3} + 2 (1) + 1 = 7 (\mod 5) = 2$
- $4 (2)^{3} + 2 (2) + 1 = 37 (\mod 5) = 2$
- $4 (3)^{3} + 2 (3) + 1 = 115 (\mod 5) = 0$
- $4 (4)^{3} + 2 (4) + 1 = 265 (\mod 5) = 0$
- $2$ solutions
- $5 ∣ 4 x^{3} + 2 x + 1$
- $5 k = 4 x^{3} + 2 x + 1$
- $5 k = x (4 x^{2} + 2) + 1$
- $4 \equiv - 1 (\mod 5)$
- $4 x^{3} + 2 x + 1 \equiv - x^{3} + 2 x + 1 (\mod 5)$
- You can always reduce:
  - $4 (27) + 2 (3) + 1 = 4 (2) + 2 (\mod 5)$
  - $27 (\mod 5) = 2$
  - So you can reduce it while doing these computations
- $x^{2} + 1 = 0$
  - No solutions to this equation
- $x^{2} + 1 \equiv 0 (\mod 2)$
  - $1$ solution
  - Input $2$ get $2 \equiv 0 (\mod 2)$
  - True
- Factoring
  - $x^{2} + 1$
  - $(x - 1)^{2}$
  - $x^{2} - 2 x + 1$
  - $2 x (\mod 2) = 0$
  - $(x^{2} + 1)$
  - $(x - 1) (x + 1) = x^{2} - 1$
2
- $Z_{2}$
- $Z_{39}$
- $Z_{47}$
- $Z_{19}$
- See that $39$ is not prime, so this is the only one that has an element with no multiplicative inverse
- $0, 3, 13$ have no multiplicative inverses because $3 \cdot 13 = 39$
- $0$ just doesn't have one anyways
- $gcd (a, n) = 1$ then it has a multiplicative inverse.
- Find $[22]^{- 1} \in Z_{39}$
  - We want $[x]$ such that $[22] [x] = [22 x] = [1]$
  - $gcd (22, 39) = 1$
  - $22 x \equiv 1 (\mod 39)$
  - $39 ∣ 1 - 22 x$
  - $39 y = 1 - 22 x$
  - $- 1 = - 22 x - 39 y$
  - $1 = 22 x + 39 y$
  - Find the solution to this
  - ${\begin{cases} 39 & = 22 (1) + 17 \\ 22 & = 17 (1) + 5 \\ 17 & = 5 (3) + 2 \\ 5 & = 2 (2) + 1 \\ 2 & = 1 (2) + 0 \end{cases}$
  - $5 + 2 (- 2) = 1$
  - reverse
  - Generally
    - $1 = b x + 39 y$
    - What values of $b$ result in a $gcd (a, b) = 1$
    - Clearly they must be co-prime
3
- Last digit of $7^{1998}$
- $7^{1998} = (7^{18})^{111} = ((7^{2})^{18})^{111}$
- $(49)^{18 \cdot 111} \equiv 9^{18 \cdot 111} (\mod 10)$
- $9^{18 \cdot 111} = (9^{2})^{9 \cdot 111} = (81)^{9 \cdot 111} \equiv 1^{9 \cdot 111} (\mod 10) \equiv 1 (\mod 10)$
- Solution:
  - $7^{1998}$
    - Example:
      - $5341$
      - $= 5 (10)^{3} + 3 (10)^{2} + 4 (10)^{1} + 1 (10)^{0}$
      - $\equiv 5 (0)^{3} + 3 (0)^{2} + 4 (0)^{1} + 1 (1) (\mod 10)$
      - $\equiv 1 (\mod 10)$
    - $(7^{2})^{999} = (49)^{999} \equiv 9^{999} (\mod 10) \equiv - 1^{999} (\mod 10)$
    - See that $(- 1)^{999}$ and $999$ is odd
    - So $(- 1)^{999} \equiv - 1 (\mod 10) \equiv 9 (\mod 10)$
  - $7^{1999} = (7^{2})^{999 + 1} = 7 (7^{2})^{999}$