```
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 usinglexicographic ordering. Indeed, for
**any string**other than`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 theircyclic 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 therepresentative of the equivalence class as the first element. So therepresentatitives 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 generate3 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 providingan action of the group
`Z/pZ`

into the set of strings`X^p`

where`X`

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

takes astring`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 primehas size either`1`

or`p`

, since the size of the orbit divides thesize 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`

haveorbits of size`1`

. We have`|X|`

such necklaces.

- All other necklaces have size
`p`

.

- The rest of the proof follows similarly as before.