Particular solution to linear congruence

Question

Suppose $ax\equiv b (\bmod m)$, then how to determine the number of solutions $x$ such that $gcd(x,m)=d$? Let us assume $gcd(a,m)|b$. I think euler totient function has some role here?Any hints. Thanks beforehand.

Answer 1

Try solving the congruence equation.

1. Dividing by $s=gcd(a,m)$ might help:

$ax \equiv b \pmod m \Longleftrightarrow a'x \equiv b' \pmod{ m'}$.

Here $$ \begin{cases} m's &= m,\\ a's &= a,\\ b's &= b. \end{cases} $$

2. Invert $a'\pmod{m'}$ so that the equation is equivalent to $$ x\equiv b' c \pmod{ m'} $$ Here $c$ is the $\pmod {m'}$ invere of $a'$.

So your problem translates to finding how many integers t satisfy $$ gcd(b'c + t m' , m's) = d. $$ If $t \equiv r\pmod s$, $0\leq r < s$ then $gcd(b'c + t m' , m's) = gcd(b'c + rm',m's)$.

So $gcd(b'c + t m' , m's)$ has at most $s$ different values and

either there are infinitely many solutions $x$ of $gcd(x,m)= gcd(b'c + t m' , m's)=d$ or there is none.