We are getting closer to Rabin-Miller primarility test and RSA. Our final prerequisites are involutions and avoiding elements, basic parts of elementary group theory.

## Sources:

## Theory:

Let be a group, two of its elements. We say that **avoids** in if and for every . Note that this condition is symmetric, i.e. avoids if and only if avoids . Realize that if is cyclic with a generator , then, by definition of cyclic group, there is no such that avoids .

If is of order , then such is said to be an **involution**. So, is an involution, if and . As an example, consider . Then there is only one involution, namely (note that the order of 0 is 1, not 2).

Combining these two previous definitions, we can realize when it is the case that an element avoids an involution . Well, it happens if and only if for every integer (this condition is unchanged) and (this condtitions is greatly reduced).

## Properties:

- Let , where are finite groups, . If the number of that avoids in is at least for some , then the number of elements of that avoids is at least .
- Let . The order of is the .
- Let be a prime number, . Then an element is of order , where .
- Suppose we have some naturals , where . An element is an involution in . The number of elements that avoid is at least .

## Examples:

#### Example 1:

What are the elements of that avoid an element ?

#### Solution:

Use the definition of avoiding and proceed case-by-case:

- : – not avoiding;
- : – not avoiding;
- : – not avoiding;
- : Multiples of modulo are and , so no . Multiples of modulo are , and 2, so no . It follows that avoids in .
- : – not avoiding;
- : – not avoiding.

Therefore, is the only element that avoids in .

#### Example 2:

Determine all involutions in ?

#### Solution:

We can proceed case-by-case and for every element we can determine its order

- is of order ;
- is of order (what makes a cyclic group);
- is of order and hence, an involution;
- is of order (another generator).

Therefore, the only involution in is the element .

#### Example 3:

What are all the involutions in ?

#### Solution:

Well, is of order 3, and the mighty Lagrange theorem says that the order of any element must divide the order of the whole group. However, (order of a potential involution) does not divide , so there is no involution in .

## Problems:

#### Problem 1:

What are the elements of that avoid an element ?

#### Problem 2:

Find all involutions in .

#### Problem 3:

Find all involutions in .