Finding all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$. What is going on here?

Question

The question is as follows:

Find all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$.

I have an issue related to this question (its not about the solution to the question):

I know that $\overline{k} \in \mathbb{Z}_{15}$ is invertible if and only if $k$ and $15$ are relatively prime. So, assume $\overline{k}$ is invertible. Then, $\overline{k}^2 = \overline{5}\overline{k}$ implies $\overline{k} = \overline{5}.$ But isn't $\overline{5}$ not invertible, since $5$ is not relatively prime with 15? What am I missing?

Answer 1

You assume there is an invertible root $\bmod 15\,$ then obtain the contradiction that the root is not invertible. This shows only that there are no invertible roots. But here the roots are all non-invertible:

$$\bmod 15\!:\,\ x(x\!-\!5)\equiv 0\iff x\equiv 0,5,\ \ {\rm by}\ \ p,q = 3,5\ \ \rm below\qquad\ \ \ $$

Theorem $\ $ If $\,p\,$ is prime, $\,p\nmid q\,$ and $\,q\,$ is squarefree (e.g. $q$ prime) and $\,a_i\equiv a_j\pmod{\!q}\,$ then

$$\bmod pq\!:\, \ f(x)=(x\!-\!a_1)\cdots(x\!-\!a_n)\equiv 0\iff x\equiv a_1,\ldots, a_n\qquad $$

Proof $ $ (sketch) $ $ By $\,p,q\,$ coprime we have $\ pq\mid f(x)\iff p,q\mid f(x)$

By $\,p\,$ prime: $\,p\mid f(x)\iff p\mid x\!-\!a_k\,$ for some $k.\,$ And $\bmod q\!:\ a_i\equiv a_j\,$ so $\,f \equiv (x\!-\!a_1)^n,\,$ so

by $\,q\,$ squarefree: $\ q\mid f(x)\iff q\mid (x\!-\!a_1)^n\iff q\mid x\!-\!a_1 \iff q\mid x\!-\!a_k$

Combining we conclude $\ p,q\mid x\!-\!a_k\iff pq \mid x\!-\!a_k\ $ by $\,p,q\,$ coprime.

Remark $ $ Here the only roots are the obvious "constant" roots $\,x\equiv a_i\,$ because all the roots coincide mod $q$. In the more general case where there are distinct roots mod $\,p\,$ and $\,q\,$ then there will be other roots by CRT lifting $\,x\equiv a_i\pmod{p}, x \equiv a_j\pmod{q}$ to a unique root $\bmod pq,\,$ where the lifted roots in the case $\,i\neq j$ will differ from the "constant" roots $\,x\equiv a_i$ when $\,i = j.\,$ You can find many examples of this in prior posts.

Answer 2

Clearly $k$ must have a factor $5$, so we can just try $0,5,10$ and see what works. There is no requirement that $k$ be invertible.

$$0^2 =0 \equiv 5\cdot 0 \pmod {15}\\ 5^2=25 \equiv 10 \equiv 5 \cdot 5 \pmod {15}\\ 10^2=100 \equiv 10 \not \equiv 5 \cdot 10 \pmod {15}$$

So all numbers $\ge 2$ equivalent to $0$ or $5\bmod 15$ satisfy this.

Answer 3

Hint:

Use the Chinese remainder theorem and solve $\;k^2-5k=k(k-5)\equiv 0\mod 3$ and $\bmod 5$ first, i.e. solve first $$k(k-2)\equiv 0\mod 3,\qquad k^2\equiv 0\mod 5,$$ then use he inverse isomorphism of this theorem.

Answer 4

If $k^2\equiv5k\mod 15,$ then $3 $ and $ 5 $ divide $ k^2-5k=k(k-5)$,

so $3$ divides $k$ or $k-5$ and $5$ divides $k$ or $k-5$.

$5$ | $k$ iff $5$ | $k-5$, so we have $3$ divides $k$ or $k-5$ and $5$ divides $k$ and $k-5$.

That means $15$ divides $k$ or $k-5$; i.e., $k\equiv 0$ or $5 \mod 15$.