Problem from Discrete Mathematics and its application for Rosen section 4.4

Question

This exercise outlines a proof of Fermat’s little theorem.

a) Suppose that a is not divisible by the prime p. Show that no two of the integers 1 · a, 2 · a, . . . , (p − 1)a are congruent modulo p.

b) Conclude from part (a) that the product of 1, 2, . . . , p − 1 is congruent modulo p to the product of a, 2a, . . . , (p − 1)a. Use this to show that (p − 1)! ≡ a p−1 (p − 1)! (mod p).

I already solved the first problem (a) but I couldn't solve Problem (b) So can any one please help me to solve it, mean problem (b) ?

Note : I can't use Fermat’s little theorem to prove it as this problem is to prove the Fermat’s little theorem

Answer 1

b) The sets $\{1,2,\dots,p-1\}$ and $\{a,2a,\dots,(p-1)a\}$ are the same modulo $p$ by item (a). So the product of their elements must be equal: $(p-1)! \equiv a\cdot 2a \cdot {\dots} \cdot (p-1)a \equiv a^{p-1}(p-1)! \pmod p$.

Answer 2

a) Suppose there are two such: $a\cdot i$ and $a\cdot j$, then $p\mid a(i-j)$ so $p\mid i-j$ and thus $p\mid |i-j|$. But then $p\leq |i-j|$ since $i \ne j$. But also $|i-j|\leq p-1$. A contradiction.