Question

Find the solution of 21x ≡ 9 mod 15 . ​

Answer 1

Step-by-step explanation:

By definition, the congruence

21x≡14(mod91)(1)

is equivalent to the equation

21x=14+91t,t∈Z(2)

If we divide each term of equation 2 by 7, we obtain the equivalent equation

3x=2+13t,t∈Z

which is equivalent to the congruence

3x≡2(mod13)(3)

Hence,

21x≡14(mod91)⟺3x≡2(mod13)

Since gcd(3,13)=1, the congruence 3x≡2(mod13) has a solution. We can find it by applying the extended Euclidean algorithm.

133=4⋅3+1=3⋅1

Solving for 1 in terms of 3 and 13 yields

1=13−4⋅3

Thus,

1≡−4⋅3(mod13)⟹−4≡3−1(mod13)

Therefore, if we multiply both sides of congruence 3 by −4, we obtain

x≡−8(mod13)

To find all the solutions of congruence 1, we must find all the solutions of the inequality

0≤−8+13t<91

in the integers.

08≤−8+13t<91≤13t<99

Hence, 1≤t≤7. Therefore, the solutions of the congruence 21x≡14(mod91) are

x≡5(mod91)≡18(mod91)≡31(mod91)≡44(mod91)≡57(mod91)≡70(mod91)≡83(mod91)

which you can check by direct computation.