Euler function and least common multiple Could you give me hint, what is the relationship between the $\phi$ and the $lcm$ functions? In the sense, that:
$p$, $q$ are primes s.t. $m < pq$ and
$$ m^{lcm(p-1, q-1)+1} \equiv m \mod pq $$
So what happens, is that we take out the gcd from $\phi{(pq)}$
What is the reason for this, that the equation works?

Well, by Fermat's little theorem $m^p\equiv m \mod p$, ans so is $m^{x(p-1)+1}$ for any integer $x$. Also, $m^{y(q-1)+1}\equiv m \mod q$. Since $lcm(p-1,q-1)$ is divisible both by $p-1$ and $q-1$, $m^{lcm(p-1,q-1)+1}$ satisfies both of these conditions, so...
