(a) Let $a$ and $m$ be integers with $1 \leqslant a<m$ and let $d=(a, m)$ be their highest common factor. For any integer $b$, prove that $b$ is a multiple of $d$ if and only if there exists an integer $r$ satisfying the equation $a r \equiv b \operatorname{(\operatorname {mod}m)\text {,andshowthatinthiscasethereare}}$ exactly $d$ solutions to the equation that are distinct $\bmod m$.

Deduce that the equation $a r \equiv b(\bmod m)$ has a solution if and only if $b(m / d) \equiv 0$ $(\bmod m)$.

(b) Let $p$ be a prime and let $\mathbb{Z}_{p}^{*}$ be the multiplicative group of non-zero integers $\bmod p$. An element $x$ of $\mathbb{Z}_{p}^{*}$ is called a $k$ th power $(\bmod p)$ if $x \equiv y^{k}(\bmod p)$ for some integer $y$. It can be shown that $\mathbb{Z}_{p}^{*}$ has a generator: that is, an element $u$ such that every element of $\mathbb{Z}_{p}^{*}$ is a power of $u$. Assuming this result, deduce that an element $x$ of $\mathbb{Z}_{p}^{*}$ is a $k$ th power $(\bmod p)$ if and only if $x^{(p-1) / d} \equiv 1(\bmod p)$, where $d$ is now the highest common factor of $k$ and $p-1$.

(c) How many 437th powers are there mod 1013? [You may assume that 1013 is a prime number.]