Order of an Integer mod m (number theory help)

In summary, the conversation discusses the relationship between congruence and order of integers in modular arithmetic. It is stated that if a^k is congruent to 1 mod m, then ord(m)a is the smallest integer k that satisfies the congruence. It is also suggested that a^(ord(m)a) and b^(ord(m)b) are equivalent to ab and ab, respectively. The conversation ends with a question about the order of a and b when raised to the power of m and n, respectively. It is implied that the order is characterized by minimality.
  • #1
Ch1ronTL34
12
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
  • #2
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.)
 

What is the "order" of an integer mod m?

The order of an integer mod m is the smallest positive integer k such that a^k ≡ 1 (mod m), where a is the integer and m is the modulus.

How is the order of an integer mod m calculated?

The order of an integer mod m can be calculated using the following formula: ordm(a) = lcm(φ(m), k), where lcm is the least common multiple function and φ(m) is the Euler totient function.

What is the significance of the order of an integer mod m?

The order of an integer mod m is significant because it determines the number of distinct solutions to the congruence a^x ≡ b (mod m), where b is any integer coprime to m. It also has applications in cryptography and number theory.

Is the order of an integer mod m always unique?

Yes, the order of an integer mod m is always unique. However, different integers may have the same order mod m.

How can the order of an integer mod m be used to solve problems in number theory?

The order of an integer mod m can be used to simplify and solve problems involving congruences, cyclic groups, and primitive roots. It also has applications in the study of quadratic residues and the structure of finite fields.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
969
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
983
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
115
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top