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

Printable View

- Apr 19th 2009, 06:00 PMFrankTheTankOrder 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 - Apr 21st 2009, 01:06 AMclic-clac
Hi

Quote:

If xy ≡ 1 (modulo n) st x, y, n are natural numbers, then x, y have the same order modulo n.

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

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

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