Suppose that $p$ and $q$ are distinct primes, then for every integer $a$ and exponent $e$ with $e\not \equiv (\bmod \,(p - 1)(q - 1))$ show that:
${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - 1)}}\,(\bmod \,p \cdot q)$.
I tried to prove it this way:
Let $n = p \cdot q$, $\gcd (p,q) = 1$ and $e' = e\,\bmod \,\varphi (n),$ then $e = m \cdot \varphi (n) + e',\,\,\,m \in {\Bbb Z}$. We have ${a^e} = {a^{m \cdot \varphi (n) + e'}} = {({a^{\varphi (n)}})^m} \cdot {a^{e'}} \equiv {a^{e'}}\,(\bmod \,n)$. The last step is true based on the Euler's totient theorem.
Unfortunately, this proof is correct if and only if $a$ is relatively prime to $n$. However, the task asks to prove it for every integer $a$ and exponent $e$. How to prove it in that case?
Answer
Case$\#1:$ If $p|a$ clearly the ${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - 1)}}\,(\bmod \,p )$ holds as $e>0$
and similarly for $q$
Case$\#2:$ If $p\nmid a\iff (a,p)=1, a^{p-1}\equiv1\pmod p$
$\implies a^{\text{lcm}(p-1,q-1)}\equiv1\pmod p$
and similarly, $a^{\text{lcm}(p-1,q-1)}\equiv1\pmod q$ for $q\nmid a\iff(a,q)=1$
$\implies a^{\text{lcm}(p-1,q-1)}\equiv1\pmod{pq}$
Let $e=r+k\cdot$lcm$(p-1,q-1)$ where $r$ is any integer
$a^e=a^r\cdot (a^{\text{lcm}(p-1,q-1)})^k\equiv a^r\cdot1^k\pmod{pq}$
No comments:
Post a Comment