# Order modulo proof help

• April 19th 2009, 07:00 PM
FrankTheTank
Order modulo proof help
If xy ≡ 1 (modulo n) st x, y, n are natural numbers, then x, y have the same order modulo n.

I tried direct proof and contradiction, but was stuck both ways.

I really need help on dis, thank u.
-Frank
• April 21st 2009, 02:06 AM
clic-clac
Hi

Quote:

If xy ≡ 1 (modulo n) st x, y, n are natural numbers, then x, y have the same order modulo n.
The second "n" is different form the first one, isn't it?

$xy\equiv 1 (\text{mod}n)\Rightarrow x,y \in (\mathbb{Z}_n^*,\times)$

Let $k$ be the order of $x,$ i.e. $x^k=1 (\text{mod}n)$ and for any $0

What about $(xy)^k$ ? Let $l$ be a positive divisor of $k,$ what can you say about $(xy)^l\ \text{if}\ y^l=1$ ? Conclusion?