Counterexample: a^k ≡ b^k (mod n) and k ≡ j (mod n) doesn't imply a^j ≡ b^j (mod n)

[Math100]

Homework Statement

Give an example to show that $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ need not imply that $a^{j}\equiv b^{j}\pmod {n}$.

Relevant Equations

None.

Disproof:

Here is a counterexample:
Let $a=2, b=3, k=2, j=7$ and $n=5$.
Then $2^{2}\equiv 3^{2}\pmod {5}$ and $2\equiv 7\pmod {5}$.
But note that $2^{7}\not\equiv 3^{7}\pmod {5}$.
Thus $a^{j}\not\equiv b^{j}\pmod {n}$.
Therefore, $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ does not imply that $a^{j}\equiv b^{j}\pmod {n}$.

 

[anuttarasammyak]

Another counter example
Say a is any decimal positive integer that ends with 1 and b is any decimal positive integer that ends with 3.
$$a^4 \equiv b^4 \equiv 1 (mod \ 10)$$
$$4 \equiv 14 (mod \ 10)$$
$$a^{14} \equiv 1(mod \ 10), b^{14} \equiv 9 (mod \ 10)$$

 

[SammyS]

Homework Statement:: Give an example to show that $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ need not imply that $a^{j}\equiv b^{j}\pmod {n}$.
Relevant Equations:: None.

Disproof:

Here is a counterexample:
Let $a=2, b=3, k=2, j=7$ and $n=5$.
Then $2^{2}\equiv 3^{2}\pmod {5}$ and $2\equiv 7\pmod {5}$.
But note that $2^{7}\not\equiv 3^{7}\pmod {5}$.
Thus $a^{j}\not\equiv b^{j}\pmod {n}$.
Therefore, $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ does not imply that $a^{j}\equiv b^{j}\pmod {n}$.

Looks good.
You might want to at least demonstrate that you actually know that $2^{7}\not\equiv 3^{7}\pmod {5}$ .

$2^7 \equiv 3 \pmod 5$ whereas $3^7 \equiv 2 \pmod 5$

 

[fresh_42]

Homework Statement:: Give an example to show that $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ need not imply that $a^{j}\equiv b^{j}\pmod {n}$.
Relevant Equations:: None.

Disproof:

Here is a counterexample:
Let $a=2, b=3, k=2, j=7$ and $n=5$.
Then $2^{2}\equiv 3^{2}\pmod {5}$ and $2\equiv 7\pmod {5}$.
But note that $2^{7}\not\equiv 3^{7}\pmod {5}$.
Thus $a^{j}\not\equiv b^{j}\pmod {n}$.
Therefore, $a^{k}\equiv b^{k}\pmod {n}$ and $k\equiv j\pmod {n}$ does not imply that $a^{j}\equiv b^{j}\pmod {n}$.

What @SammyS said, looks good. To know $2^7=128\equiv 3\pmod 5$ and $3^7=2187\equiv 2\pmod 5$ would have helped a lot. Most people have only the first, say four or five, powers in mind. It could be omitted in a book but should be told in an exercise.