- #1

Cheesycheese213

- 55

- 8

If gcd (a, p) = 1, then a

^{p-1}≡ 1 (mod p)

And then the proof was

__Lemma:__

Let p be prime, Let i, j ,k = Integers

If gcd (k, p) = 1 and ik ≡ jk (mod p)

then i ≡ j (mod p)

__Main Proof:__

Consider 1a, 2a, 3a, ..., (p - 1)a

Taking mod p is some arrangement of 1, 2, 3, ..., p - 1

Then (p - 1)! a

^{p-1}≡ (p - 1)! mod p

Therefore, a

^{p-1}≡ 1

But I couldn't really understand the part going from the 1, 2, 3, ..., p - 1 to the next step. Where and how did they get that equation?

Thanks!

P.S. Looking online, people did the proof a different way, but then the last line before the therefore is the same?