Example Questions Regarding Gauss's Lemma

Example Questions Regarding Gauss's Lemma

Before we look at the following questions, let's recall Gauss's Lemma, that is:

Lemma (Gauss): Suppose that p is an odd prime where $p \nmid a$ and among the set of least residues (mod p) of: $a, 2a, 3a, ..., \left ( \frac{p - 1}{2} \right )a$ there are exactly g that are greater than $\left ( \frac{p - 1}{2} \right )$, then $x^2 \equiv a \pmod p$ has a solution if g is even and no solution if g is odd. Hence $(a/p) \equiv (-1)^g$.

We will now apply Gauss's Lemma in the following questions.

Example 1

Determine if 7 is a quadratic residue or a quadratic non-residue modulo 19.

We are going to look at the following $\frac{p - 1}{2} = \frac{19 - 1}{2} = 9$ integers: $(1)(7), (2)(7), (3)(7), (4)(7), (5)(7), (6)(7), (7)(7), (8)(7), (9)(7)$, or rather $7, 14, 21, 28, 35, 42, 49, 56, 63$. Taking these integers modulo 19, we now get the list $7, 14, 2, 9, 16, 4, 11, 18, 6$.

Looking at this list, we see that 4 that are strictly greater than 9. Hence $(7/19) = (-1)^4 = 1$. So 7 is a quadratic residue modulo 19.

Example 2

Determine if 10 is a quadratic residue or quadratic non-residue modulo 23.

We are going to first look at the following 11 integers: $(1)(10), (2)(10), (3)(10), (4)(10), (5)(10), (6)(10), (7)(10), (8)(10), (9)(10), (10)(10), (11)(10)$ integers, or rather $10, 20, 30, 40, 50, 60, 70, 80 90, 100, 110$. Taking this list modulo 23, we get the following list: $10, 20, 7, 17, 4, 14, 1, 11, 21, 8, 18$.

Looking at this list, we see that there are 5 that are strictly greater than 11. Hence $(10/23) = (-1)^5 = -1$. So 10 is a quadratic non-residue modulo 23.

Example 3

Determine if 8 is a quadratic residue or quadratic non-residue modulo 17.

We will look at the following 8 integers: $(1)(8), (2)(8), (3)(8), (4)(8), (5)(8), (6)(8), (7)(8), (8)(8)$ or more appropriately $8, 16, 24, 32, 40, 48, 56, 64$. Taking this list (mod 17), we get the following list: $8, 16, 7, 15, 6, 14, 5, 13$.

We note that there are 4 integers in this list that are strictly greater than 8. Hence $(8/17) = (-1)^4 = 1$. So 8 is a quadratic non-residue modulo 17.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License