Exercise 2.2.7 ( Probability that $ax \equiv b \pmod{15}$ has at least one solution)

Proof.

a)

By theorem 2.17, we know that the congruence $\mathit{ax}\equiv b(\mathit{mod}15)$ has at least one solution if and only if $15\wedge a\mid b$.

For each fixed $a\in [[1,14]]$, the number of $b\in [[1,15]]$ such that $15\wedge a\mid b$ is $\frac{15}{15\wedge a}$.

Therefore, the number of ordered pairs $(a,b)\in [[1,14]]\times [[1,15]]$ such that $\mathit{ax}\equiv b(\mathit{mod}15)$ has at least one solution is

$$N=\underset{a=1}{\overset{14}{\sum }}\frac{15}{15\wedge a}=146.$$

Sage :

     sum(15//gcd(a,15) for a in range(1,15))

The probability $p$ that $\mathit{ax}\equiv b(\mathit{mod}15)$ has at least one solution is

$$p=\frac{N}{14\times 15}=\frac{146}{210}=\frac{73}{105}\simeq 0.695\dots$$

b)

The congruence $\mathit{ax}\equiv b(\mathit{mod}15)$ has exactly one solution if $a\wedge 15=1$.

Therefore, the number $N^{\prime }$ of $a\in [[1,14]]$ such that $\mathit{ax}\equiv b(\mathit{mod}15)$ has exactly one solution is $\varphi (15)=8$, and the probability $p^{\prime }$ is

$$p^{\prime }=\frac{N^{\prime }}{14}=\frac{8}{14}=\frac{4}{7}\simeq 0.571\dots$$