Primitive root modulo n

2017-04-12T13:54:00Z

79.248.250.129:

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 <math>g^x\equiv m \pmod n</math>. As an example, 3 is a primitive root modulo 7:
:<math>3^1 \equiv 3\ \pmod 7</math>
:<math>3^2 \equiv 2\ \pmod 7</math>
:<math>3^3 \equiv 6\ \pmod 7</math>
:<math>3^4 \equiv 4\ \pmod 7</math>
:<math>3^5 \equiv 5\ \pmod 7</math>
:<math>3^6 \equiv 1\ \pmod 7</math>
All the elements <math>1, 2, \ldots, 6</math> of the group modulo 7 can be expressed that way. The number 2 is no primitive root modulo 7, because
:<math>2^3=8 \equiv 1 \pmod 7</math>
and
:<math>2^6=64 \equiv 1 \pmod 7</math>

[[Category:Number theory]]

{{math-stub}}

TCS Wiki - User contributions [en]

Primitive root modulo n