# What does it mean when a non-integer rational fraction is a square modulo an integer?

Let’s say that $p$ and $q$ are coprime integers such that $p/q$ is a non-integer rational fraction in lowest terms. Now let’s say that $r$ is a positive integer such that $p/q$ is a square modulo $r$.

What does that even mean?

Note: In the best case scenario [vis-à-vis my current mathematical work], it would imply $r=1$. What I have is $7/6$ is a square modulo [an indeterminate/unknown integer] $r$.

EDIT (more details): I have a system of four equations in four indeterminate integers $x$, $y$, $p$, and $q$. Manipulating the system, I found that $7k^2 \equiv 6m^2\!\pmod{3q-4p}$ for some integers $k$ and $m$ [actually functions of the four unknown integers]. I'm trying to determine what I can say about $3q-4p$, which I'm hoping to prove equals $1$.

EDIT #2 (even more details): I can obtain a fairly large number of such conclusions, e.g. $-14/3$ and $9/2$ and $7/6$ are all squares modulo this indeterminate integer $3q - 4p$. Perhaps there is a way to use two or more of these results to force $3q - 4p = 1$? For example, is it kosher to say $$\frac{-14}{3} \times \frac{9}{2} = -21$$ is a square modulo $3q-4p$, because each one is a square modulo $3q-4p$? Better yet, is $$\frac{-14}{3} \times \frac{7}{6} = -\frac{49}{9} = -\biggl(\frac{7}{3}\biggr)^2$$ a square modulo $3q-4p$? Because then $-1$ is a square, so all primes dividing $3q-4p$ are of the form $4n+1$, I think?

• Please give some context. Where did you encounter that statement? – Bill Dubuque Jul 1 '16 at 19:16
• Expressing numbers $\bmod 1$ rarely leads to useful insight in my experience. – Joffan Jul 1 '16 at 19:33
• @BillDubuque: See edits. – Kieren MacMillan Jul 1 '16 at 19:36
• @Joffan: When you're simply comparing integers, I totally agree. But if you could use modular considerations to prove that some otherwise-indeterminate integer modulus equals $1$, that would be whole different story… – Kieren MacMillan Jul 1 '16 at 19:38

We use fraction notation $\,x = a/b\,$ only when there exists a unique solution $\,x\,$ to $\,b x = a.\,$

Modulo $\,n,\,$ this is true iff $\,b\,$ is coprime to $\,n\,$ since then by Bezout $\, bj+nk = 1\,$ for some integers $\,j,k.\,$ Thus reducing this equation modulo $\,n\,$ we obtain $\,bj\equiv 1\pmod{n},\,$ i.e. $\, j\equiv b^{-1}.\,$ Scaling $\, bx\equiv a\,$ by $\,b^{-1}$ we obtain the unique solution $\,x\equiv ab^{-1},\,$ i.e. $\,a/b \equiv ab^{-1}.$

Conversely if $\,b\,$ is not coprime to $\,n,\,$ a unique solution of $\,bx\equiv a\,$ need not exist, i.e. there can be no solutions, or more than one solution, so $\,x \equiv a/b\pmod n\,$ is not well-defined.

For example, mod $\rm 10,$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}\,$ cannot designate a unique solution of $\,4x\equiv 2.\,$ Indeed, the solution is $\rm\:x\equiv 1/2\equiv 3\pmod 5,\,$ which requires canceling $\,2\,$ from the modulus too, because $\rm\:10\mid 4x-2\iff5\mid 2x-1.\,$

Further $\,x \equiv 1/2\pmod{10}\,$ has no solution since $\,10\mid 2x-1\,\Rightarrow 10n = 2x-1\,$ hence $\,1 = 2x-10n\,$ is even, contradiction. See here for more.

Thus, when the fraction is well-defined, your question reduces to asking about when integers are squares mod $\,n,\,$ a classical question that is solvable by quadratic reciprocity and a generalized Euler criterion.

If $q$ is relatively prime to $r$, then division by $q$ is well-defined mod $r$ and the statement is simply saying that $p/q$ is a square in $\mathbb{Z}/r\mathbb{Z}$.

Probably the most reasonable interpretation of that statement would then say that $p/q$ cannot be a square modulo $r$ when $q$ is not relatively prime to $r$, because as the term "modulo $r$" indicates an element of that ring, and $p/q$ is not an element of that ring.

However, even if $q$ and $r$ are not relatively prime, it's possible there's a more general interpretation, perhaps using $r$-adic numbers. Rather than speculate about this, one would want more context for your statement.

If $q$ and $r$ are coprime, division by $q$ is well-defined in the ring $\mathbb Z/r \mathbb Z$ of integers mod $r$, i.e. there is some integer $x$ such that $p \equiv q x \mod r$. So this is saying that there is such an $x$ that is the square of an integer.

For example, $7/6 \equiv 5^2 \mod 11$, so $7/6$ is a square $\mod 11$.

The integers $r$ such that $7/6$ is a square mod $r$ are the divisors of $7 - 6 y^2$ for integers $y$. The first few are $1, 7, 11, 13, 17, 19, 29, 41, 47, 53, 61, 77, 79, 89, 91$.

EDIT: Yes, the squares coprime to $r$ mod $r$ form a subgroup of the multiplicative group of $\mathbb Z/r \mathbb Z$. $-1$ is a square mod $r$ (and therefore mod any prime factor of $r$) iff all odd prime factors of $r$ are congruent to $1 \mod 4$ and there is at most one factor of $2$: see OEIS sequence A008784. However, be careful: $-14/3$, $7/6$, and $9/2$ are all squares mod $7$ but $-1$ is not.

• Is $r=1$ not a possible solution? – Kieren MacMillan Jul 1 '16 at 19:32
• I have accepted this answer (because it answered the original question well). But if you have a second to look at EDIT #2 and the resulting question, I would appreciate it. Thanks! – Kieren MacMillan Jul 1 '16 at 19:54
• OK, $r=1$ as well, but $\mathbb Z/\mathbb Z = \{0\}$ is trivial. – Robert Israel Jul 1 '16 at 21:29

Your hope seems unsatisfiable. Let $k=2$, $m=1$, $p = 2$ and $q = 10$. Then $$3q-4p = 22 \text{ and } \\ 7 k^2 \cong 6 m^2 \cong 6 \pmod{22} \text{.}$$ Furthermore, both $22 \neq 1$ and $22 = 2 \cdot 11$ has no prime factors of the form $4n+1$.

Note that since both $k^2$ and $m^2$ are obviously quadratic residues modulo $3q-4p$, it must be that $6$ and $7$ are both quadratic residues or are both quadratic nonresidues modulo $3q-4p$. Only about 50% of moduli have this property. So it would seem that for half the choices of "generic integers" $p$ and $q$, there exist satisfying choices of $k$ and $m$. This doesn't tell you about the prime factorizations, but by reasonable counting methods, much less than half the integers factor only over primes congruent to $1$ modulo $4$.

A search through small moduli for those having $-14 \times 3^{-1}$, $9 \times 2^{-1}$, and $7 \times 6^{-1}$ as quadratic residues (actually, I only checked that the Jacobi symbol of these three residues was positive, which can give false positives below for composite moduli) turns up the following moduli:

17, 25, 41, 89, 121, 169, 185, 193, 209, 257, ...


all of which are congruent to $1 \pmod{4}$, but don't necessarily factor to primes with the same residue. For instance $121 = 11^2$ and $11 \cong 3 \pmod{4}$.

I like your idea of investigating for which moduli $-21 = -1 \cdot 3 \cdot 7$ is a quadratic residue. If the Jacobi symbols for each prime factor of $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots$ (where we assume each of the $p_j$ are distinct) are $1$, then $n$ will be a modulus for which $-21$ is a quadratic residue. It is convenient to dispose of $p_j = 2$ immediately: $-21$ is a quadratic residue modulo $2$, but not to any higher power of $2$. \begin{align} \left( \frac{-21}{n} \right) &= \left( \frac{-1}{n} \right)\left( \frac{3}{n} \right)\left( \frac{7}{n} \right) \end{align} Now $\left( \dfrac{-1}{p_j^{\alpha_j}} \right) = \begin{cases} 1^{\alpha_j} = 1, & p_j \cong 1 \pmod{4} \\ (-1)^{\alpha_j}, & p_j \cong 3 \pmod{4} \end{cases}$. Also, $\left( \frac{3}{n} \right) = 0$ if $3$ divides $n$ and $\left( \frac{7}{n} \right) = 0$ if $7$ divides $n$, so $n$ is not divisible by $3$ or $7$. From quadratic reciprocity, $$\left( \frac{3}{p_j^{\alpha_j}} \right) \left( \frac{p_j^{\alpha_j}}{3} \right) = \begin{cases} 1^{\alpha_j} = 1 , & p_j \cong 1 \pmod{4} \\ (-1)^{\alpha_j}, & p_j \cong 3 \pmod 4 \end{cases}$$ and $$\left( \frac{7}{p_j^{\alpha_j}} \right) \left( \frac{p_j^{\alpha_j}}{7} \right) = \begin{cases} 1^{\alpha_j} = 1 , & p_j \cong 1 \pmod{4} \\ (-1)^{\alpha_j}, & p_j = 2 \text{ or } p_j \cong 3 \pmod{4} \end{cases} \text{.}$$ Further, a simple calculation shows $$\left( \frac{p_j^{\alpha_j}}{3} \right) = \begin{cases} 1^{\alpha_j} = 1, & p_j \cong 1 \pmod{3} \\ (-1)^{\alpha_j}, & p_j \cong 2 \pmod{3} \end{cases}$$ and $$\left( \frac{p_j^{\alpha_j}}{7} \right) = \begin{cases} 1^{\alpha_j} = 1, & p_j \in \{1,2,4\} \pmod{7} \\ (-1)^{\alpha_j}, & p_j \in \{3,5,6\} \pmod{7} \end{cases}$$ and inserting these into the above reciprocity results gives $$\left( \frac{3}{p_j^{\alpha_j}} \right) = \begin{cases} 1 , & p_j \cong 1 \pmod{4} \text{ and } p_j \cong 1 \pmod{3} \\ (-1)^{\alpha_j}, & p_j \cong 3 \pmod{4} \text{ and } p_j \cong 1 \pmod{3} \\ (-1)^{\alpha_j} , & p_j \cong 1 \pmod{4} \text{ and } p_j \cong 2 \pmod{3} \\ (-1)^{2\alpha_j} = 1, & p_j \cong 3 \pmod{4} \text{ and } p_j \cong 2 \pmod{3}\end{cases}$$ and $$\left( \frac{7}{p_j^{\alpha_j}} \right) = \begin{cases} 1^{\alpha_j} = 1 , & p_j \cong 1 \pmod{4} \text{ and } p_j \in \{1,2,4\} \pmod{7} \\ (-1)^{\alpha_j}, & p_j \cong 3 \pmod{4} \text{ and} p_j \in \{1,2,4\} \pmod{7} \\ (-1)^{\alpha_j} , & p_j \cong 1 \pmod{4} \text{ and } p_j \in \{3,5,6\} \pmod{7} \\ (-1)^{2\alpha_j} = 1, & p_j \cong 3 \pmod{4} \text{ and} p_j \in \{3,5,6\} \pmod{7} \end{cases} \text{.}$$

Using the Chinese Remainder Theorem (of just working iteratively through small integers), we can simplify the conditions in these big blocks. $$\left( \frac{3}{p_j^{\alpha_j}} \right) = \begin{cases} 1 , & p_j \in \{1, 11\} \pmod{12} \\ (-1)^{\alpha_j}, & p_j \in \{5, 7\} \pmod{12} \end{cases}$$ and $$\left( \frac{7}{p_j^{\alpha_j}} \right) = \begin{cases} 1 , & p_j \in \{1, 3, 9, 19, 25, 27 \} \pmod{28} \\ (-1)^{\alpha_j}, & p_j \in \{5, 11, 13, 15, 17, 23 \} \pmod{28} \end{cases} \text{.}$$

So, for $-21 \pmod{n}$ to be a quadratic residue, $\left( \frac{-1}{p_j^{\alpha_j}} \right) \left( \frac{3}{p_j^{\alpha_j}} \right) \left( \frac{7}{p_j^{\alpha_j}} \right)$ must be $1$ for each $p_j$. This is true if exactly all or $1$ of these symbols is $1$. These are all $1$ if $p_j \in \{1, 4, 16, 25, 37, 58, 64\} \pmod{84}$. Exactly one of these symbols is $1$ if $p_j \in \{5, 11, 17, 19, 20, 23, 26, 31, 41, 44, 55, 68, 71, 76, 80\} \pmod{84}$. Discarding all the even residues (since the modulus is zero and we have resolved the contribution of the prime $2$ initially), if $p_j$ is one of these $12$ residues, $\{1, 5, 11, 17, 19, 23, 25, 31, 37, 41, 55, 71\}$ modulo $84$, $-21$ is a quadratic residue modulo $p_j$ and $-21$ is a quadratic residue modulo any product of such primes. (Note that this is very far from requiring the primes are congruent to $1$ modulo $4$.) For instance $-21 \cong 1^2 \pmod{11}$ and $-21 \cong 12^2 \pmod{55}$ are quadratic residues.

To address your first question: Suppose $x$, $y$, $a$, $b$, and $m$ satisfy $x^2 \cong a \pmod {m}$ and $y^2 \cong b \pmod {m}$. Then $\dfrac{a}{b} \cong \dfrac{x^2}{y^2} \cong x^2 y^{-2} \pmod{m}$, is a fraction that is a square modulo $m$.