Yioop - PHP Search Engine

Apr 4 In-Class Exercise Thread.

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

Best, Chris

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

-- Apr 4 In-Class Exercise Thread

1.) 5x = 3 mod 15. The number of solutions is gcd(5,15) = 5. Since 5 does not divide 3, it is very apparent (exceedingly apparent) that there are no solutions.

2.) The second equation can be worked out by looking at there being d solutions where d=gcd(a,n) in the equation ax≡b(modn) (10x=5mod15). If we look at the gcd(10,15), we get 5. Therefore there are 5 solutions.

3.) 2, 5, 8, 11, 14

(Edited: 2018-04-04)

1.) 5x = 3 mod 15. The number of solutions is gcd(5,15) = 5. Since 5 does not divide 3, it is very apparent (exceedingly apparent) that there are no solutions. 2.) The second equation can be worked out by looking at there being d solutions where d=gcd(a,n) in the equation ax≡b(modn) (10x=5mod15). If we look at the gcd(10,15), we get 5. Therefore there are 5 solutions. 3.) 2, 5, 8, 11, 14

-- Apr 4 In-Class Exercise Thread

  As per Theorem on previous slide
  ax = b(mod n) has d mod n solutions where d= gcd(a,n) or no solutions

  1.  5x = 3 mod 15
      d = gcd(5,15) = 5
      but 5 does not divide 3, so there are no solutions

  2. 10x = 5 mod 15
     d = gcd(10,15) = 5
     5 mod 15 = 5 or no solutions
     5 divides 5 therefore there are 5 solutions
     solutions are 2,5,8,11,14

(Edited: 2018-04-04)

As per Theorem on previous slide ax = b(mod n) has d mod n solutions where d= gcd(a,n) or no solutions 1. 5x = 3 mod 15 d = gcd(5,15) = 5 but 5 does not divide 3, so there are no solutions 2. 10x = 5 mod 15 d = gcd(10,15) = 5 5 mod 15 = 5 or no solutions 5 divides 5 therefore there are 5 solutions solutions are 2,5,8,11,14

-- Apr 4 In-Class Exercise Thread

1) How many solutions will 5x = 3 mod 15 have?

  If it has any solutions
  number of solutions = gcd(5, 15) = 5
  <a> = {0,5,10}
  b=3 is not contained in <a>, therefore there are no solutions

2) How many solutions will 10x = 5 mod 15 have?

  If it has any solutions
  number of solutions = gcd(10,15) = 5
  <a> = {0,5,10}
  since b=5 is contained in <a>, the equation has 5 solutions
  solutions: 2, 5, 8, 11, 14

(Edited: 2018-04-04)

1) How many solutions will 5x = 3 mod 15 have? If it has any solutions number of solutions = gcd(5, 15) = 5 <a> = {0,5,10} b=3 is not contained in <a>, therefore there are no solutions 2) How many solutions will 10x = 5 mod 15 have? If it has any solutions number of solutions = gcd(10,15) = 5 <a> = {0,5,10} since b=5 is contained in <a>, the equation has 5 solutions solutions: 2, 5, 8, 11, 14

-- Apr 4 In-Class Exercise Thread

ax = b(mod n), then we have x iff gcd(a,n)|b

1. 5x =3 mod 15

a = 5, n = 15, b = 3;

gcd(a,n) = gcd(5,15) = 5 which is not divisible by b=3, so no solution.

2. 10x = 5 mod 15

a = 10, b = 5, n = 15;

gcd(a,n) = gcd(10,15) =5 which is divisible by b=5, so we have 5 solutions.

10 * x % 15 = 5

x= 2, 5, 8, 11, 14

(Edited: 2018-04-04)

ax = b(mod n), then we have x iff gcd(a,n)|b 1. 5x =3 mod 15 a = 5, n = 15, b = 3; gcd(a,n) = gcd(5,15) = 5 which is not divisible by b=3, so no solution. 2. 10x = 5 mod 15 a = 10, b = 5, n = 15; gcd(a,n) = gcd(10,15) =5 which is divisible by b=5, so we have 5 solutions. 10 * x % 15 = 5 x= 2, 5, 8, 11, 14

-- Apr 4 In-Class Exercise Thread

 Q1. 5x = 3 mod 15 -> GCD is 5. But 5 is not dividable by 3. So it is not solvable.
 Q2. 10x = 5 mod 15 -> GCD is 5. And 5 is divisible by 5. Therefore, this has 5 solutions.
 Q3. Solutions are 2,5,8,11,14

Q1. 5x = 3 mod 15 -> GCD is 5. But 5 is not dividable by 3. So it is not solvable. Q2. 10x = 5 mod 15 -> GCD is 5. And 5 is divisible by 5. Therefore, this has 5 solutions. Q3. Solutions are 2,5,8,11,14

-- Apr 4 In-Class Exercise Thread

 1. No solution : gcd(5,15) = 5 and 5 does not divides 3
 2. 5 solutions : gcd(10, 15) = 5 and 5 does divide 5 => (2, 5, 8, 11, 14)

1. No solution : gcd(5,15) = 5 and 5 does not divides 3 2. 5 solutions : gcd(10, 15) = 5 and 5 does divide 5 => (2, 5, 8, 11, 14)

-- Apr 4 In-Class Exercise Thread

The GCDs for each of the equations is 5. The first equation is unsolvable as the gcd(5,15) doesn't divide 3 The second equation is solvable as the gcd(10,15) divides 5 Thus we proceed to find solutions for 10x = 5mod15 The solutions for the above equation are 2,5,8,11,14

<nowiki> The GCDs for each of the equations is 5. The first equation is unsolvable as the gcd(5,15) doesn't divide 3 The second equation is solvable as the gcd(10,15) divides 5 Thus we proceed to find solutions for 10x = 5mod15 The solutions for the above equation are 2,5,8,11,14 </nowiki>

-- Apr 4 In-Class Exercise Thread

1. There is no solution to this as gcd(5, 15) = 5 does not divide 3. 2. There is a solution to this as gcd(10, 15) = 5 divides 5. Hence, it will have 5 solutions, e.g., x = 2 and 5.

-- Apr 4 In-Class Exercise Thread

 In case one, 
 a * x = b % n => 5 * x = 3 % 15 has no distinct solutions because 5 doesn't divide 3 
 
 10 * x = 5 % 15
 This problem has either 5 or no solutions
 The sequence is (2, 5, 8, 11, 15)

In case one, a * x = b % n => 5 * x = 3 % 15 has no distinct solutions because 5 doesn't divide 3 10 * x = 5 % 15 This problem has either 5 or no solutions The sequence is (2, 5, 8, 11, 15)