RSA and number of decryption exponents

We must prove that in the RSA cryptographic system for the primes $\displaystyle p, q$ and the encryption exponent $\displaystyle e\bot\phi(pq)$ in set $\displaystyle \{0,\dots,\phi(pq)-1\}$ is exactly $\displaystyle gcd(p-1,q-1)$ elements that

you can use as the decryption exponent $\displaystyle d$.

(That is for every $\displaystyle M\in\{0,\dots,pq-1\}$, after encryption $\displaystyle M$ using encryption exponent $\displaystyle e$, and then by using the decryption exponent $\displaystyle d$ we get back the $\displaystyle M$).

Thank you for all helpful answers. (Wink)