Determine the number of pairs $(a,b)$ such that the equation $ax=b$ is solvable in the ring $(\mathbb{Z}_{2015},+,\cdot)$.
Proposed by Dorin Andrica, Cluj-Napoca, Romania
Solution:
If $b=0$, then the given equation is solvable for any $a \in \{0,1,\ldots,2014\}$. Hence, there are $2014$ pairs of the form $(a,0)$. Let $b \neq 0$. If $a$ is invertible in $(\mathbb{Z}_{2015},+,\cdot)$, then the equation $ax=b$ in the ring $(\mathbb{Z}_{2015},+,\cdot)$ is solvable and the solution is unique. The number of invertible elements in $(\mathbb{Z}_{2015},+,\cdot)$ is $\varphi(2015)=\varphi(5)\varphi(13)\varphi(31)=4\cdot12\cdot30=1440$. For any invertible element and for any $b \in \{1,2,\ldots,2014\}$ there is a unique solution. Hence, there are $1440\cdot2014=29001600$ pairs $(a,b)$ with $(a,2015)=1$ and $b \neq 0$. Now, let $(a,2015)>1$. Then, also $(b,2015)>1$. We have three cases.
(i) Let $b=5k$, where $k \in \{1,2,\ldots,402\}$. For any $k$, we have $a \in \{5,10,\ldots,5k\}$. So, there are $1+2+\ldots+402=201\cdot403=81003$ pairs $(a,b)$ with $(a,2015)>1$ in this case.
(ii) Let $b=13k$, where $k \in \{1,2,\ldots,154\}$. For any $k$, we have $a \in \{13,26,\ldots,13k\}$. So, there are $1+2+\ldots+154=77\cdot155=11935$ pairs $(a,b)$ with $(a,2015)>1$ in this case.
(iii) Let $b=31k$, where $k \in \{1,2,\ldots,64\}$. For any $k$, we have $a \in \{31,62,\ldots,31k\}$. So, there are $1+2+\ldots+64=32\cdot65=2080$ pairs $(a,b)$ with $(a,2015)>1$ in this case.
Since in each case we have counted twice the pairs for which $b=65k$ or $b=155k$ or $b=403k$, reasoning as before, we have that the total number of pairs when $(a,2015)>1$ is $81003+11935+2080-465-78-10=94465$. So, the total number of pairs $(a,b)$ for which the equation $ax=b$ is solvable in $(\mathbb{Z}_{2015},+,\cdot)$ is
$$2014+29001600+94465=29098079.$$
Note. The result obtained is different from the official solution. See the official solution.
No comments:
Post a Comment