How can you show that the modular equation 22x41(mod13) has a unique solution and find that solution?

Answer 1

Let 22*41 = 13*a + b where a and b are integers and 0<=b<13

[b is the remainder when 22*41 is divided by 13.]

Suppose there are two solutions. That is

22*41 = 13*a + b and 22*41 = 13*c + d

13*a + b = 13*c + d

so that 13*(a - c) = (d - b)

This implies that a - c = 0 or the LHS divides the RHS.

But RHS = d - b < 13 so LHS cannot divide RHS.

Therefore a - c = 0 ie a = c.

Then LHS = 0 so RHS = 0 => d - b = 0.

That is a = c and b = d so that 13*a + b = 13*c + d ie the solution is unique.

Since 13 is prime, we can simplify the question to

22*41(mod 13) = 22(mod13)*41(mod13) = 9*2(mod 13) = 18(mod13) = 5.