Solution
= Solution
The <Euler theorem> states that if $\gcd(a,d)=1$, then
$$
a^{\phi(d)}\equiv1\pmod d.
$$
Let $r_1,\ldots,r_{\phi(d)}$ be the reduced residue classes modulo $d$. Multiplication by $a$ permutes them, so
$$
a^{\phi(d)}r_1\cdots r_{\phi(d)}
\equiv r_1\cdots r_{\phi(d)}\pmod d.
$$
Their product is a unit and may be cancelled, proving the theorem.