```
000
001
010
011
100
101
110
111
```

To make use of $\mod 3$, we're going to treat our strings as `011`

looks like:
```
*-→ 0 -*
| |
| ↓
1 ←--- 1
```

So we have three possible rotations of the string `011`

:
```
011
110
101
```

- Each of these rotations are unique, since they can be totally ordered using lexicographic ordering. Indeed, for
other than*any string*`000`

,`111`

, all of its rotations are unique.

- So we can count the above 7 strings with equivalence class representatives. These representatives are those strings that are the lex smallest in their cyclic shifts. (Why are cyclic shifts
*so important*?)

```
Cyclic subshifts of strings:
---------------------------
000, 000, 000
001, 010, 100
011, 110, 101
111, 111, 111
```

- We've written the strings along with their cyclic subshifts, with the representative of the equivalence class as the first element. So the representatitives are
`000, 001, 011, 111`

. Note that two of these (`000, 111`

) are equal to their cyclic subshifts. All of the others are distinct, and generate 3 elements.

- So we can count the above strings as:

```
all strings = {shifts of 001, 011}U{000, 111}
|all strings| = |{shifts of 001, 011}|+|{000, 111}|
no. of shifts = 3*(no. of representatives)
2^3 = 3 * (no. of representatives) + 2
2^3 = 3 * (no. of representatives) + 2
2^3 % 3 = 2
```

In general, for `x^p % p`

, we will get `x`

strings that contain the same letter.
These will not have elements in their cyclic shift equivalence classes. The
other strings will be generated as the smallest cyclic subshift of some
string.
`p`

is not prime? `p = 4`

. In this case, I can pick the string `s = 0101`

. It has shifts:
```
0101 <-
1010
0101 <-
1010
```

so two of its shifts overlap, hence we will double-count the string `0101`

if I counted its equivalence class as having size `4`

.
- How does this relate to group theory? Well, what we are doing is providing an action of the group
`Z/pZ`

into the set of strings`X^p`

where`X`

is some set. Our group action for a number`n ∈ Z/pZ`

takes a string`s ∈ X^p`

to its cyclic shift by`n`

characters.

- We are then using the fact that the orbits of an action when
`p`

is prime has size either`1`

or`p`

, since the size of the orbit divides the size of the group`Z/pZ`

, which is`p`

, a prime. The divisors of`p`

are only`1`

and`p`

. Therefore, the size of the orbit is either`1`

or`p`

.

- Only necklaces that have identical elements like
`000`

and`111`

have orbits of size`1`

. We have`|X|`

such necklaces.

- All other necklaces have size
`p`

.

- The rest of the proof follows similarly as before.