3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Please give some context. Where did you encounter that statement? $\endgroup$ – Bill Dubuque Jul 1 '16 at 19:16
  • $\begingroup$ Expressing numbers $\bmod 1$ rarely leads to useful insight in my experience. $\endgroup$ – Joffan Jul 1 '16 at 19:33
  • $\begingroup$ @BillDubuque: See edits. $\endgroup$ – Kieren MacMillan Jul 1 '16 at 19:36
  • $\begingroup$ @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… $\endgroup$ – Kieren MacMillan Jul 1 '16 at 19:38
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $r=1$ not a possible solution? $\endgroup$ – Kieren MacMillan Jul 1 '16 at 19:32
  • $\begingroup$ 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! $\endgroup$ – Kieren MacMillan Jul 1 '16 at 19:54
  • $\begingroup$ OK, $r=1$ as well, but $\mathbb Z/\mathbb Z = \{0\}$ is trivial. $\endgroup$ – Robert Israel Jul 1 '16 at 21:29
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.