Post your solutions to the Apr 10 In-Class Exercise to this thread. Best, Chris

-- Apr 10 In-Class Exercise

'''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@

-- Apr 10 In-Class Exercise

 a = 14, b = 7, n = 21,

 (p-p) = 0, then (a−p)(b−p)⋯ (p-p) ⋯ (x−p)(y−p)(z−p) = 0

How many solutions will the equation 7x=3mod21 have ? Solution: No solutions. Let a = 7, b = 3, n = 21, then gcd(a, n) = 7. 7 is not dividable by 3, therefore no solutions. How many solutions will the equation 14x=7mod21 have? Solution: Seven solutions. Let a = 14, b = 7, n = 21, then gcd(a, n) = 7. 7 is dividable by 7, d =7, therefore 7 solutions. Work out any solutions using what we've learned so far: xi = (x0 + i * (n / d)) % n a = 14, b = 7, n = 21, for i in 1...7, the solutions are: 2 5 8 11 14 17 20 Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p) (p-p) = 0, then (a−p)(b−p)⋯ (p-p) ⋯ (x−p)(y−p)(z−p) = 0

-- Apr 10 In-Class Exercise

How many solutions will the equation 7x=3mod21 have? d solutions where d = gcd(a,n) ax = bmodn -> 7x = 3mod21 d = gcd(a,n) -> d = gcd(7, 21) = 7 7 does not divide 3 therefore no solutions. How many solutions will the equation 14x=7mod21 have? d solutions where d = gcd(a,n) ax = bmodn -> 14x = 7mod21 -> d = gcd(14, 21) = 7 There are 7 solutions Work out any solutions using what we've learned so far. // to be continued Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p).

-- Apr 10 In-Class Exercise

1. 7x = 3 mod 21 d = gcd(a, n) = gcd(7, 21) = 7 gcd(7, 21) = gcd(21, 7) = gcd(7, 0) = 7 d | b = 7 | 3 False. It has no solution. 2. 14x = 7 mod 21 d = gcd(14, 21) = 7 d | b = 7 | 7 True. It has 7 solutions. 3. It contains the item (p - p), so (a - p)(b - p)... (p - p)...(z - p) =0

-- Apr 10 In-Class Exercise

 gcd(7,21) = 7

 d = 7 does not divide b = 3 so there are 0 solutions

 gcd(14,21) = 7

 d = 7 does divide b = 7 so there are 7 solutions.

 From EE, you get x' = -1 and x0 = x' * (b/d) mod 21 = (-1)(7/7) mod 21 = 20

 xi = x0 + i(n/d) mod 21 = 20 + i(3) mod 21

 For i = 1,2,...,7
 xi = 2,5,8,11,14,17,20

 = (a-p)(b-p)...(p-p)...(x-p)(y-p)(z-p) = 0
 because (p-p) = 0

How many solutions will the equation 7x=3(mod21) have ? gcd(7,21) = 7 d = 7 does not divide b = 3 so there are 0 solutions How many solutions will the equation 14x=7(mod21) have ? gcd(14,21) = 7 d = 7 does divide b = 7 so there are 7 solutions. From EE, you get x' = -1 and x0 = x' * (b/d) mod 21 = (-1)(7/7) mod 21 = 20 xi = x0 + i(n/d) mod 21 = 20 + i(3) mod 21 For i = 1,2,...,7 xi = 2,5,8,11,14,17,20 Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p). = (a-p)(b-p)...(p-p)...(x-p)(y-p)(z-p) = 0 because (p-p) = 0

-- Apr 10 In-Class Exercise

7x=3mod21 let a=7,b=3,n=21 d=gcd(a,n)=gcd(7,21)=7. But, 7 does not divide 3 so there will be No solutions. 14x=7mod21 let a=14,b=7,n=21 d=gcd(14,21)=7. 7 can divide 7, by our corollary there exist 7 solutions. From the EE, d=7⋅(−1)+21⋅1; therefore, x'=−1. Our first solution is x0=x'(b/d)mod 21=−1(7/7)mod 21=20 Trick Question.. Evaluate: (a−p)(b−p)...(x−p)(y−p)(z−p) (a-p)(b-p)...(p-p)...(x−p)(y−p)(z−p) (a-p)(b-p)...0...(x−p)(y−p)(z−p) = 0

-- Apr 10 In-Class Exercise

# 7x = 3 mod 21 ; a = 7, b= 3, n = 21 ; we can get d = 7 ; so d = 7 don't divide by b = 3, there is 0 solution # 14x = 7 mod 21 * a = 14, b = 7, n = 21 * so, we get d = 7, x = 1, y = -1 * as d = 7 can divide by b = 7, there are solutions * then, x_0 = (-1)*1 mod 21 = -1 * i from 0 to 6, there is 7 solutions. * when i = 0, we get first solution : -1 + (0*(7/7) mod 21) = -1 + (0 mod 21) = -1 # Trick Question.. Evaluate: (a−p)(b−p)...(x−p)(y−p)(z−p) (a-p)(b-p)...(p-p)...(x−p)(y−p)(z−p) (a-p)(b-p)...0...(x−p)(y−p)(z−p) = 0

-- Apr 10 In-Class Exercise

    -1 + * i(21/7) mod 21

a) No solutions. b) 7 solutions for (i = 0 to 6): -1 + * i(21/7) mod 21 So solution is [-1, 2, 5, 8, 11, 14, 17]

-- Apr 10 In-Class Exercise

 How many solutions will the equation 7x=3(mod21) have?
 d=gcd(7,21)=7, b=3, 7 does not divide 3, therefore, there is no solution.

 How many solutions will the equation 14x=7(mod21) have?
 d=gcd(14,21)=7, b=7, 7 divide 7, therefore, there are 7 solutions.
 Since we have d=7*(-1)+21*1, x'=-1.
 x0=x'(b/d)mod n = -1(7/7)mod21 = 20,therefore, the rest of the solutions for i = 1 ... 6 can be obtain by xi = x0 + i(21/7) mod 21, the rest of solutions are 2,5,8,11,14,17

 Trick question... Evaluate:
 (a−p)(b−p)⋯(x−p)(y−p)(z−p)
 =(a-p)(b-p)⋯(p-p)⋯(x−p)(y−p)(z−p)
 =(a-p)(b-p)⋯0⋯(x−p)(y−p)(z−p)
 =0

How many solutions will the equation 7x=3(mod21) have? d=gcd(7,21)=7, b=3, 7 does not divide 3, therefore, there is no solution. How many solutions will the equation 14x=7(mod21) have? d=gcd(14,21)=7, b=7, 7 divide 7, therefore, there are 7 solutions. Since we have d=7*(-1)+21*1, x'=-1. x0=x'(b/d)mod n = -1(7/7)mod21 = 20,therefore, the rest of the solutions for i = 1 ... 6 can be obtain by xi = x0 + i(21/7) mod 21, the rest of solutions are 2,5,8,11,14,17 Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p) =(a-p)(b-p)⋯(p-p)⋯(x−p)(y−p)(z−p) =(a-p)(b-p)⋯0⋯(x−p)(y−p)(z−p) =0