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\).

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.\]

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)\).

Problem 8 Prove that \(4kxy-1\) does not divide the number \(x^m+y^n\) for any positive integers \(x,y,k,m,n\).