# Maximum order of an element

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'.

Related Linear and Abstract Algebra News on Phys.org
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 $\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
Gold Member
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}$?

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...

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

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
Gold Member
@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.

@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
Gold Member
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.

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 = 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)

Petek
Gold Member
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