Let $p\geq 3$ be a prime. Determine whether there exists a permutation $(a_1,a_2,\dots,a_{p-1})\dots$ Problem. Let $p\geq 3$ be a prime. Determine whether there exists a permutation $(a_1,a_2,...,a_{p-1})$ of $(1,2,3,...,p-1)$ such that the sequence $\{ia_i\}_{i=1}^{p-1}$ contains $p-2$ distinct congruence classes modulo $p$.
My Attempt: Now by Wilson's theorem one can easily show that the sequence is not a complete set of residue classes modulo $p.$ Thus it can have at most $p-2$ congruence classes. In order to gain intuition I tried to play with a couple of examples but failed to gain any intuition.
The solution constructs $a_i$ such that they satisfy the equation $ia_i\equiv i+1\pmod p$ for each $1\leq i\leq p-2.$ I am unable to see any particular idea/insight that would have provided motivation for this choice. Moreover, is there any deeper implication/meaning of this result?
 A: I hope this answer your question somehow. Since I actually didn't solve the question by myself but read the solution you wrote above instead, so the things I will say below is not the motivation for picking $ia_i \equiv i+1 \pmod{p}$, put some thought that one might think to come up with the construction.
We need to pick $a_i \; (1 \le i \le p-1)$ so that $ia_i \equiv f(i) \pmod{p}$ where $f(i)$ is some polynomial we need to choose to satisfy:


*

*$f(i) \not\equiv f(j) \pmod{p}$ for at least $p-2$ values for $i$.

*$\dfrac{f(i)}{i} \not\equiv \dfrac{f(j)}{j} \pmod{p}$ (to make sure $a_j \not\equiv a_i \pmod{p}$) for all $1 \le i <j \le p-1$.


Now, look at the second condition, we consider polynomial $G(i,j)=f(i)j-f(j)i \pmod{p}$. We need to find $f(x)$ so that $G(i,j) \not\equiv 0 \pmod{p}$ for all possible $i \ne j$. 
A note that the higher the degree of $f(i)$, the more chances $G(i,j)$ has solution for $i,j$ so that $G(i,j) \equiv 0 \pmod{p}$, which is the thing we don't want. 
Let's take an example, if $f(i)=i^2+1$ then $$G(i,j)=(i^2+1)j-(j^2+1)i=(i-j)(ij-1) \equiv 0 \pmod{p}$$ is true for all $ij \equiv 1 \pmod{p}$. Now, look at $G(i,j)$ of the official solution with $f(i)=i+1$, which is $$G(i,j)=(i+1)j-(j+1)i=j-i \not\equiv 0 \pmod{p}$$ is true for all $i \ne j$.
Thus, all of these wants us to pick the polynomial $f(i)=ai+b$. This choice will automatically satisfy the second condition, which is $\dfrac{f(i)}{i} \not\equiv \dfrac{f(j)}{j} \pmod{p}$.
Now, for the first condition, it is equivalent to $ai+b \not\equiv aj+b \pmod{p}$ which is true for all $p \nmid a$. We pick $a=1$. $b$ can be any number but for convenience, pick $b=1$.
This gives us the choice of $ia_i \equiv i+1 \pmod{p}$.
