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
816
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.
 
Since ##px^9+q## is the factor, then ##x^9=\frac{-q}{p}## will be one of the roots. Let ##f(x)=27x^{18}+bx^9+70##, then: $$27\left(\frac{-q}{p}\right)^2+b\left(\frac{-q}{p}\right)+70=0$$ $$b=27 \frac{q}{p}+70 \frac{p}{q}$$ $$b=\frac{27q^2+70p^2}{pq}$$ From this expression, it looks like there is no greatest value of ##b## because increasing the value of ##p## and ##q## will also increase the value of ##b##. How to find the greatest value of ##b##? Thanks
Back
Top