Establish that ## a\equiv b\pmod {p} ##

  • Thread starter Math100
  • Start date
In summary: So you meant to argue that ##a-b\equiv 0\pmod{p}##, since ##a\equiv b\pmod{p}##, is not possible. I am not sure, this is "cleaner" than what you did before, but it's always an option.
  • #1
Math100
792
220
Homework Statement
Assuming that ## a ## and ## b ## are integers not divisible by the prime ## p ##, establish the following:
If ## a^{p}\equiv b^{p}\pmod {p} ##, then ## a\equiv b\pmod {p} ##.
Relevant Equations
None.
Proof:

Suppose ## a^{p}\equiv b^{p}\pmod {p} ##, where ## a ## and ## b ## are integers not divisible by the prime ## p ##.
Then ## p\nmid a ## and ## p\nmid b ##.
Applying the Fermat's theorem produces:
## a^{p}\equiv a\pmod {p}, b^{p}\equiv b\pmod {p} ##.
Thus ## a^{p}\equiv a\equiv b^{p}\equiv b\pmod {p} ##.
Therefore, if ## a^{p}\equiv b^{p}\pmod {p} ##, then ## a\equiv b\pmod {p} ##.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: Assuming that ## a ## and ## b ## are integers not divisible by the prime ## p ##, establish the following:
If ## a^{p}\equiv b^{p}\pmod {p} ##, then ## a\equiv b\pmod {p} ##.
Relevant Equations:: None.

Proof:

Suppose ## a^{p}\equiv b^{p}\pmod {p} ##, where ## a ## and ## b ## are integers not divisible by the prime ## p ##.
Then ## p\nmid a ## and ## p\nmid b ##.
Applying the Fermat's theorem produces:
## a^{p}\equiv a\pmod {p}, b^{p}\equiv b\pmod {p} ##.
Thus ## a^{p}\equiv a\equiv b^{p}\equiv b\pmod {p} ##.
Therefore, if ## a^{p}\equiv b^{p}\pmod {p} ##, then ## a\equiv b\pmod {p} ##.
Right, but what do you need ## p\nmid a ## and ## p\nmid b ## for?

If ##p\,|\,a^p\equiv b^p## then ##p\,|\,a ## and ##p\,|\,b## so ##a\equiv b\equiv 0\pmod{p}.##
 
  • #3
fresh_42 said:
Right, but what do you need ## p\nmid a ## and ## p\nmid b ## for?

If ##p\,|\,a^p\equiv b^p## then ##p\,|\,a ## and ##p\,|\,b## so ##a\equiv b\equiv 0\pmod{p}.##
I just realized that I don't need them for anything.
 
  • #4
fresh_42 said:
Right, but what do you need ## p\nmid a ## and ## p\nmid b ## for?

If ##p\,|\,a^p\equiv b^p## then ##p\,|\,a ## and ##p\,|\,b## so ##a\equiv b\equiv 0\pmod{p}.##
So should I include/add the line of ## p\,|\,a^p\equiv b^p##?
 
  • #5
I think you can argue that $$(a-b)$$ is always a factor of $$a^p-b^p$$and use that Integers are an integral domain.
 
  • #6
WWGD said:
I think you can argue that $$(a-b)$$ is always a factor of $$a^p-b^p$$and use that Integers are an integral domain.
Not if ##a\equiv b\pmod{p}.## Then you cannot divide.
 
  • #7
Math100 said:
I just realized that I don't need them for anything.

fresh_42 said:
Not if ##a\equiv b\pmod{p}.## Then you cannot divide.
I don't mean dividing. I mean, in an Integral domain, as in our case, if a.b=0, then either a=0 or b=0 ( mod p).
 
  • #8
Sorry @fresh_42 I have always believed that 0 is a factor of 0.

I have never seen someone say ##x^2-1## factors into ##(x-1)(x+1)##, except when ##x=\pm 1##
 
  • #9
Office_Shredder said:
Sorry @fresh_42 I have always believed that 0 is a factor of 0.

I have never seen someone say ##x^2-1## factors into ##(x-1)(x+1)##, except when ##x=\pm 1##
Yes, I thought he meant ##\dfrac{a^p-b^p}{a-b}=a^{p-1}+\ldots \pmod{p}##
 

FAQ: Establish that ## a\equiv b\pmod {p} ##

1. What does it mean for two numbers to be congruent modulo a prime number?

Two numbers, a and b, are said to be congruent modulo a prime number p if they have the same remainder when divided by p. This is denoted as a ≡ b (mod p). In other words, a and b have the same remainder when divided by p, and the difference between them is a multiple of p.

2. How do you prove that two numbers are congruent modulo a prime number?

To prove that two numbers, a and b, are congruent modulo a prime number p, you need to show that their difference, a - b, is divisible by p. This can be done by using the definition of congruence and manipulating the equation to show that a - b = kp, where k is an integer.

3. Can two numbers be congruent modulo a non-prime number?

Yes, two numbers can be congruent modulo a non-prime number. The definition of congruence modulo a number p does not require p to be a prime number. However, if p is not a prime number, there may be more than one pair of numbers that are congruent modulo p.

4. What are some applications of congruence modulo a prime number?

Congruence modulo a prime number has many applications in number theory, cryptography, and computer science. It is used in encryption algorithms, such as the RSA algorithm, to ensure the security of data. It is also used in the study of prime numbers and their properties.

5. How is congruence modulo a prime number related to modular arithmetic?

Congruence modulo a prime number is a concept in modular arithmetic. Modular arithmetic is a system of arithmetic where numbers "wrap around" after reaching a certain value, called the modulus. Congruence modulo a prime number is a way of expressing this wrapping around, where two numbers are considered equivalent if they have the same remainder when divided by the prime number.

Back
Top