Editing Primitive root modulo n (section)

==Examples==

For example, if {{nowrap|{{mvar|n}} {{=}} 14}} then the elements of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} are the congruence classes {1, 3, 5, 9, 11, 13}; there are {{nowrap|{{mvar|φ}}(14) {{=}} 6}} of them. Here is a table of their powers modulo 14:

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (mod 14)
  1 :   1
  3 :   3,  9, 13, 11,  5,  1 
  5 :   5, 11, 13,  9,  3,  1
  9 :   9, 11,  1
 11 :  11,  9,  1
 13 :  13,  1

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.

For a second example let {{nowrap|{{mvar|n}} {{=}} 15 .}} The elements of <math>\mathbb{Z}</math>{{su|b=15|p=×}} are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are {{nowrap|{{mvar|φ}}(15) {{=}} 8}} of them.

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (mod 15)
  1 :   1
  2 :   2,  4,  8, 1 
  4 :   4,  1
  7 :   7,  4, 13, 1
  8 :   8,  4,  2, 1
 11 :  11,  1
 13 :  13,  4,  7, 1
 14 :  14,  1

Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, {{nowrap|{{mvar|λ}}(15) {{=}} 4}}, where {{mvar|λ}} is the [[Carmichael function]]. {{OEIS|id=A002322}}