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

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?

• You aren't missing anything. You can't solve it with inverses. So you have to do something else. Hint: Cathoid Ray Tubes. – fleablood Oct 9 at 0:08
• Possible duplicate of Modulo division: Find all integers $k \geq 2$ such that $k^2 = 5k(\mod 15).$ – John Omielan Oct 9 at 5:08
• @John I put the dupe link the other way since the OP wrote more here (and there are more diverse answers here). – Bill Dubuque Oct 9 at 14:58
• @BillDubuque Thanks. That makes sense. – John Omielan Oct 9 at 16:49

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.

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.

• i.e. $\bmod 15\!:\ f(x) = (x-\color{#c00}0)(x-\color{#c00}5)\,$ has only the obvious "constant" roots $\,x\equiv\color{#c00}{ 0,5}\,$ and this holds much more generally - see my answer. – Bill Dubuque Oct 9 at 15:03

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.

• Simpler: that the roots all coincide $\bmod 5$ implies $\bmod 15\!:\ f(x) = (x-\color{#c00}0)(x-\color{#c00}5)\,$ has only the obvious "constant" roots $\,x\equiv\color{#c00}{ 0,5},\,$ which holds much more generally - see my answer. – Bill Dubuque Oct 9 at 15:07

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$$.

• This is a special case of the proof in my answer. – Bill Dubuque Oct 10 at 1:55