This Demonstration shows two types of pseudorandom walks constructed from Gauss sums, an exponential (red) and a quadratic residue (blue) Gauss walk. The random walk starts at the origin, takes steps given by the terms of the exponential or quadratic residue Gauss sum modulo , and ends at the value of the Gauss sum. By a famous result of Gauss, if the modulus is a prime number, the two walks always end at the same point, located at or depending on the remainder of modulo 4. The exponential Gauss walk has a characteristic shape consisting of two spirals. The quadratic residue Gauss walk exhibits a more complex behavior whose shape is roughly determined by the remainder of modulo 24.

(Based on an undergraduate research project at the Illinois Geometry Lab by Ka Fung Tjin, Erqian Wang and Yifan Zhang and directed by A. J. Hildebrand.)

Given an integer , the exponential sum version of the Gauss sum modulo is defined by

and the quadratic residue version is defined by

,

where is the Jacobi symbol, which has values 0, 1, depending on the quadratic residue properties of modulo .

A famous result of Gauss states that when the modulus is a prime , the two sums and have the same value , given by

.

For composite moduli , the two sums are in general different, and the above formula does not necessarily hold.

It was shown by Lehmer [1] that the exponential Gauss walk always has the spiral-type shape observed in the visualization. On the other hand, the shape of the quadratic residue Gauss walk is more mysterious and has not been explored in the literature.