-- Apr 10 In-Class Exercise
Corollary: The equation `ax\equiv b\text{ (mod n)}` either has `d` distinct solutions modulo `n`, where `d=\text{gcd}(a,n)`, or it has no solutions.
``
How many solutions will the equation `7x=3\text{ mod }21` have ?
``
Solution: let `a = 7, b = 3, n = 21`, then `d = \text{gcd}(a, n) = \text{gcd}(7, 21) = 7`. Because `d = 7` does not divide `b = 3`, by our corollary, there are 0 solutions.
``
How many solutions will the equation `14x=7\text{ mod }21` have ?
``
Solution: let `a = 14, b = 7,` and `n = 21`, then `d = \text{gcd}(a, n) = \text{gcd}(14, 21) = 7`. Because `d = 7` does divides `b = 7`, by our corollary, there are 7 solutions.
From the EE, `d = 7\cdot (-1) + 21\cdot 1`; therefore, `x' = -1`.
Our first solution is `x_0 = x'(b/d) \text{mod 21} = (-1)(7/7) \text{mod 21} = 20`
Our solutions are of the form `x_i = x_0 + i(\frac{n}{d}) \text{mod 21}` for `i = 0, 1, ...,`. Because `n/d = 3`, our remaining solutions are: `2, 5, 8, 11, 14, 17`.
``
Trick question. Evaluate: `(a−p)(b−p)⋯(x−p)(y−p)(z−p)`.
``
Solution: because `(p-p) = 0`, `(a−p)(b−p)\cdots(p-p)\cdots(x−p)(y−p)(z−p) = 0`
(
Edited: 2019-04-10)
'''Corollary:''' The equation @BT@ax\equiv b\text{ (mod n)}@BT@ either has @BT@d@BT@ distinct solutions modulo @BT@n@BT@, where @BT@d=\text{gcd}(a,n)@BT@, or it has no solutions.
@BT@@BT@
How many solutions will the equation @BT@7x=3\text{ mod }21@BT@ have ?
@BT@@BT@
'''Solution: ''' let @BT@a = 7, b = 3, n = 21@BT@, then @BT@d = \text{gcd}(a, n) = \text{gcd}(7, 21) = 7@BT@. Because @BT@d = 7@BT@ does not divide @BT@b = 3@BT@, by our corollary, there are 0 solutions.
@BT@@BT@
----
How many solutions will the equation @BT@14x=7\text{ mod }21@BT@ have ?
@BT@@BT@
'''Solution: ''' let @BT@a = 14, b = 7,@BT@ and @BT@n = 21@BT@, then @BT@d = \text{gcd}(a, n) = \text{gcd}(14, 21) = 7@BT@. Because @BT@d = 7@BT@ does divides @BT@b = 7@BT@, by our corollary, there are 7 solutions.
From the EE, @BT@d = 7\cdot (-1) + 21\cdot 1@BT@; therefore, @BT@x' = -1@BT@.
Our first solution is @BT@x_0 = x'(b/d) \text{mod 21} = (-1)(7/7) \text{mod 21} = 20@BT@
Our solutions are of the form @BT@x_i = x_0 + i(\frac{n}{d}) \text{mod 21}@BT@ for @BT@i = 0, 1, ...,@BT@. Because @BT@n/d = 3@BT@, our remaining solutions are: @BT@2, 5, 8, 11, 14, 17@BT@.
@BT@@BT@
----
Trick question. Evaluate: @BT@(a−p)(b−p)⋯(x−p)(y−p)(z−p)@BT@.
@BT@@BT@
'''Solution: ''' because @BT@(p-p) = 0@BT@, @BT@(a−p)(b−p)\cdots(p-p)\cdots(x−p)(y−p)(z−p) = 0@BT@