Given a prime number . There are people in a circle, each one came up with a positive integer and then wrote down the remainder when divided by on a piece of paper. Then everyone showed their piece of paper to the neighbor on the right, computed the product of their number on a piece of paper and their neighbor's number, and wrote down the second number, which is the remainder of a product divided by . What is the largest value that could be, if it is known that everyone's first numbers are pairwise distinct, and each piece of paper has two distinct numbers written down?
Solution
Clearly, there cannot be more than different numbers. It follows from the condition of the problem, that could not be someone's number on the first step, since then that person will have it on the second step as well. Also, no one can have as a first number, since then the neighbor on the left will have two equal numbers. We will show that the conditions hold for .
Indeed, let the following consecutive numbers be written down on the first step from left to right: . They are all pairwise distinct. Assume that after the second step someone's two numbers are equal. If it's one of the first people, it means that the product , where , has the same remainder when divided by , as the number . But then their difference is divisible by , that is, is divisible by a prime number , thus, , which is not possible. If the -th person has two equal numbers, then the number will be multiplied by , but then two numbers will be different, since is not divisible by .