group-theory.md

Group theory

primitive element

Proof:

We hope to prove that

1. The number of primitive elements is the number of coprimes of |G| = φ(|G|).
2. If the order or an element is factor of |G|, it's not a primitive element.

Let ∝ ∈ G be a primitive element of group G, then we can define any element x_i ∈ G as:
x_i = f(∝, i) = ∝ ο ∝ ο ∝ ο ∝ ο ... ∝ ο ∝ ο    i times

• since ∝ is a primitive element, then 1 <= i <= |G|, such that.
  f(∝, i = 1) = ∝, and f(∝, i = |G|) = N.

An element is primitive if it reaches N for the first time after |G| steps.

1. if i is a factor of |G|:
   ∴  f(x_i, ord(x_i)) = f(∝, i * ord(x_i)) = f(∝, |G|) = N
   ∴  i * ord(x_i) = |G|, and i is factor of |G|.
   ∴  ord(x_i) is factor of |G|.
   ∵  ord(x_i) < |G|.
   ∴  x_i is not a primitive element of G, if |x_i| is a factor of |G|, and |x_i| = |G|/i

2. if i is comprime of |G|:
   ∴  f(x_i, ord(x_i)) = f(∝, i * ord(x_i)) = f(∝, m*|G|) = N.
   ∵  gcd(i, |G|) = 1
   ∴  i*|x_i| ≠ |G|.
   ∵  x_i must reach N after |x_i| steps, the equation would be
       i*|X_i| = m*|G| where m is an integer constant such that m < |G| ∵  i is coprime with |G|
   ∴  |x_i| >= |G| , but |x_i| <= |G|
   ∴  x_i = |G|
   ∴  x_i is a primitive element of group G, if i is coprime with |G|

3. if i has a common factor with |G|
   let f = gcd(i, |G|) >= 1, f < i < |G|.
   let's consider the group generated by the element x_f called F.
   ∵ f is a factor of i.
   ∴ x_i ∈ F.
   ∴ |x_i| <= |F| = |G|/f < |G|.
   ∴ X_i is not a primitive element of group G.
   also since x_i ∈ F, we can compute its order within the subgroup instead which is a maximum of f, depending on the relation between |F| = |G|/f, and j = i/f, where |F| and j are analgous to |G| and i in the original group.

Since the 3 possibilities above cover all possibilities for i. ∴ We can conclude that an element X_i ∈ G is a primitive element iff i is coprimes with |G|.
∴ the number of primitive elements of group G = the number of coprimes of |G| = φ(|G|).