Hi,

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

to

?