Prove that xn b mod m gcdb m 1 gcdx m 1SolutionProof x b

Prove that

[xⁿ b (mod m), gcd(b, m) = 1] gcd(x, m) = 1

Solution

Proof

x = b (mod m) => R(b/m)[to be read as remainder of dividing b by m] = x ........ (1)

gcd(b, m) = 1 => the only common factor between b and m is 1 => b and m are co-prime. => R(b/m) also will have no common factor with m =>  R(b/m) and m are co-prime => gcd{R(b/m), m} = 1. But, R(b/m) = x from (1) Hence, gcd(x, m) = 1. PROVED