Prove that between any two rational numbers there is a rational whose numerator and denominator are both perfect squares. (1) Suppose $\frac{p_1}{q_1}$ and $\frac{p_2}{q_2}$ are rationals with $0<\frac{p_1}{q_1} <\frac{p_2}{q_2}$.  We want to find a rational $\frac{a}{b}$ such that $\frac{p_1}{q_1}<\frac{a^2}{b^2} <\frac{p_2}{q_2}$.
I know that if we choose any rational in the open interval between $\sqrt{\frac{p_1}{q_1}}$ and $\sqrt{\frac{p_2}{q_2}}$, then this rational will have the desired property.  However, the issue is that I am trying to use this proof as a part of a larger proof to prove the existence of the square root of any positive real number.  So I cannot use any argument that directly references square roots.
Here is some work I have done so far.  I went down the rabbit hole a bit and this may be a dead end, I'm not sure. 
Since $\frac{p_1}{q_1} = \frac{p_1q_1q_2^2}{q_1^2q_2^2}$ and $\frac{p_2}{q_2} = \frac{p_2q_1^2q_2}{q_1^2q_2^2}$, it is sufficient to prove that: 
(2) there exists a perfect square, $n^2$, (possibly 1) such that the interval between $n^2p_1q_1q_2^2$ and $n^2p_2q_1^2q_2$ contains a perfect square. 
To prove (2) it is sufficient to prove that:
(3) for all positive integers $n$ there exist perfect squares, $k^2$ and $m^2$, such that $k^2n<m^2<k^2(n+1)$
So my question is either for assistance proving any of (1), (2), or (3) without using the existence of square roots of positive real numbers,
OR if this is something that MUST be proven using the existence of square roots, then just state that.  I would NOT like help in proving the existence of square roots another way.  If it MUST be done another way, I would like to figure out the other way myself.
That being said, I am sure that proving the existence of square roots of positive reals CAN be proven another way (likely much simpler), but I am hoping that the path I am taking may work too.  I just need help with this last part.
 A: Let rational $\ x\ z\in\mathbb Q\ $ be such that $\ 0<x<z;\ $ for instance, let $\ x:=\frac{p_1}{q_1}\ $ and
$\ z:=\frac{p_2}{q_2},\ $ where the fractions are as in the OP's Question. Let $\ y:=\frac{x+z}2,\ $ so that
$\ 0<x<y<z;\ (y\in\mathbb Q).$
The classical (and beautiful) Newton's method provides arbitrarily good rational approximations $\ r_n\ $ of $\ \sqrt y\ $ in the most elementary way, and $\ r_n^2\ $ provides an answer to the OP's Question when the Newton approximation is advanced enough.
The consecutive Newton approximations $\ r_n\ $ of $\ y\ $ converge to $\ y\ $ very fast:
$$ \rho_0:= 1\qquad r_0:=y $$
and
$$ \rho_n\ :=\ \frac{\rho_{n-1}+r_{n-1}}2 $$
$$ r_n\ :=\ \frac y{\rho_n} $$
for arbitrary $\ n=1\ 2\ \ldots$.
we see that:
$$ \forall_{n=0}^\infty\quad \rho_n\cdot r_n\ =\ y $$
and, depending on $ y\le 1\ $ or $\ y\ge 1$, we get
$$ r_0^2\ \le y\ \le \rho_0^2\qquad\mbox{or}
     \qquad r_0^2\ \ge y\ \ge \rho_0^2 $$
and
$$ \forall_{n\in\mathbb N}\quad r_n^2\ \le\ y\ \le\ \rho_n^2 $$
I'll leave the estimates of the wonderful speed of approximation as a pleasant and most rewarding exercise (perhaps in mathematical induction).
A: The following proof does not assume any knowledge of real numbers and square roots and uses only the properties of rational numbers. The argument below is typical of many analytical arguments and is the essence of definition of real numbers as envisaged first by Dedekind. 

Let $x, y$ be two positive rationals with $x<y$. We are supposed to find a rational $a$ such that $x<a^2<y$. The problem is easily handled if $y$ itself is a perfect square. Thus if $y=t^2$ then we can choose $a<t$ such that $$y-a^2=t^2-a^2<y-x$$ ie $$(t-a) (t+a) <y-x$$ and this is easily done if we choose $$t-a<\frac{y-x} {2t}$$
We are thus left with the difficult case when $y$ is not a square. Let's consider the set $$A=\{a\mid a\in\mathbb {Q}, a>0,a^2<y\}$$ Clearly this set is non empty and bounded above. We will prove that there is no greatest member in this set. Suppose on the contrary that there is a greatest member, say $m$, in $A$. Then we have $m^2<y$ but for any rational $n>m$ we have $n^2>y$. Let's further assume $m<n<m+1$ and then we have $$n^2-m^2=(n-m)(n+m)<(n-m)(2m+1)$$ And we have an obvious contradiction if $$0<n-m<\min\left(1,\frac{y-m^2}{2m+1}\right)$$ because then we have $n^2-m^2<y-m^2$ or $n^2<y$.
In a similar manner we can show that the set $$B=\{b\mid b\in\mathbb {Q}, b>0,b^2>y\}$$ is non-empty, bounded below and has no least member. Now we can choose some specific members $a\in A, b\in B$ and an arbitrary positive integer $n$ and consider the sequence of numbers $$x_i=a+i\cdot\frac{b-a} {n} $$ so that $$a=x_0<x_1<x_2<\dots<x_n=b$$ In the above sequence there is a last, say $x_r$, which lies in $A$ and the next one $x_{r+1}\in B$ and we have $x_{r+1}-x_r=1/n$. Since $n$ is arbitrary it follows that give any positive rational number $\epsilon$ we can find members $a\in A, b\in B$ such that $b-a<\epsilon$.
Next we set $\epsilon=y-x>0$ and consider a specific number $k\in B$. Now we can choose $a\in A, b\in B$ with $b-a<\epsilon/(2k)$ and also ensure $b<k$. This implies that $a<b<k$ and thus $a+b<2k$ and $$b^2-a^2=(b+a)(b-a)<2k\cdot\frac{\epsilon}{2k}=\epsilon$$ or $$(b^2-y)+(y-a^2)<\epsilon$$ Each term in parentheses in positive and hence individually less than $\epsilon $. We thus have $$y-a^2<\epsilon=y-x$$ or $x<a^2<y$. Thus we have found a rational number $a$ as desired.

The above proof can be worked out (to aid in understanding) for specific example. Let's say we wish to find a square between $x=1.9$ and $y=2$. We take $a=1\in A, b=2\in B$ and set $n=100$ ($n$ is choosen such that $1/n< (y-x) / 2b$) and consider sequence of numbers $x_i=1+(i/100)$. Clearly $x_{41}=1.41\in A, x_{42}=1.42\in B$ and $1.9<1.41^2<2$.
A: HINT:
Let your rationals be $0< r_1 < r_2$. Consider $0<a < b$ rationals so that $a^2 < r_1$ and $b^2 > r_2$. Now consider a set of intermediate points $x_k=a +  \frac{k(b-a)}{N}$, $\ k = 0,1,\ldots, N$, where $N$ is sufficiently large so that $0<f(x_{k+1})-f(x_k)<r_2 - r_1$  for all $k$.  It should be easy now.
ADDED: This works in a similary for any other "continuous" function $f$, like a polynomial. The property is "weak intermediate value", that is, if $f(a)\ne f(b)$ then $f([a,b]\cap \mathbb{Q})$ is dense in $[f(a),f(b)]$. 
Note that even if we "avoid using the reals" in the proof, we used natural numbers and the fact that $\mathbb{Q}$ is an archimedean ordered field ( a subfield of $\mathbb{R}$ as it is).  
A: NOTE: this answer ignores the constraints of the question.
Here's one way to do it.
Let $f$ be defined as follows:
$$ f(x) = x \cdot |x| $$
And let $f^{-1}$ be the inverse of $f$.
$f$ is like the square function except that it preserves signs. Note that $f$ is monotonic.
Let's define a function $B : \mathbb{Z} \times \mathbb{R} \to \mathbb{Q}$ .
$B_x(\alpha)$ is the largest rational number strictly less than $\alpha$ that is expressible as a fraction with a denominator of $x$. That fraction is not required to be in simplest form.
$$ B_x(\alpha) = \sup \left( \mathbb{R}_{\le \alpha} \;\bigcap\; \left\{ \frac{w}{x} \mathop. w \in \mathbb{Z} \right\} \right) $$
Here are a few examples:
$$ B_3\left(\frac{1}{2}\right) = \frac{1}{3} $$
$$ B_4\left(\frac{2}{3}\right) = \frac{2}{4} \;\;\text{and furthermore}\;\; B_4\left(\frac{2}{3}\right) = \frac{1}{2} $$

Lemma 101: upper bound on $\alpha - B_x(\alpha)$
The distance between $\alpha$ and $B_x(\alpha)$ is always less than or equal to $\frac{1}{x}$ . If the distance were any greater than $\frac{1}{x} + B_x(\alpha)$ would be closer to $\alpha$ than $B_x(\alpha)$, but still less than $B_x(\alpha)$ . This is a contradiction.
$$ \alpha - B_x (\alpha) \le \frac{1}{x} \tag{101} $$

Theorem 102: There exist integers $x$ and $y$ such that $\frac{a}{b} < \frac{xx}{yy} < \frac{p}{q} $
We are trying to show the following:
$$ \forall a p \in \mathbb{Z} \mathop. \forall b q \in \mathbb{Z} \setminus \{0\} \mathop. \exists x y \in \mathbb{Z} \mathop. \frac{a}{b} < \frac{p}{q} \implies \frac{a}{b} < \frac{xx}{yy} < \frac{p}{q} \tag{102} $$
Let $\beta = f^{-1}\left(\frac{p}{q}\right) - f^{-1}\left(\frac{a}{b}\right)$ . This is the distance between the pseudo-square root of our two endpoints.
Let $\gamma = \min\left(10, \lceil \frac{1}{\beta} \rceil \right)$ . $\gamma$ is a positive integer such that $\frac{1}{\gamma}$ is guaranteed to be smaller than $\beta$ .
Let $\delta$ be the smallest power of $2$ bigger than or equal to $\gamma$ .
$$ \delta = 2^{\lceil \mathrm{lb} \gamma \rceil} $$
Let's pick $\varepsilon$ as follows. It will be the numerator of our fraction.
$$ \varepsilon = B_\delta\left(f^{-1}\left(\frac{p}{q}\right)\right)$$
Because of how we picked $\delta$ we know the following:
$$ f^{-1}\left(\frac{a}{b}\right) < \frac{\varepsilon}{\delta} < f^{-1}\left(\frac{p}{q}\right) $$
And thus by applying $f$, our sign-preserving pseudo-square function.
$$ \frac{a}{b} < \pm \frac{\varepsilon\varepsilon}{\delta\delta} < \frac{p}{q} $$
In the cases where $\frac{a}{b}$ and $\frac{p}{q}$ are both positive,  $ \frac{\varepsilon\varepsilon}{\delta\delta} $ is a perfect square as desired since it's positive.
