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

Best, Chris

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

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

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

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

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.

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

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

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)

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

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.

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)