Congruence Question: Proving m=n (mod p-1)

  • Thread starter StudentR
  • Start date
In summary, the conversation discusses a question about congruences and whether the statement "a^m = a^n (mod p) implies m = n (mod p-1)" is true. The conversation suggests using the little fermat theorem to understand the second set of congruences.
  • #1
StudentR
7
0
Congruence Question !

I have a question regarding congruences, I could not find this result in the textbooks.

(note to readers: a^k means a to the power k, and = means congruent)

If we have a congruence: a^m = a^n (mod p) for a,m,n,p>0

It seems likely to deduce that m = n (mod p)

However after attempting a homework question, I discover that

a^m = a^n (mod p) implies m = n (mod p-1)

Is this result true? How does one go about to formally prove the above statement?

Thank you...
 
Physics news on Phys.org
  • #2
What made you think that's true? Did you try some numerical examples?
 
  • #3
One would first go about thinking what the correct statement of the above should be: one raised to any power is still one.
 
  • #4
Consider a^m = a^n (mod p) => m = n (mod p) for m=p, n=1. Then it's obviously not true, and proof that it's not true follows immediately from the little fermat theorem.

Hint: the little fermat theorem is key to understanding the 2nd set of congruences as well
 
Last edited:

1. What is congruence?

Congruence is a mathematical concept that describes the relationship between two numbers being equivalent in a specific way. Two numbers are congruent if they have the same remainder when divided by a given number.

2. What is the purpose of proving m=n (mod p-1)?

The purpose of proving m=n (mod p-1) is to show that two numbers, m and n, are congruent modulo p-1. This means that when m and n are divided by p-1, they will have the same remainder. This can be useful in many areas of mathematics, such as number theory and cryptography.

3. How do you prove congruence?

To prove congruence, you need to show that the two numbers have the same remainder when divided by the given number. This can be done by performing the division and comparing the remainders, or by using the congruence notation m≡n (mod p-1).

4. What is the significance of p-1 in congruence?

In congruence, p-1 is the modulus or the number that the two numbers, m and n, are being divided by. It is important because it determines the relationship between the two numbers and whether or not they are congruent.

5. Can congruence be proved for all numbers?

No, congruence can only be proved for specific numbers and moduli. It is not applicable to all numbers. Additionally, some numbers may have multiple congruent values depending on the modulus chosen.

Similar threads

I Proof for a congruence relation
    • Linear and Abstract Algebra
Replies
17
Views
1K
I Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
    • Linear and Abstract Algebra
Replies
7
Views
829
Prove ## a/d\equiv b/d \mod n/d ##.
    • Precalculus Mathematics Homework Help
Replies
2
Views
694
MHB Prove Polynomial Congruence $(x+y)^n \equiv x^n + y^n$ (mod $p$)
    • General Math
Replies
2
Views
1K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
    • Precalculus Mathematics Homework Help
Replies
17
Views
2K
When n*(n+1)/2 - k is never a square
    • Linear and Abstract Algebra
Replies
2
Views
1K
MHB Congruences - Rotman - Proposition 1.58 - Second Question
    • Linear and Abstract Algebra
Replies
1
Views
1K
Prove that the congruences admit a simultaneous solution
    • Precalculus Mathematics Homework Help
Replies
5
Views
926
I Congruence Subgroups and Modular Forms Concept Questions
    • Linear and Abstract Algebra
Replies
1
Views
1K
B Transformation Rules For A General Tensor M
    • Linear and Abstract Algebra
Replies
1
Views
823

Hot Threads

Recent Insights

Back
Top