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

  • Context: Undergrad 
  • Thread starter Thread starter StudentR
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the properties of congruences, specifically examining the relationship between the congruence \( a^m \equiv a^n \mod p \) and the implication that \( m \equiv n \mod (p-1) \). Participants are exploring the validity of this implication and seeking a formal proof.

Discussion Character

  • Exploratory
  • Technical explanation
  • Homework-related

Main Points Raised

  • One participant questions the validity of the implication \( a^m \equiv a^n \mod p \) leading to \( m \equiv n \mod (p-1) \) and seeks a formal proof.
  • Another participant suggests trying numerical examples to test the initial assumption.
  • A different viewpoint emphasizes that the statement should be reconsidered, noting that raising one to any power remains one.
  • One participant provides a counterexample, stating that \( a^m \equiv a^n \mod p \) does not imply \( m \equiv n \mod p \) by citing \( m = p \) and \( n = 1 \) as a case where the implication fails, referencing Fermat's Little Theorem as relevant to understanding the congruences.

Areas of Agreement / Disagreement

Participants do not appear to reach a consensus on the validity of the implication \( m \equiv n \mod (p-1) \). Multiple competing views are presented, with some participants questioning the initial assumption and others providing counterexamples.

Contextual Notes

The discussion highlights the need for careful consideration of the conditions under which congruences hold, particularly in relation to Fermat's Little Theorem. There are unresolved assumptions regarding the nature of \( a \) and the specific values of \( m \) and \( n \) in the context of the congruences.

StudentR
Messages
7
Reaction score
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
What made you think that's true? Did you try some numerical examples?
 
One would first go about thinking what the correct statement of the above should be: one raised to any power is still one.
 
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:

Similar threads

Undergrad ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K
Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
MHB Congruences - Rotman - Proposition 1.58 - Second Question
  • · Replies 1 ·
Replies
1
Views
2K
Graduate When n*(n+1)/2 - k is never a square
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How Do Properties of Modulus Algebra Apply to RSA and Diffie-Hellman?
  • · Replies 12 ·
Replies
12
Views
3K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K
Graduate What Does a = b (mod pZp) Mean in p-adic Numbers?
  • · Replies 4 ·
Replies
4
Views
4K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K