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