Order of an Integer mod m (number theory help)

  • Thread starter Thread starter Ch1ronTL34
  • Start date Start date
  • Tags Tags
    Integer Theory
Click For Summary
SUMMARY

The discussion focuses on proving that if \( ab \equiv 1 \mod m \), then \( \text{ord}_m(a) = \text{ord}_m(b) \). The order of an integer \( a \) modulo \( m \), denoted as \( \text{ord}_m(a) \), is defined as the smallest integer \( k \) such that \( a^k \equiv 1 \mod m \). The example provided illustrates that \( \text{ord}_{10}(7) = 4 \) since \( 7^4 \equiv 1 \mod 10 \). The discussion emphasizes the relationship between the orders of \( a \) and \( b \) when their product is congruent to 1 modulo \( m \.

PREREQUISITES
  • Understanding of modular arithmetic and congruences
  • Familiarity with the concept of the order of an integer modulo \( m \)
  • Basic knowledge of number theory
  • Ability to manipulate exponents in modular equations
NEXT STEPS
  • Study the properties of modular inverses in number theory
  • Explore the concept of group theory and its relation to modular arithmetic
  • Learn about Euler's theorem and its applications in modular arithmetic
  • Investigate the relationship between the orders of elements in multiplicative groups modulo \( m \)
USEFUL FOR

This discussion is beneficial for students and enthusiasts of number theory, particularly those studying modular arithmetic and its applications in cryptography and algebra.

Ch1ronTL34
Messages
12
Reaction score
0
Ok, my question is:

Show that if ab == 1 mod m, then
ord(m)a=ord(m)b

(Note that == means congruent) and ord(m)a means the order of a mod m

I know that if a^k==1 mod m, then the ord(m)a is the smallest integer k such that the congruence holds. For example,
ord(10)7=4 since 7^4==1 mod m.

I'm thinking, a^(ord(m)a)==1 mod m so maybe ab=a^ord(m)a and also:
b^(ord(m)b)==1 mod m so ab=b^ord(m)a

Am i on the right track? Thanks!
 
Physics news on Phys.org
I dislike unnecessary notation, so suppose the order of a is m, then what is 1^m=(ab)^m? Similarly if the order of b is n, what is 1^n=(ab)^n? Thus...? (remember the order is characterized by minimilality.)
 

Similar threads

Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
4
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 1 ·
Replies
1
Views
6K
Replies
15
Views
4K
  • · Replies 1 ·
Replies
1
Views
1K