In my book there are many proofs that looks like this in the primitive roots chapter:
For the record for this particular proof is the order of , is an integer, and is Euler's totient function.
The last step (where you end up with at the end) is the only part that isn't clear to me and would like someone to tell me if my justification is correct:
The way I have justified the last step is that since we can cancel in (since they are also congruent to each other... do congruencies work like this?) and get
also since I can further cancel to get:
The problem is I still don't fully understand how congruencies work.
If my justification is incorrect and if I had to write the proof on my own how would I get from