Multiplicative order of a number

  • Thread starter koolkuzz
  • Start date
In summary, the multiplicative order of a number is the smallest positive integer <i>k</i> such that <i>a<sup>k</sup> ≡ 1 (mod n)</i>, where <i>a</i> is the number and <i>n</i> is the modulus. It can be calculated using the Euler's totient function and has significance in number theory and cryptography. It is closely related to group theory and is always less than or equal to the modulus.
  • #1
koolkuzz
5
0
I'm stuck on a question that requires me to prove the following:

Let s,n ∈ N, a ∈ Z and (a,n) = 1. (Note: a & n are coprime)
Prove that ordnas = ordna implies that (s, ordn a) = 1.

I have tried using Proof by contradiction, but seem to go nowhere with this.

Can you help?
 
Physics news on Phys.org
  • #2
Suppose [tex](s, \mathop{\mathrm{ord}_n} a) = d[/tex] and put [tex]s = de[/tex]. Observe that [tex]a^s = (a^d)^e[/tex]. What is [tex]\mathop{\mathrm{ord}_n} a^d[/tex]?
 
Last edited:

What is the multiplicative order of a number?

The multiplicative order of a number is the smallest positive integer k such that ak ≡ 1 (mod n), where a is the number and n is the modulus. In simpler terms, it is the smallest power of a number that results in a remainder of 1 when divided by the modulus.

How is the multiplicative order of a number calculated?

The multiplicative order of a number can be calculated using the Euler's totient function, which is the number of positive integers less than the given modulus that are relatively prime to it. The multiplicative order is then equal to the smallest positive integer k such that ak ≡ 1 (mod φ(n)), where φ(n) is the Euler's totient function value of the modulus n.

What is the significance of the multiplicative order of a number?

The multiplicative order of a number is significant in number theory and cryptography. It is used in various algorithms for generating pseudorandom numbers, primality testing, and encryption schemes. It also has applications in solving certain mathematical problems, such as finding primitive roots and discrete logarithms.

How does the multiplicative order of a number relate to the group theory?

The concept of multiplicative order is closely related to the group theory, particularly the subgroup theory. The multiplicative order of a number a modulo n is equal to the order of the subgroup generated by a in the group of units modulo n. This connection is useful in understanding the properties and applications of the multiplicative order.

Can the multiplicative order of a number be larger than the modulus?

No, the multiplicative order of a number is always less than or equal to the modulus. This is because the remainder of a division cannot be larger than the divisor. In other words, the multiplicative order of a number a modulo n is always in the range [1, φ(n)], where φ(n) is the Euler's totient function value of the modulus n.

Similar threads

Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
2
Views
267
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
511
Prove ##a\cdot b = b \cdot a ##using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
686
Prove ##(a\cdot b)\cdot c =a\cdot (b \cdot c)## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
1
Views
458
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
503
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
574
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
519
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
809
Show that a set has no "unique nearest point" property
    • Calculus and Beyond Homework Help
Replies
14
Views
520
Prove ##(a+b) + c = a + (b+c)## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
9
Views
1K

Hot Threads

Recent Insights

Back
Top