Quadratic Congruences with Composite Moduli
Not all moduli are prime, so we do not want to be restricted to prime
moduli. The above theory can be generalized to composite moduli, yet
losing as little as possible. The following function generalizes
Legendre's symbol to a certain extent.
Definition
Let \(a\) be an integer and \(b\) an
odd number, and let \(b=p_1^{\alpha_1}p_2^{\alpha_2}\cdots
p_r^{\alpha_r}\) be the factorization of \(b\) onto primes.
Jakobi's symbol \(\left(\frac ab\right)\) is defined as
\[\left(\frac ab\right)=\left(\frac a{p_1}\right)^{\alpha_1}
\left(\frac a{p_2}\right)^{\alpha_2}\cdots\left(\frac
a{p_r}\right)^{\alpha_r}.\]
Since there is no danger of
confusion, Jacobi's and Legendre's symbol share the notation.
It is easy to see that \(\left(\frac ab\right)=-1\) implies that \(a\)
is a quadratic nonresidue modulo \(b\). Indeed, if \(\left(\frac
ab\right)=-1\), then by the definition \(\left(\frac a{p_i}\right)
=-1\) for at least one \(p_i\mid b\); hence \(a\) is a quadratic nonresidue
modulo \(p_i\).
However, the converse is false, as seen from the following
example.
Example 4
Although \[\left(
\frac2{15}\right)=\left(\frac23\right)\left(\frac25\right)=
(-1)\cdot(-1)=1,\] 2 is not a quadratic residue modulo 15, as it is not
so modulo 3 and 5.
In fact, the following weaker statement holds.
Theorem 12
Let \(a\) be an integer and \(b\)
a positive integer, and let \(b=p_1^{\alpha_1}p_2^{\alpha_2}\cdots
p_r^{\alpha_r}\) be the faktorization of \(b\) onto primes. Then \(a\) is a
quadratic residue modulo \(b\) if and only if \(a\) is a quadratic residue
modulo \(p_i^{\alpha_i}\) for each \(i=1,2,\dots,r\).
If \(a\) quadratic residue modulo \(b\), it is clearly
so modulo each \(p_i^{\alpha_i}\), \(i=1,2,\dots,r\).
Assume that \(a\) is a quadratic residue modulo each \(p_i^{\alpha_i}\)
and that \(x_i\) is an integer such that \(x_i^2\equiv a\) (mod \(p_i^
{\alpha_i}\)). According to Chinese Remainder Theorem there is an \(x\)
such that \(x\equiv x_i\) (mod \(p_i^{\alpha_i}\)) for \(i=1,2,\dots,
r\). Then \(x^2\equiv x_i^2\equiv a\) (mod \(p_i^{\alpha_i}\)) for each
\(i\), and therefore \(x^2\equiv a\) (mod \(b\)).
Theorem 13
The number of quadratic residues modulo \(p^n\)
(\(n > 0\)) is equal to \[\left[\frac{2^{n-1}-1}3\right]+2\;\;\mbox{for}\;
p=2,\quad\mbox{and}\quad\left[\frac{p^{n+1}-1}{2(p+1)}\right]+1\;\;
\mbox{for}\;p > 2.\]
Let \(k_n\) denote the number of quadratic residues
modulo \(p^n\).
Let \(p\) be odd and \(n\geq2\). Number \(a\) is a quadratic residue modulo
\(p^n\) if and only if either \(p\nmid a\) and \(a\) is a quadratic residue
modulo \(p\), or \(p^2\mid a\) and \(a/p^2\) is a quadratic residue modulo
\(p^{n-2}\). It follows that \(k_n=k_{n-2}+p\prime p^{n-1}\).
Let \(p=2\) and \(n\geq3\). Number \(a\) is a quadratic residue modulo \(2^n\)
if and only if either \(a\equiv1\) (mod 8) or \(4\mid a\) and \(a/4\) is
a quadratic residue modulo \(2^{n-2}\). We obtain
\(k_n=k_{n-2}+2^{n-3}\).
Now the statement is shown by simple induction on \(n\).
Many properties of Legendre's symbols apply for Jacobi's symbols also.
Thus the following statements hold can be easily proved by using the
definition of Jacobi's symbol and the analogous statements for
Legendre's symbols.
Theorem 14
For all integers \(a,b\) and odd numbers \(c,d\)
the following equalities hold:
\[\left(\frac{a+bc}c\right)=\left(\frac ac\right)
,\quad\left(\frac{ab}c\right)=\left(\frac ac\right)
\left(\frac bc\right),\quad\left(\frac a{cd}\right)=
\left(\frac ac\right)\left(\frac ad\right).\]
Theorem 15For every odd integer \(a\),
\[\left(\frac{-1}a\right)=(-1)^{\frac{a-1}2},\quad
\left(\frac2a\right)=(-1)^{\left[\frac{a+1}4\right]}.\]
Theorem 16 (The Reciprocity Rule) For any two
coprime odd numbers \(a,b\) it holds that
\[\left(\frac ab\right)\left(\frac ba\right)=
(-1)^{\frac{a-1}2\cdot\frac{b-1}2}.\]
Problem 7
Prove that the equation \(x^2=y^3-5\) has no
integer solutions \((x,y)\).
For even \(y\) we have \(x^2=y^3-5\equiv3\)
(mod 8), which is impossible.
Now let \(y\) be odd. If \(y\equiv3\) (mod 4), then \(x^2=y^3-5\equiv
3^3-5\equiv2\) (mod 4), impossible again. Hence \(y\) must be of the
form \(4z+1\), \(z\in\mathbb{Z}\). Now the given equation transforms into
\[x^2+4=64z^3+48z^2+12z=4z(16z^2+12z+3).\] It follows that \(x^2\equiv4\)
(mod \(16z^2+12z+3\)).
However, the value of Jacobi's symbol
\[\left(\frac{-4}{16z^2+12z+3}\right)=
\left(\frac{-1}{16z^2+12z+3}\right)\] equals \(-1\) because \(16z^2+12z+3
\equiv3\) (mod 4). Contradiction.
Problem 8 Prove that \(4kxy-1\) does not divide the number
\(x^m+y^n\) for any positive integers \(x,y,k,m,n\).
For even \(y\) we have \(x^2=y^3-5\equiv3\) Note that \((x^m,y^n,4kxy-1)=1\). Let us write
\(m\prime =[m/2]\) and \(n\prime =[n/2]\). We need to investigate the
following cases.
\(1^{\circ}\)
\(m=2m\prime \) and \(n=2n\prime \). Then \(4kxy-1\mid(x^{m\prime })^2+(y^{n\prime })^2\)
by Theorem 6 implies \(\left(\frac{-1}{4kxy-1}\right)=1\),
which is false.
\(2^{\circ}\) \(m=2m\prime \) and \(n=2n\prime +1\) (the case \(m=2m\prime +1\), \(n=2n\prime \) is analogous).
Then \(4kxy-1\mid(x^{m\prime })^2+y(y^{n\prime })^2\) and hence
\(\left(\frac{-y}{4kxy-1}\right)=1\).
We claim this to be impossible.
Suppose that \(y\) is odd. The Reciprocity Rule gives us
\[\left(\frac{-y}{4kxy-1}\right)=\left(\frac{-1}{4kxy-1}\right)
\left(\frac{y}{4kxy-1}\right)=(-1)\cdot(-1)^{\frac{y-1}2}\left(
\frac{-1}{y}\right)=-1.\] Now assume that \(y=2^ty_1\), where \(t\geq1\) is
an integer and \(y_1\in\mathbb{N}\). According to Theorem 15, we have
\(\left(\frac{2}{4kxy-1}\right)=1\), whereas, like in the case of odd
\(y\), \(\left(\frac{-y_1}{4kxy-1}\right)=
\left(\frac{-y_1}{4\cdot2^tkxy_1-1}\right)=-1\). It follows that
\[\left(\frac{-y}{4kxy-1}\right)=\left(\frac{2}{4kxy-1}\right)^t
\left(\frac{-y_1}{4kxy-1}\right)=-1.\]
\(3^{\circ}\) \(m=2m\prime +1\) and \(n=2n\prime +1\). Then \(4kxy-1\mid x(x^{m\prime })^2+
y(y^{n\prime })^2\), and hence \(\left(\frac{-xy}{4kxy-1}\right)=1\). On the
other hand, \[\left(\frac{-xy}{4kxy-1}\right)=\left(\frac
{-4xy}{4kxy-1}\right)=\left(\frac{-1}{4kxy-1}\right)=-1,\] a
contradiction.
This finishes the proof.