Let $n$ be an integer and $p>n$ be a prime. Assume for simplicity that $p-1$ is divisible by $n$, and that $p-1=nk$. Let $a$ be a member of $(\mathbf Z/p\mathbf Z)^*$ and assume that $a\neq 1$. I am trying to put a bound on the cardinality of the set $S=\{x\in (\mathbf Z/p\mathbf Z)^*:\ x\pmod{n} = xa\pmod{n}\}$.
(Given a member $y\in (\mathbf Z/p\mathbf Z)^*$, by "$y\pmod{n}$" we mean the remainder which the unique representative of $y$ in $\{1, \ldots, p-1\}$ leaves when divided by $n$).
Generating a little bit of data by writing a code, I feel that $|S|\leq 2p/n$, though I am not confident.
Basically, we are trying to find the number of pairs $(\beta, i)$ with $\beta\in \{0, 1, \ldots, p-1\}$ and $i\in \{1, \ldots, n\}$ such that
$$n\alpha +i\equiv (n\beta+i)a\pmod{p}$$ for some $\alpha\in \{0, 1, \ldots, p-1\}$. But this formulation has not helped me yet.
Relevance of the Title of the Post.
For each $1\leq i\leq n$, consider the arithmetic progression $A_i=\{i, n+i, \ldots, n(k-1)+i\}$ in $(\mathbf Z/p\mathbf Z)^*$. Then $S$, as defined above, is given by $$S= \bigcup_{i=1}^n(aA_i\cap A_i)$$ where $aA_i$ is by definition $\{ay:\ y\in A_i\}$, that is $aA_i$ is the translation of $A_i$ by $a$. So if we could put a bound on $|aA_i\cap A_i|$, then we can get a bound on $|S|$.
The Question is Prompted By...
Problem 4 of Chapter 2 of Alon and Spencer's The Probabilistic Method is the following:
Let $p>n>10m^2$, with $p$ prime, and $0< a_1< a_2< \cdots<a_m<p$ be integers. Prove that there is an integer $x$, $0< x< p$ for which the $m$ numbers $$(xa_i\pmod{p}\pmod{n}), \quad 1\leq i\leq m$$ are pairwise distinct.