, 2022

From $4k = 12 + 3\ell$, it follows $k = 3k_1$, $k_1 \in \mathbb{N}$. Analogously, $\ell = 4\ell_1$, $\ell_1 \in \mathbb{N}$. Assuming $p = 3$ gives rise to $3 \mid k$ and $3 \mid \ell^2 + \ell k + k^2 \Rightarrow 3 \mid \ell \Rightarrow (k, \ell) \ge 3 > 1$, a contradiction with $(k, \ell) = 1$. Thus, $p > 3$, $(3, p) = 1$, and
$$\begin{aligned} \ell^2 + \ell k + k^2 \equiv 3 \pmod{p} &\iff 9\ell^2 + 9\ell k + 9k^2 \equiv 27 \pmod{p} \\ &\iff (4k - 12)^2 + (4k - 12)3k + 9k^2 \equiv 27 \pmod{p} \\ &\iff 16k^2 - 96k + 144 + 12k^2 - 36k + 9k^2 - 27 \equiv 0 \pmod{p} \\ &\iff 37k^2 - 132k + 117 \equiv 0 \pmod{p} \\ &\iff (37k)^2 - 2 \cdot 66 \cdot 37 \cdot k + 117 \cdot 37 \equiv 0 \pmod{p} \\ &\iff (37k - 66)^2 \equiv 66^2 - 117 \cdot 37 \equiv 27 \pmod{p} \\ &\iff (37k_1 - 22)^2 \equiv 3 \pmod{p}, \end{aligned}$$
meaning that 3 must be a quadratic residue modulo $p$. Since the quadratic residues mod 5 and mod 7 are respectively $\{0, 1, 4\}$ and $\{0, 1, 2, 4\}$, 3 is not among them and $p \notin \{5, 7\}$, i.e., $p \ge 11$. For $p = 11$, $11 \mid 22$ and $37 \equiv 4 \pmod{11}$. Therefore, it suffices to find a solution for $(4k_1)^2 \equiv 3 \pmod{11}$, which modulo 11 is equivalent to $k_1^2 \equiv 5 \pmod{11}$, i.e., $k_1 = 11k_2 + 4$ or $k_1 = 11k_2 + 7$. We have to additionally assure $(k, \ell) = 1$. We know that $k_1 = 1 + \ell_1$, thus $(k_1, \ell_1) = 1$. Therefore, it suffices to take $(k_1, 4) = 1$ and $(\ell_1, 3) = 1$, e.g., $k_1 = 15$. Then $\ell_1 = 14$, $k = 45$, $\ell = 56$, $(k, \ell) = 1$, and from $k \equiv \ell \equiv 1 \pmod{11}$ we check that
$$\ell^2 + \ell k + k^2 \equiv 1^2 + 1 \cdot 1 + 1^2 \equiv 3 \pmod{11}.$$
In conclusion, the answer is $p = 11$.