Let a b n Z Show that if a n 1 then x ban 1 is solution to

Let a, b, n Z. Show that if (a, n) = 1, then x = ba^((n) 1) is solution to ax b (mod n)

Solution

a, b, n Z

Euler’s Theorem states that, if a and n are relatively prime then a⁽ⁿ⁾ 1 (mod n)

Since, it is given that gcd(a, n) = 1, then by Euler’s Theorem, a⁽ⁿ⁾ 1 (mod n)

Now, a⁽ⁿ⁾ 1 (mod n) implies that, ba⁽ⁿ⁾ b (mod n)               (as b is an integer, by property of congruence)

Therefore, a solution to the equation ax b (mod n) is given by

ax = ba⁽ⁿ⁾

Or, x = ba^((n)-1)

(Proved)