# Thread: Minor point of clarification regarding congruencies

1. ## Minor point of clarification regarding congruencies

Hi,

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

$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 $t$ is the order of $a (mod \ m)$, $k$ is an integer, and $\phi(m)$ is Euler's totient function.

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

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

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

$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

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

2. Originally Posted by BBAmp
Hi,

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

$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 $t$ is the order of $a (mod \ m)$, $k$ is an integer, and $\phi(m)$ is Euler's totient function.

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

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

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

$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

$a^{t+k\phi(m)} \equiv 1(mod \ m)$ to $a^{t} \equiv 1 (mod \ m)$?
If you don't fully understand congruences, you should go back and learn those before jumping into like order and primitive roots.

Anyway, $(a^k)^{\phi(m)}\equiv1\bmod{m}\implies a^t(a^k)^{\phi(m)}\equiv a^t\cdot 1=a^t \bmod{m}$.

But you're given $\text{ord}_m(a)=t \implies a^t\equiv1\bmod{m}$.

3. I looked back and a small proof clarified everything. I believe this was the only thing that was confusing me in congruences so I am set for the coming chapters.