Give an example to show that ## a^{k}\equiv b^{k}\pmod {n} ## ....

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Example
AI Thread Summary
The discussion presents a counterexample to demonstrate that if \( a^k \equiv b^k \pmod{n} \) and \( k \equiv j \pmod{n} \), it does not necessarily imply \( a^j \equiv b^j \pmod{n} \). Using \( a=2, b=3, k=2, j=7, \) and \( n=5 \), it shows that \( 2^2 \equiv 3^2 \pmod{5} \) holds true, but \( 2^7 \not\equiv 3^7 \pmod{5} \). Another example illustrates that integers ending in 1 and 3 can also fail this condition. The discussion emphasizes the importance of understanding modular exponentiation beyond small powers. Ultimately, the examples effectively highlight the limitations of the initial equivalence condition.
Math100
Messages
813
Reaction score
229
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} ##.
 
  • Like
Likes fresh_42 and Delta2
Physics news on Phys.org
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)
 
Math100 said:
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 ##
 
Math100 said:
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.
 
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
Back
Top