1
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Oct 9 at 15:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Oct 9 at 15:07
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.