Originally Posted by

**BBAmp** Hi,

In my book there are many proofs that looks like this in the primitive roots chapter:

$\displaystyle a^{t+k\phi(m)} \equiv a^{t}(a^{k})^{\phi(m)} \equiv a^{t} \equiv 1 (mod \ m)$

For the record for this particular proof $\displaystyle t$ is the order of $\displaystyle a (mod \ m)$, $\displaystyle k$ is an integer, and $\displaystyle \phi(m)$ is Euler's totient function.

The last step (where you end up with $\displaystyle a^{t} \equiv 1 (mod \ m)$ 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 $\displaystyle (a, m) = 1$ we can cancel $\displaystyle a^{t}$ in $\displaystyle a^{t}(a^{k})^{\phi(m)} \equiv a^{t}$ (since they are also congruent to each other... do congruencies work like this?) and get

$\displaystyle (a^{k})^{\phi(m)} \equiv 1 \equiv 1 (mod \ m)$.

also since $\displaystyle a^{t+k\phi(m)} \equiv (a^{k})^{\phi(m)}$ I can further cancel $\displaystyle (a^{k})^{\phi(m)}$ to get:

$\displaystyle a^{t} \equiv 1(mod \ m)$.

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

$\displaystyle a^{t+k\phi(m)} \equiv 1(mod \ m)$ to $\displaystyle a^{t} \equiv 1 (mod \ m)$?