How Do You Determine the Maximum Order of an Element Modulo n?

[Ferzurio]

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
x^t = 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'.

 

[DonAntonio]

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
x^t = 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 \left(\mathbb Z/nZ\right)^* .

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

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

with p=11\,,\,q=7 we already have a group with 3 different prime divisors, and with p=31\,,\,q=91 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 \frac{pq-1}{2} , but for this I can't

see what else can be said...

DonAntonio

 

[Petek]

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 x^t \equiv 1 \pmod{pq} with t being the least positive integer that satisfies the congruence. Can you find a relationship between those solutions and solutions to x^t \equiv 1 \pmod{p} and x^t \equiv 1 \pmod{q}?

 

[Ferzurio]

I have only a small compendium with no more than 120 pages (10 different chapters) that covers an entire semester.

I see that for x^t≡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...

 

[DonAntonio]

The maximum order modulo n is \Phi(n), where \Phi 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

 

[20Tauri]

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.

 

[Petek]

@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 g_1 be a primitive root mod p and let g_2 be a primitive root mod q.

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

x \equiv g_1 \pmod{p}
x \equiv g_2 \pmod{q}

x can be regarded as an element of (\mathbb{Z}/pq\mathbb{Z})^* (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 (\mathbb{Z}/pq\mathbb{Z})^* 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.

 

[DonAntonio]

@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 g_1 be a primitive root mod p and let g_2 be a primitive root mod q.

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

x \equiv g_1 \pmod{p}
x \equiv g_2 \pmod{q}

x can be regarded as an element of (\mathbb{Z}/pq\mathbb{Z})^* (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 (\mathbb{Z}/pq\mathbb{Z})^* 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 \left(\mathbb Z/pq\mathbb Z\right)^* , 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 \left(\mathbb Z/pq\mathbb Z\right)^*\cong U_p \times U_q where U_r is the cyclic group of units modulo r, from where it follows that if x,y are generators of U_p\,,\,U_q corr., then

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

DonAntonio

Ps OTOH, it may be that the OP meant exactly what you answered...I can't say for sure.

 

[Petek]

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.

 

[Ferzurio]

1. Let g_1 be a primitive root mod p and let g_2 be a primitive root mod q.

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

x \equiv g_1 \pmod{p}
x \equiv g_2 \pmod{q}

x can be regarded as an element of (\mathbb{Z}/pq\mathbb{Z})^* (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 (\mathbb{Z}/pq\mathbb{Z})^* 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 = g₁M₁y₁ + g₂M₂y₂ mod pq
where
M₁ = (pq)/p = q
M₂ = (pq)/q = p
y₁ = (M₁)^-1 = q^-1 mod p
y₂ = (M₂)^-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)

 

[Petek]

You're making progress, but still have some work to do. I'll sketch the necessary steps below.

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

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

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

3. If y is any element of (\mathbb{Z}/pq\mathbb{Z})^*, then y^t \equiv 1 \pmod{pq} (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 g_1, g_2 or x.

HTH