A new method for finding a solution (when they exist) to $x^2 = a \pmod p$?

Question

For prime $p \ge 2$ define a set $S \subset \Bbb N$ by

$\quad S = \{t^2 \mid t \ge 1 \land t^2 \lt p\}$

Let $a$ be an integer satisfying

$\quad 1 \le a \lt p$

Conjecture: The equation $x^2 \equiv a \pmod p$ has a solution if and only if there exists an integer $s$ belonging to $S$ such that, when applying Euclidean division by setting the dividend to $sa$ and the divisor to $p$, the remainder also belongs to $S$.

When a solution exists, it can be calculated by solving the corresponding $tx \equiv 1 \pmod{p}$ equation.

If this is known please point to some references or supply a proof. Otherwise please help in finding a counter-example; see also Jaap Scherphuis' comments.

It is certainly possible that $S$ has to be expanded, up, to say,

$\; S = \{t^2 \mid 1 \le t \lt p\}$

when forming the divisor $sa$, but the 'tighter the better' when formulating algorithms for this idea. But we really want the aesthetically pleasing duality statement,

$\quad S^\text{*} (\text{residue side of } sa) = S (\text{multiply side of } sa$).

Example 1: $x^2 = 2 \pmod{17}$.

Here $S = \{1,4,9,16\}$.

Dividing $4 \cdot 2:\quad$ $8 = 0\cdot 17 + 8$ and $8 \notin S$
Dividing $9 \cdot 2:\quad$ $18 = 1\cdot 17 + 1$ and $1 \in S$

We have $[3]^{-1} = [6]$ in the $\text{modulo-}17$ system.

So

$\; x^2 = 2 \pmod{17} \; \text{ iff } \; 3^2 x^2 \equiv 1 \pmod{17} \; \text{ iff } \; \large x^2 \equiv 3^{-2} \pmod{17} \; \text{ iff } \; x^2 \equiv 6^{2} \pmod{17} $

and we've found a solution, $x = 6$.

Example 2: $x^2 \equiv 3\pmod {10007}$.

Here is a Python program:

S =[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000]

for m in S:
    r = m*3 % 10007
    if r in S:
        print(m, m**.5, r)
        raise SystemExit

with output

$3721\; 61.0\; 1156$

We have $1156 = 34^2$.

We have $[61]^{-1} = [3281]$ in the $\text{modulo-}10007$ system.

So

$\; x^2 = 3 \pmod{10007} \; \text{ iff } \; 61^2 x^2 \equiv 34^2 \pmod{10007} \; \text{ iff } \; \large x^2 \equiv 61^{-2} 34^2 \pmod{10007} \; \text{ iff } \; x^2 \equiv (3281 \cdot 34)^2 \pmod{10007} \; \text{ iff } \; x^2 \equiv 1477^2 \pmod{10007}$

and we've found a solution, $x = 1477$.

Example 3: $x^2 \equiv 3 \pmod{7}$.

Here $S = \{1,4\}$.

Since $4 \times 3 \equiv 5 \pmod{7}$ is not in $S$, there are no solutions.

Example 4: $x^2 = 19 \pmod{127}$

$\; x^2 \equiv 19 \pmod{127} \; \text{ iff }$
$\;6^2 x^2 \equiv 6^2 \cdot 19 \pmod{127}\; \text{ iff }$
$\;6^2 x^2 \equiv 7^2 \pmod{127}$

We have $[6]^{-1} = [106]$ in the $\text{modulo-}127$ system.

So,

$\;x^2 \equiv 6^{-2} 7^2 \pmod{127}\; \text{ iff }$
$\;x^2 \equiv \bigr( 6^{-1} 7^1 \bigr)^2 \pmod{127}\; \text{ iff }$
$\;x^2 \equiv \bigr( 106 \cdot 7 \bigr)^2 \pmod{127}\; \text{ iff }$
$\;x^2 \equiv 107^2 \pmod{127}$

and we see that $x \equiv 107 \pmod{127}$ is a solution.

My Work

After seeing lonza leggiera's counter-example answer to my question here, I went back to the drawing board and this kind of just 'popped out'.

In this question I wanted to focus on the extensively studied modulo prime systems, but if it works here further research would be warranted.