# Inconsistent definitions of “quadratic residue” versus (linear) “residue”?

The Legendre symbol $(94 / 59)$ is equal to $1$, therefore, by definition, $94$ is a quadratic residue mod $59$.

At the same time, the residue of $a\mod n$ is defined as the (positive) remainder when $a$ is divided by $n$, i.e. the residue of $a\mod n$ is an element of $\mathbb{Z}_n$.

So, in the first paragraph above, while there's no argument about calling $94-59=35$ a quadratic residue of $59$, aren't the two definitions above inconsistent if $94$ is also called a quadratic residue of $59$?

Thank you, I just want to be sure that I'm using the terminology correctly.

-
You only care about the class of the number modulo the modulus. 3 is a quadratic residue modulo 2 simply because it is congruent to 1 modulo 2. –  Mariano Suárez-Alvarez Oct 30 '12 at 15:21
I'd say the common definition of quadratic residue is: the congruence class of a square. –  Mariano Suárez-Alvarez Oct 30 '12 at 15:27
@MarianoSuárez-Alvarez That's what I said in my question. However, is this not inconsistent with the common definition of residue to mean the positive remainder? –  Ryan Oct 30 '12 at 15:30
I think that the word "larger" is maybe inappropriate for comparing residues. There is no order once you reduce $\mathbb{Z}$ modulo $n$. For instance, modulo 5, would we have $3<4<5<6<7<8\equiv3$? –  alex.jordan Oct 30 '12 at 15:54

Mathematically, a remainder$\!\mod n$ is an equivalence class defined by the equivalence relation $R$ given by "$aRb$ iff $a-b$ is divisible by $n$". Such an equivalence class is determined by giving any number contained in it, and the chosen representative is usually the smallest non-negative number in the class.

However, there are exceptions, such as your case above. Another example is the classic proplem "Given a prime $p$, when is $-1$ a quadratic residue$\!\mod p$?"

Were it defined to be the remainder after division by $n$, then defining addition and multiplication $\!\mod n$ would be more complicated than it is using the definition of equivalence classes.

-
Oh good, so my usage has not been wrong and I wasn't wrong to see it as an exception (inconsistency) then. Thanks Arthur. I accept the discrepancy and am glad I aren't crazy. Haha –  Ryan Oct 30 '12 at 15:54

To add some information about contexts in which it can be useful to have the top number 'higher' ...

If you are looking at the law of quadratic reciprocity you swap the numbers in the Legendre symbol - and one will be larger than the other. It is then the ability to reduce modulo the smaller number which makes this law so computationally useful. You may also be able to use the prime factorisation of the large top number to reduce to some simpler cases (it becomes more visible or obvious), or ones you already know.

So you need, and may encounter in practice, Legendre Symbols where the top number is higher.

-
Hi Mark, thanks. Yes I know that the allowing of the "numerator" to be a "higher" number is for practical reasons. My question was regarding the contradiction in terms, that's all. –  Ryan Oct 31 '12 at 3:19