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:

$\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)$?

2. 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)$?
If you don't fully understand congruences, you should go back and learn those before jumping into like order and primitive roots.

Anyway, $\displaystyle (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 $\displaystyle \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.