Let $ n = pq$ where $p$ and $q$ are distinct primes, and let $e$ be an integer coprime to $ \varphi (n)$.
Explain why there is an integer $d$ such that $ed = 1 $ (mod $ \varphi(n)$).
Prove that $b^{ed} = b $(mod $ n$) for any integer $b$.
.
.
Since $p$ and $q$ are coprime I can rewrite $\varphi (n)$ as $\varphi(p) \varphi(q)$
I believe I can say that $gcd(\varphi(n), e) = gcd(\varphi(p), e) = gcd(\varphi(q), e) = 1$
But I can't seem to dig out the answer from here. Any ideas? Thanks a mill!
On
The crux of the problem is the stipulation "for ANY integer b". In that case, there is no assurance that gcd(b,pq)=1. We cannot say "for any integer b" because the general claim of b^ed=b mod pq would be FALSE. I believe this problem was motivated by trying to understand the RSA algorithm. In RSA, it is stipulated that b is less than pq. In that case b must be relatively prime to at least one of p or q. That turns out to be sufficient to insure b^ed=b mod pq. See RSA algorithm for more details on this point.
You just could take a look at the ring $\;\Bbb Z_{\varphi(n)}\;$ . Its units are precisely all the integers modulo $\;\varphi(n)\;$ which are coprime with $\;\varphi(n)\;$ .
Both claims follow at once from the above, with the second one following from the fact that $\;\left|\Bbb Z_n^*\right|=\varphi(n)\;$