Maximum order of an element

In summary, the maximum order of an element modulo n, where n is a product of two odd, distinct primes, can be found by using the Chinese Remainder Theorem and finding an element with a primitive root modulo each prime, then taking the LCM of their orders.
  • #1
Ferzurio
3
0
What is the maximum order of an element modulo n, where n is a product of two odd, distinct primes?
Let t be the smallest positive integer such that
xt = 1 mod n

I've have been searching around on the web, but I don't really understand this concept.
Some of the keyword I have found to be useful to show/use are
'Fermat's Theorem', 'Eulers Phi Function', 'LCM', 'Chinese Remainder Theorem'.
 
Physics news on Phys.org
  • #2
Ferzurio said:
What is the maximum order of an element modulo n, where n is a product of two odd, distinct primes?
Let t be the smallest positive integer such that
xt = 1 mod n

I've have been searching around on the web, but I don't really understand this concept.
Some of the keyword I have found to be useful to show/use are
'Fermat's Theorem', 'Eulers Phi Function', 'LCM', 'Chinese Remainder Theorem'.



First ,you meant "x, an element of [itex]\left(\mathbb Z/nZ\right)^*[/itex] .

Second, I don't think there's a general answer to this question, since for example:

Take [itex]p=3\,,\,q=5\Longrightarrow pq-1=14=\left|\left(\mathbb Z/nZ\right)^*\right|[/itex] and we have here an abelian group of order 14, but

with [itex]p=11\,,\,q=7[/itex] we already have a group with 3 different prime divisors, and with [itex]p=31\,,\,q=91[/itex] we have 4 prime divisors, etc.

Now, we know that in this case the units group is NEVER cyclic, so the maximal order an element of that group is [itex]\frac{pq-1}{2}[/itex] , but for this I can't

see what else can be said...

DonAntonio
 
  • #3
Hi Ferzurio,

I'm going to respectfully disagree with DonAntonio. Your problem has a definite answer. I have a question for you. You said that you found some terms that might apply to your question on the Internet. Don't you have a textbook? If so, look in the book for those terms. Another one that might be useful is primitive root. Also, I'm going to assume that you are not using group theory to solve this problem. That's fine; all you need to know is elementary number theory.

To get you started, try solving the problem for small values of p and q. For example, let p = 3 and q = 5. Then try p = 3 and q = 7. Finally, let p = 5 and q = 7. In each case find an x and a t such that [itex]x^t \equiv 1 \pmod{pq}[/itex] with t being the least positive integer that satisfies the congruence. Can you find a relationship between those solutions and solutions to [itex]x^t \equiv 1 \pmod{p}[/itex] and [itex]x^t \equiv 1 \pmod{q}[/itex]?
 
  • #4
I have only a small compendium with no more than 120 pages (10 different chapters) that covers an entire semester.

I see that for xt≡1 mod p, for p = 3, 5, 7, it follows a repetitive order whereas mod 15, 21, 35 does not.

For p = 3, q = 5, n=15, I see for the same value of x, the order with n is either an order with p or with q

For p = 3, q = 7, n=35, I see almost the same, except for example x=2, the order of 3 is 2, order for 7 is 3, but the order of n is 6 which is these two order from p and q multiplied together.

For p = 3, q = 5, n=15 I can't see that pattern anymore...
 
  • #5
20Tauri said:
The maximum order modulo n is [itex]\Phi[/itex](n), where [itex]\Phi[/itex] is Euler's Totient Function aka the Euler phi-function. In the case where n is the product of two distinct primes p and q, this will be equal to (p-1)(q-1).



This cannot be lest the units group is cyclic, and it isn't in this case.

DonAntonio
 
  • #6
DonAntonio said:
This cannot be lest the units group is cyclic, and it isn't in this case.

DonAntonio

Oh, shoot, I think you're right. I pulled out my number theory book and it really only talks about orders mod p where p is prime. I'll delete my prior post.
 
  • #7
@Ferzurio,

It's too bad that you don't have a very detailed text. You might want to look at this page, which contains links to several free (and legal) texts on elementary number theory. You also can refer to Wikipedia for explanations of Chinese Remainder Theorem, Primitive Root and so on.

Here are some hints about how to solve the problem:

1. Let [itex]g_1[/itex] be a primitive root mod p and let [itex]g_2[/itex] be a primitive root mod q.

2. Use the Chinese Remainder Theorem to find an x such that

[tex]x \equiv g_1 \pmod{p}[/tex]
[tex]x \equiv g_2 \pmod{q}[/tex]

x can be regarded as an element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] (the multiplicative group of integers mod pq).

3. Let t = LCM(p-1, q-1). Show that x has order t and that no other element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] has greater order.

That should solve your problem. If you don't understand any of these terms or concepts, try looking them up in the resources that are available to you. Please post again if you still have any questions.
 
  • #8
Petek said:
@Ferzurio,

It's too bad that you don't have a very detailed text. You might want to look at this page, which contains links to several free (and legal) texts on elementary number theory. You also can refer to Wikipedia for explanations of Chinese Remainder Theorem, Primitive Root and so on.

Here are some hints about how to solve the problem:

1. Let [itex]g_1[/itex] be a primitive root mod p and let [itex]g_2[/itex] be a primitive root mod q.

2. Use the Chinese Remainder Theorem to find an x such that

[tex]x \equiv g_1 \pmod{p}[/tex]
[tex]x \equiv g_2 \pmod{q}[/tex]

x can be regarded as an element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] (the multiplicative group of integers mod pq).

3. Let t = LCM(p-1, q-1). Show that x has order t and that no other element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] has greater order.

That should solve your problem. If you don't understand any of these terms or concepts, try looking them up in the resources that are available to you. Please post again if you still have any questions.



I can't understand why you think the above answers the OP's question, which asks , if I understood correctly, what's the maximal order

of a general element in [itex]\left(\mathbb Z/pq\mathbb Z\right)^*[/itex] , and what you're doing is to produce an element there of maximal order...

If the OP wanted to know what you're proposing, I think it'd be easier to point out that [tex]\left(\mathbb Z/pq\mathbb Z\right)^*\cong U_p \times U_q[/tex] where [itex]U_r[/itex] is the cyclic group of units modulo r, from where it follows that if [itex]x,y[/itex] are generators of [itex]U_p\,,\,U_q[/itex] corr., then

the element [itex](x,y)\in U_p\times U_q[/itex] has order [itex]lcm(p-1,q-1) =[/itex] exponent of the group...

DonAntonio

Ps OTOH, it may be that the OP meant exactly what you answered...I can't say for sure.
 
  • #9
Well, that was my interpretation of the OP. I agree that's it's easier to use arguments from group theory. However, I assumed this problem was for a class in elementary number theory and argued accordingly.
 
  • #10
Petek said:
1. Let [itex]g_1[/itex] be a primitive root mod p and let [itex]g_2[/itex] be a primitive root mod q.

2. Use the Chinese Remainder Theorem to find an x such that

[tex]x \equiv g_1 \pmod{p}[/tex]
[tex]x \equiv g_2 \pmod{q}[/tex]

x can be regarded as an element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] (the multiplicative group of integers mod pq).

3. Let t = LCM(p-1, q-1). Show that x has order t and that no other element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex] has greater order.

Okay, I have look up some more of these terms but I might still be missing something.

The Chinese Remainder Theorem in step (2) I have
x = g1M1y1 + g2M2y2 mod pq
where
M1 = (pq)/p = q
M2 = (pq)/q = p
y1 = (M1)-1 = q-1 mod p
y2 = (M2)-1 = p-1 mod q


In (3)
t = LCM(p-1,q-1) = ((p-1)(q-1))/gcd(p-1,q-1) = phi(n)/gcd(p-1,q-1)
 
  • #11
You're making progress, but still have some work to do. I'll sketch the necessary steps below.

Let [itex]g_1[/itex], [itex]g_2[/itex], x and t be as in my last post. Then you need to show that

1. [itex]x^t \equiv 1 \pmod{pq}[/itex] (and so the order of x mod pq is at most t).

2. If 0 < n < t, then [itex]x^n \not\equiv 1 \pmod{pq}[/itex] (which together with (1) implies that the order of x mod pq is exactly t).

3. If y is any element of [itex](\mathbb{Z}/pq\mathbb{Z})^*[/itex], then [itex]y^t \equiv 1 \pmod{pq}[/itex] (and so the order of any integer mod pq is at most t).

All of these statements can be proved using the properties of primitive roots and congruences. You don't need to write down explicit values for [itex]g_1[/itex], [itex]g_2[/itex] or x.

HTH
 

1. What is the maximum order of an element?

The maximum order of an element is the highest number of times the element can be multiplied by itself and still result in the identity element. In other words, it is the largest exponent that can be used for the element in a group.

2. How is the maximum order of an element calculated?

The maximum order of an element is calculated by finding the smallest positive integer n for which the element raised to the power of n results in the identity element. This can be done through trial and error or by using the fundamental theorem of cyclic groups.

3. Can the maximum order of an element be infinite?

No, the maximum order of an element cannot be infinite. It is always a finite number, as it is defined as the largest exponent that results in the identity element. However, the maximum order can be arbitrarily large depending on the group and the element.

4. How does the maximum order of an element relate to the order of a group?

The maximum order of an element is always a factor of the order of the group. In other words, the maximum order of an element must divide the order of the group. This is because the maximum order is limited by the size of the group.

5. Why is the maximum order of an element important in group theory?

The maximum order of an element is important because it helps determine the structure and properties of a group. It can also be used to classify and distinguish between different types of groups. In addition, the maximum order of an element can be used to solve problems and equations within groups.

Similar threads

  • Linear and Abstract Algebra
Replies
11
Views
1K
Replies
2
Views
941
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
3K
  • Linear and Abstract Algebra
Replies
4
Views
3K
Replies
6
Views
3K
Back
Top