Let $p$ be a prime number and $F=\left \{0,1,2,...,p-1 \right \}$. Let $A$ be a proper subset of $F$ that satisfies the following property: if $a,b \in A$, then $ab+1$ (mod $p$) $ \in A$. How many elements can $A$ have? (Justify your answer.)
Problem
Source: : 2nd Memorial Mathematical Competition "Aleksandar Blazhevski - Cane" - Problem 2
Tags: number theory, prime numbers
13.01.2021 06:19
First note that if $A \subsetneq F$ then $0,1 \ne a$. This readily shows that $|A| = 0$ if $p = 2$. Now suppose $p > 3$. We claim that $|A| = 0$ unless $-3$ is a quadratic residue $\pmod p$ or $p =3$, in which case $|A| = 1$ is the only other possible answer. Henceforth assume $0,1\not \in A$ and $|A| \ge 2$. We will derive a contradiction. Note that the map $m_{a,b}: x \mapsto ax+b$ maps $A$ onto itself if $b = 1$ and $a\in A$. Consider now the cycle decomposition of $m_{a,b}$ where $b\in F$ and $a\ne 0$. Note that there is at most one cycle of length $1$. We claim that all cycles have length $1$ or $\delta(a)$ where $\delta(a)$ is defined to the the multiplicative order of $a$. Note that $m_a^{(n)}(x) = a^nx + \frac{a^n-1}{a-1}$ hence $m_a^{(n)}(x) = x \iff (a^n-1)(x + \frac{1}{a-1}) = 0$, as claimed. Claim: Suppose $u_1,\dots,u_k\in A$ have orders $\delta(u_1), \delta(u_k)$ then there exist $a,b$ such that $m_{a,b}:A \to A$ is bijective and $d(a) = lcm[d(u_1),...,d(u_k)]$. Proof: Choose $\alpha_i \text{ s.t. } \prod_i u_i^{\alpha_i}$ has order $[d(u_i)]$ and let $m_{a,b} = m_{u_1,1}^{(\alpha_1)}\circ m_{u_2,1}^{(\alpha_2)}\circ\dots\circ m_{u_k,1}^{(\alpha_k)}$. Since composition of linear transformations is linear there are $a,b$ such that the above holds. Moreover $a = \prod_i u_i^{\alpha_i}$ has order $> 1 \implies a \ne 1$. Since composition of bijective transformations is bijective it follows that $m_{a,b}:A \to A$ is bijective, as desired. $\blacksquare$ Now let $L = lcm(\delta(A))$ and choose $m_{a,b}$ in the above claim with $\delta(a) = L$. Then $|A| \ge 2 \implies |A| \ge L$. However, the number of elements with order dividing $L$ in $F$ other than $1$ is at most $\sum_{d|L, d< L} \phi(\frac{L}{d}) = L-1 < L$, contradiction.
13.01.2021 06:23
Basically ELMO 2019 P5; see my solution there.