(m^b )^a =m(mod n)

By Dan.Weinrauch Dan.Weinrauch (M1118) on Friday, May 4, 2001 - 09:47 am :

Why it is enough to prove that (m^b )^a = m(mod p)
and (m^b )^a = m(mod q) when n = p x q are prime rather than (m^b )^a = m(mod n)?

By Kerwin Hui (Kwkh2) on Friday, May 4, 2001 - 11:28 am :

This is a consequence of Chinese Remainder Theorem.

(One version of) Chinese Remainder Theorem states that, if $m$ and $n$ are coprime, then the congruence

$x \equiv a$ (mod $m$ ), $x \equiv b$ (mod $n$ )

has a unique solution (mod $p q$ ).

[Another version is a generalisation to a set of pairwise coprime integers ${m_{1}, m_{2}, \dots, m_{n}}$ , the congruence

$x \equiv a_{i}$ (mod $m_{i}$ ), $1 \leq i \leq n$

has a unique solution (mod $m_{1}$ , $m_{2}$ , ..., $m_{n}$ )] Now, as $p$ and $q$ are distinct prime, they are coprime. Hence, if we let $x = (m^{b})^{a}$ , then we have the congruence

$x \equiv m$ (mod $p$ ), $x \equiv m$ (mod $q$ )

Now we can immediately spot a value of $x$ that satisfy this condition, namely $x = m$ . Hence, $x \equiv m$ (mod $p q$ ), as required.

Kerwin

By Susan Langley (Sml30) on Monday, May 7, 2001 - 09:37 am :

If (m^b )^a =m (mod p)=m (mod q). So m (mod p) =m (mod q) as p and q prime, highest common factor =1.

So, say m (mod p)= m (mod q) = r, so m= cp + r=kq + r. Solving for c and k (to some degree), cp=kq since LCF=1 c must be a multiple of q and k a multiple of p. So, m= spq +r =sn+r so m (mod n)=r=(m^b )^a .

I hope that makes sense!