Let a be a positive integer and p be a prime. Consider the set of circular...

Transcribed Image Text:

Let a be a positive integer and p be a prime. Consider the set of circular necklaces with p equally spaced beads, each of which is colored in one of a colors. (a) How many necklaces are there in total? (Ignore rotations and reflections.) (b) If we now declare two necklaces to be the same if we can rotate one into the other, how many different necklaces are there in total? [Hint: There are two cases: one where the beads are all the same color, and the other where they are not.] (c) Show that a = a (mod p) for any a, and that ap-1 = 1 (mod p) when p does not divide a. [Hint: Part (b) is counting something, so it is always an integer.] (d) Find the remainder when 22018 is divided by 43. Let a be a positive integer and p be a prime. Consider the set of circular necklaces with p equally spaced beads, each of which is colored in one of a colors. (a) How many necklaces are there in total? (Ignore rotations and reflections.) (b) If we now declare two necklaces to be the same if we can rotate one into the other, how many different necklaces are there in total? [Hint: There are two cases: one where the beads are all the same color, and the other where they are not.] (c) Show that a = a (mod p) for any a, and that ap-1 = 1 (mod p) when p does not divide a. [Hint: Part (b) is counting something, so it is always an integer.] (d) Find the remainder when 22018 is divided by 43.