## Gauss’s Criterion

### May 1, 2018

Yesterday was the 241st anniversary of the birth of Carl Gauss, who is perhaps the greatest mathematician who ever lived. In his honor, I picked a small task based on some mathematics that he discovered. Gauss’s Criterion states:

Let p be an odd prime and b a positive integer not divisible by p. Then for each positive integer 2 k − 1 < p, let rk be rk ≡ ( 2 k − 1) b (mod p) with 0 < rk < p, and let t be the number of even rk s. Then (b/p) = (-1)t, where (b/p) is the Legendre symbol.

Your task is to write a program to compute Gauss’s criterion, and confirm that it is the appropriate power of the Legendre symbol. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

### One Response to “Gauss’s Criterion”

1. Daniel said

Here’s a solution in Python 2.

```def legendre(b, p):
l = (b ** ((p - 1) / 2)) % p
if l == p - 1:
l = -1
return l

def gauss(b, p):
r = ((x * b) % p for x in xrange(1, p, 2))
t = sum(1 for x in r if (x % 2) == 0)
return (-1) ** t

ps = [3, 5, 7, 11, 13, 17, 19, 23, 29]
for p in ps:
for b in range(1, p):
assert gauss(b, p) == legendre(b, p)
```