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

Best,

Chris

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

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

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).

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.

1. 14x = 7 mod 21

d = gcd(14, 21) = 7 d | b = 7 | 7 True. It has 7 solutions.

1. It contains the item (p - p), so (a - p)(b - p)... (p - p)...(z - 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

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

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

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]

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