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

Question

I want to solve the congruence for $k$ such that $k^2\equiv 5k\pmod {15}, 2\leq k\leq 30$.

For this, if $\gcd(15,k)=1$, then $k\equiv 5\pmod{15}$. Is my approach correct? How can I get the values of $k$.

Answer 1

Well, no because if $\gcd(15,k)=1$, then $k\not\equiv 5\pmod{15}$.

Since there is an integer $s$ such that $$k^2-5k=15s\iff k^2=5(k+3s),$$ there is an integer $t$ such that $k=5t$. So, we have $$(5t)^2=5(5t+3s)\iff 5t(t-1)=3s.$$

Hence, we have $$t=3u\ \ \text{or}\ \ t-1=3v$$ where $u,v$ are integers.

Case 1 : If $t=3u$, then $k=5t=15u\Rightarrow k=15,30$.

Case 2 : If $t-1=3v$, then $k=5t=5(3v+1)\Rightarrow k=5,20.$

Then, since each of $k=5,15,20,30$ satisfies $k^2\equiv 5k\pmod{15}$, the answer is $k=5,15,20,30$.

Answer 2

$k^2\equiv 5k\bmod{15}$

$\iff$ $k^2\equiv 0\bmod{5}$ and $k^2\equiv 2k\bmod{3}$

$\iff$ $k\equiv 0\bmod{5}$ and $k\equiv 0,2\bmod{3}$

$k\equiv 0\bmod{5}$ and $k\equiv 0\bmod{3}$ $\iff$ $k\equiv 0\bmod{15}$, which gives us $k=15$ and $k=30$.

$k\equiv 0\bmod{5}$ and $k\equiv 2\bmod{3}$ $\iff$ $k\equiv 0\bmod{15}$, which gives us $k=5$ and $k=20$.