Yioop - PHP Search Engine

-- Apr 10 In-Class Exercise

7x = 3 mod 21
a = 7
b = 3
n = 21
d = gcd(7, 21) = 7
d does not divide 7, so there are no solutions. 
 
14x = 7 mod 21
a = 14
b = 7
n = 21 
 
Extended-Euclid(14,21) = (7, -1, 1)
Extended-Euclid(21, 14) = (7, 1, -1)
Extended-Euclid(14, 7) = (7, 0, 2)
Extended-Euclid(7, 0) = (7, 1, 0) 
 
gcd(14, 21) = 7
d | b, so there are 7 solutions. 
 
x_0 = -1(7/7) mod 21 = 20
for i = 0 ... 6
x_i = (20 + (i * 21/7)) mod 21
Possible solutions are 20, 2, 5, 8, 11, 14, 17 
 
Trick question
(a-p)(b-p)...(x-p)(y-p)(z-p) = 0 as (p-p) = 0 and will make the product 0

<pre> 7x = 3 mod 21 a = 7 b = 3 n = 21 d = gcd(7, 21) = 7 d does not divide 7, so there are no solutions. 14x = 7 mod 21 a = 14 b = 7 n = 21 Extended-Euclid(14,21) = (7, -1, 1) Extended-Euclid(21, 14) = (7, 1, -1) Extended-Euclid(14, 7) = (7, 0, 2) Extended-Euclid(7, 0) = (7, 1, 0) gcd(14, 21) = 7 d | b, so there are 7 solutions. x_0 = -1(7/7) mod 21 = 20 for i = 0 ... 6 x_i = (20 + (i * 21/7)) mod 21 Possible solutions are 20, 2, 5, 8, 11, 14, 17 Trick question (a-p)(b-p)...(x-p)(y-p)(z-p) = 0 as (p-p) = 0 and will make the product 0 </pre>

-- Apr 10 In-Class Exercise

1) gcd(7,21) = 7

    d = 7 does not divide b = 3

    so there are no solution

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

3)In the series comes a term that is (p−p) which evaluates to 0.

   
   Hence, the series (a−p)(b−p)⋅⋅(p−p)⋅⋅(x−p)(y−p)(z−p) evaluates to 0.

1) gcd(7,21) = 7 d = 7 does not divide b = 3 so there are no solution 2)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 3)In the series comes a term that is (p−p) which evaluates to 0. Hence, the series (a−p)(b−p)⋅⋅(p−p)⋅⋅(x−p)(y−p)(z−p) evaluates to 0.

-- Apr 10 In-Class Exercise

How many solutions will the equation 7x=3mod21 have ?

Based on Solution Existence Theorem, d = gcd(21,7) = 7, b = 3, 7 does not divides 3, so there is no solution.

How many solutions will the equation 14x=7mod21 have ?

Based on Solution Existence Theorem, d = gcd(21,14) = 7, b = 7, 7 divides 7, so there are 7 solutions, Solution are given by

formular xi = (x0 + i(n/d)) mod 21, x0 = (0*(7/7))mod 21 = -1, given i = 7, solution are 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) = (a-p)(b-p)...0...(x-p)(y-p)(z-p) = 0.

How many solutions will the equation 7x=3mod21 have ? Based on Solution Existence Theorem, d = gcd(21,7) = 7, b = 3, 7 does not divides 3, so there is no solution. How many solutions will the equation 14x=7mod21 have ? Based on Solution Existence Theorem, d = gcd(21,14) = 7, b = 7, 7 divides 7, so there are 7 solutions, Solution are given by formular xi = (x0 + i(n/d)) mod 21, x0 = (0*(7/7))mod 21 = -1, given i = 7, solution are 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) = (a-p)(b-p)...0...(x-p)(y-p)(z-p) = 0.

-- Apr 10 In-Class Exercise

a. The equation ax = b mod n has either d = gcd(a, n) solutions or no solutions. Given that a = 7, b = 3, and n = 21, d = gcd(7,21) = 7. Since 3 does not divide into 7, there are no solutions for this equation.

b. following the same logic, a = 14, b = 7, n = 21, d = gcd(14,21) = 7. Since 7 divides into 7, there are 7 solutions for this equation.

EE(14,21) evaluates to (7,-1,1).

Using the equation (x'*(b/d) mod n ) + (i * (n/d)) mod n for i = 0 to d - 1, we get:

(-1 * (7/7) mod 21) = -1

-1 + (0 * 21/7) mod 21 = -1 -1 + (1 * 21/7) mod 21 = 2 -1 + (2 * 21/7) mod 21 = 5 8 11 14 17

c. 0

a. The equation ax = b mod n has either d = gcd(a, n) solutions or no solutions. Given that a = 7, b = 3, and n = 21, d = gcd(7,21) = 7. Since 3 does not divide into 7, there are no solutions for this equation. b. following the same logic, a = 14, b = 7, n = 21, d = gcd(14,21) = 7. Since 7 divides into 7, there are 7 solutions for this equation. EE(14,21) evaluates to (7,-1,1). Using the equation (x'*(b/d) mod n ) + (i * (n/d)) mod n for i = 0 to d - 1, we get: (-1 * (7/7) mod 21) = -1 -1 + (0 * 21/7) mod 21 = -1 -1 + (1 * 21/7) mod 21 = 2 -1 + (2 * 21/7) mod 21 = 5 8 11 14 17 c. 0

-- Apr 10 In-Class Exercise

 1. ax = b mod n
 7x = 3 mod 21
 a = 7, b = 3, n = 21
 d = gcd(a, n) = gcd(7, 21) = 7
 d|b? -> 7 doesn't divide 3 -> no solution

 2. 14x = 7 mod 21
 a = 14, b = 7, n = 21
 d = gcd(14, 21) = 7
 d|b? -> yes, 7|7 -> d = 7 solutions

 extended-euclid(a, n)
 = extended-euclid(14, 21)
 = (7, -1, 1) = (d, x', y')

 x0 = x'(b/d) mod n = (-1)(7/7) mod 21 = 20

 xi =(x0 + i(n/d)) mod n = (20 + 3i) mod 21
 for i = 1, 2, ..., 6
 we get the solutions 2, 5, 8, 11, 14, 17

 3. (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

(Edited: 2019-04-15)

1. ax = b mod n 7x = 3 mod 21 a = 7, b = 3, n = 21 d = gcd(a, n) = gcd(7, 21) = 7 d|b? -> 7 doesn't divide 3 -> no solution 2. 14x = 7 mod 21 a = 14, b = 7, n = 21 d = gcd(14, 21) = 7 d|b? -> yes, 7|7 -> d = 7 solutions extended-euclid(a, n) = extended-euclid(14, 21) = (7, -1, 1) = (d, x', y') x0 = x'(b/d) mod n = (-1)(7/7) mod 21 = 20 xi =(x0 + i(n/d)) mod n = (20 + 3i) mod 21 for i = 1, 2, ..., 6 we get the solutions 2, 5, 8, 11, 14, 17 3. (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. 7x = 3 mod 21
 No solutions. gcd(7,21) = 7 and 3 is not divisible by 7.

 2. 14x = 7 mod 21
 extendedEuclid(14, 21) = (7, -1, 1)
 x0 = -1(7/7) mod 21 = 20
 for i from 0 to 6
 xi = (20 + (i * 21/7)) mod 21
 x = [2, 5, 8, 11, 14, 17, 20]

 3. Evaluate (a-p)(b-p)...(x-p)(y-p)(z-p)
 (p-p) evaluates to 0, so the whole expression equals 0.

(Edited: 2019-04-15)

1. 7x = 3 mod 21 No solutions. gcd(7,21) = 7 and 3 is not divisible by 7. 2. 14x = 7 mod 21 extendedEuclid(14, 21) = (7, -1, 1) x0 = -1(7/7) mod 21 = 20 for i from 0 to 6 xi = (20 + (i * 21/7)) mod 21 x = [2, 5, 8, 11, 14, 17, 20] 3. Evaluate (a-p)(b-p)...(x-p)(y-p)(z-p) (p-p) evaluates to 0, so the whole expression equals 0.

-- Apr 10 In-Class Exercise

How many solutions will the equation 7x=3mod21 have ? a = 7, b = 3, n = 21 d = gcd(7, 21) = 7 so that d not divisible by 3 --> 0 solution

How many solutions will the equation 14x=7mod21 have ? a = 14, b = 7, n = 21 d = gcd(14, 21) = 7 EE(14,21) --> x' = -1

-1*(7/14)mod21 = 20 so that solutions are 2, 5, 8, 11, 14, 17, 20

How many solutions will the equation 7x=3mod21 have ? a = 7, b = 3, n = 21 d = gcd(7, 21) = 7 so that d not divisible by 3 --> 0 solution How many solutions will the equation 14x=7mod21 have ? a = 14, b = 7, n = 21 d = gcd(14, 21) = 7 EE(14,21) --> x' = -1 -1*(7/14)mod21 = 20 so that solutions are 2, 5, 8, 11, 14, 17, 20

-- Apr 10 In-Class Exercise

1. How many solutions will the equation 7x=3mod21 have ?

a = 7, b = 3, n = 21, d = gcd(7,21) = 7. Since 7 doesn't divide by 3, no solution

2. How many solutions will the equation 14x=7mod21 have ?

a = 14, b = 7, n = 21, d = gcd(14,21) = 7. 7 does divide by 7, so there are 7 solutions

EE(14,21) = (7, -1, 1)

x0 = x'*(b/d) mod n, which is -1(7/7) mod 21 = 20

Using for i = 0 to 6

(20 + (i * 3)) mod 21

Solutions are: 20, 2, 5, 8, 11, 14, 17

3. Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p).

(a-p)(b-p) ....(o-p)(p-p)(q-p).....(x-p)(y-p)(z-p)

(a-p)(b-p) ....(o-p)0(q-p).....(x-p)(y-p)(z-p)

= 0

1. How many solutions will the equation 7x=3mod21 have ? a = 7, b = 3, n = 21, d = gcd(7,21) = 7. Since 7 doesn't divide by 3, no solution 2. How many solutions will the equation 14x=7mod21 have ? a = 14, b = 7, n = 21, d = gcd(14,21) = 7. 7 does divide by 7, so there are 7 solutions EE(14,21) = (7, -1, 1) x0 = x'*(b/d) mod n, which is -1(7/7) mod 21 = 20 Using for i = 0 to 6 (20 + (i * 3)) mod 21 Solutions are: 20, 2, 5, 8, 11, 14, 17 3. Trick question... Evaluate: (a−p)(b−p)⋯(x−p)(y−p)(z−p). (a-p)(b-p) ....(o-p)(p-p)(q-p).....(x-p)(y-p)(z-p) (a-p)(b-p) ....(o-p)0(q-p).....(x-p)(y-p)(z-p) = 0

-- Apr 10 In-Class Exercise

since g(a, n) = gcd (14, 21) = 7, 1) when b =3 , d|b == false, therefore no solution for 14x = 3 mod 21; 2) when b = 7, d|b == true, therefore there are d= 7 solutions; 3) Extended Euclidian (a, n) = EE ( 14, 21) --> EE( 21, 14) --> EE( 14, 7) --> EE( 7,0) returns (7, 1,0) --> returns ( 7, 0, 1) --> returns (7, 1, -1) --> returns ( 7, -1,1 ) where d = 7 + 14 * (-1) + 21 * 1
x0 = (x' * (b/d)) mod n = ((-1) * (7/7) ) mod 21 = 20;
for i = 0,1,2...6 calculate x_i = ( x0 + i * (n/d)) mod n, that is 20, 23, 26, 29, 32, 35, 38 all mod 21
so final answers are 20, 2, 5, 8, 11, 14, 17.

(Edited: 2019-05-15)

since g(a, n) = gcd (14, 21) = 7, 1) when b =3 , d|b == false, therefore no solution for 14x = 3 mod 21; 2) when b = 7, d|b == true, therefore there are d= 7 solutions; 3) Extended Euclidian (a, n) = EE ( 14, 21) --> EE( 21, 14) --> EE( 14, 7) --> EE( 7,0) returns (7, 1,0) --> returns ( 7, 0, 1) --> returns (7, 1, -1) --> returns ( 7, -1,1 ) where d = 7 + 14 * (-1) + 21 * 1 <br> x0 = (x' * (b/d)) mod n = ((-1) * (7/7) ) mod 21 = 20; <br> for i = 0,1,2...6 calculate x_i = ( x0 + i * (n/d)) mod n, that is 20, 23, 26, 29, 32, 35, 38 all mod 21 <br> so final answers are 20, 2, 5, 8, 11, 14, 17.