Given integers $a$ and $r$ as well as an arbitrary prime $p$ with $0\leq r\leq p-1$, how many natural numbers are less then or equal to $a$ coprime to $a$ and congruent to $r$ modulo $p$.
At first I tried to count the number of solutions by constructing them from residue classes of factors of $\phi(a)$ but so far this hasn't helped simplify the problem.
Given any $(m,b)=1$ define $\delta_{m,b}(n)$ to be equal to one when $n\equiv b\bmod m$ and zero otherwise.
Now note that:
$$\delta_{m,b}(xy)=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\delta_{m,r}(x)\delta_{m,br^{-1}}(y)$$
Where $r^{-1}$ is the unique multiplictive inverse of $r$ modulo $m$, thus we have:
$$\sum_{\substack{n\leq x\\ n\equiv b\bmod m\\\gcd(n,a)=1}}1=\sum_{\substack{n\leq x\\ \gcd(a,n)=1}}\delta_{m,b}(n)=\sum_{d\mid a}\mu(d)\sum_{n\leq \frac{x}{d}}\delta_{m,b}(dn)\\=\sum_{d\mid a}\mu(d)\sum_{n\leq \frac{x}{d}}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\delta_{m,r}(d)\delta_{m,br^{-1}}(n)\right)=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\left(\sum_{d\mid a}\mu(d)\delta_{m,r}(d)\left(\sum_{n\leq \frac{x}{d}}\delta_{m,br^{-1}}(n)\right)\right)\\$$
However because for any positive real number $y$ and an integer $0\leq c\leq m-1$ we can write:
$$\sum_{n\leq y}\delta_{m,c}(n)=\sum_{mk+c\leq y}1=\sum_{k\leq \frac{y-c}{m}}1=\left\lfloor\frac{y-c}{m}\right\rfloor$$
We must then have:
$$\sum_{\substack{n\leq x\\ n\equiv b\bmod m\\\gcd(n,a)=1}}1=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\left(\sum_{d\mid a}\mu(d)\delta_{m,r}(d)\left(\sum_{n\leq \frac{x}{d}}\delta_{m,br^{-1}}(n)\right)\right)\\=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\left(\sum_{d\mid a}\mu(d)\delta_{m,r}(d)\left\lfloor\frac{x}{dm}-\frac{\overline{br^{-1}}}{m}\right\rfloor\right)$$
Where the expression $\overline{u}$ denotes the smallest non negative integer equivalent to $u$ modulo $m$.
Now from here if we define:
$$\mu(d)\delta_{m,r}(d)\left(\left\lfloor\frac{x}{dm}-\frac{\overline{br^{-1}}}{m}\right\rfloor-\frac{x}{dm}\right)=l_{m,r,b,d}(x)$$
We have the bound:
$$|l_{m,r,b,d}(x)|\leq 2|\mu(d)|\delta_{m,r}(d)$$
Thus we can write:
$$\sum_{\substack{n\leq x\\ n\equiv b\bmod m\\\gcd(n,a)=1}}1=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\left(\sum_{d\mid a}\mu(d)\delta_{m,r}(d)\left\lfloor\frac{x}{dm}-\frac{\overline{br^{-1}}}{m}\right\rfloor\right)\\=\sum_{\substack{1\leq r\leq m\\(m,r)=1}}\left(\sum_{d\mid a}\mu(d)\delta_{m,r}(d)\frac{x}{dm}+\sum_{d\mid a}l_{m,r,b,d}(x)\right)\\=\sum_{d\mid a}\mu(d)\chi_0(d)\frac{x}{dm}+\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)\\=\frac{x}{m}\prod_{p\mid a}\left(1-\frac{\chi_0(p)}{p}\right)+\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)\\=\frac{x}{ma}a\prod_{p\mid a}\left(1-\frac{1}{p}\right)\prod_{p\mid m}\frac{1}{1-\frac{1}{p}}+\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)\\=\frac{x}{ma}\phi(a)\frac{m}{\phi(m)}+\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)=x\frac{\phi(a)}{a\phi(m)}+\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)$$
But we have:
$$|\sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}l_{m,r,b,d}(x)\right)|\leq \sum_{d\mid a}\left(\sum_{\substack{1\leq r\leq m\\(m,r)=1}}2|\mu(d)|\delta_{a,r}(d)\right)\leq 2\sum_{d\mid a}|\mu(d)|=2^{\omega(a)+1}$$
Thus we finally get:
$$\sum_{\substack{n\leq x\\ n\equiv b\bmod m\\\gcd(n,a)=1}}1=x\frac{\phi(a)}{a\phi(m)}+O(2^{\omega(a)})$$
Where again $x$ is any positive real number while $a,m$ and $b$ are arbitrary natural numbers such that $1\leq b\leq m$ with $\gcd(b,m)=1$.