# Maximum order of an element

1. Apr 26, 2012

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

2. Apr 26, 2012

### DonAntonio

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

3. Apr 27, 2012

### 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}$?

4. Apr 27, 2012

### 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 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. Apr 27, 2012

### DonAntonio

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

DonAntonio

6. Apr 27, 2012

### 20Tauri

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. Apr 28, 2012

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

8. Apr 28, 2012

### DonAntonio

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.

9. Apr 28, 2012

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

10. Apr 28, 2012

### Ferzurio

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. Apr 29, 2012

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