The other way is entirely equivalent: it just starts with a private key $s$ which has gcd $1$ with $n$, and computes the square of the inverse modulo $n$ (or the inverse of the square, which is the same). That way you're sure that the public key will be a square residue because that's how you made it.
If you know $p$ and $q$ prime such that $pq=n$ you can compute the $s$ from the public value $v$ in the standard way: compute $v'=v^{-1} \pmod{n}$ using the extended Euclidean algorithm and compute the square roots of $v'$ modulo $p$ and $q$ and combine them via the Chinese remainder theorem to find all 4 square roots of $v'$ modulo $n$.
Small example: $n=77$ and $v=64$. Clearly $p=7,q=11$ will do. $v'=\frac{1}{v} \pmod{n}= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 \pmod{7} = 1$ which has roots $1, -1\equiv 6$.
Modulo $11$: $71 \pmod{11}= 5$ which has roots $4, -4 \equiv 7$.
The Bézout coefficients for $7$ and $11$ are also easy to find by hand:
$$8 \cdot 7 + (-5) \cdot 11 = 1$$
So by the CRT, the four square roots of $71$ are
$$(\pm 4) \cdot 8 \cdot 7 + (\pm 1) \cdot (-5) \cdot 11 \pmod{77}$$
for all $4$ choices of signs.
That gave me $(++): 15, (-+): 29, (--): 62, (+-) 48$ as the solutions, so the smallest is $15$. This indeed has square $71$ modulo $n$, as required.
Best Answer
Assuming that $n_1$ and $n_2$ are RSA moduli: the common prime $p$ is $\gcd(n_1, n_2)$, easily computable by Euclid's algorithm. We then know $q = \frac{n_1}{p}$ and now you're good to go.