In modular arithmetic, a number g is a primitive root modulo n, if every number m from 1..(n-1) can be expressed in the form of
. As an example, 3 is a primitive root modulo 7:
![{\displaystyle 3^{1}\equiv 3\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2fd49f9bb4f493071419f54589d539a969a0a21)
![{\displaystyle 3^{2}\equiv 2\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66867f62b8c558ba573726a685c14cba3ec45bed)
![{\displaystyle 3^{3}\equiv 6\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b4423357519902f245b7582188be234c1c04f0d)
![{\displaystyle 3^{4}\equiv 4\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f153f00bcd9e993c3b7f839dce80216c188c0ef)
![{\displaystyle 3^{5}\equiv 5\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aeef08611a3d967e10ce36d7753fa910d93a5bde)
![{\displaystyle 3^{6}\equiv 1\ {\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6ce5198cbd6ef4d2e4d1ab69f734127afa5779e)
All the elements
of the group modulo 7 can be expressed that way. The number 2 is no primitive root modulo 7, because
![{\displaystyle 2^{3}=8\equiv 1{\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a94cda2762b6fbedf4d06c23c89c16f4e42f6573)
and
![{\displaystyle 2^{6}=64\equiv 1{\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fb73234c0fdc12956306555aad2bc279592f2c4)