1

I do not know whether or not the statement is true or false, but here is my approach:

We know that $\exists y \in \mathbb{Z}_n : xy = 1$. By definition, in order for ord(x) to be defined, there must exist an $r$ such that $x^r = 1 \in \mathbb{Z}_n$.

In other words, we are given that:

$xy \equiv 1$ (mod n)

$n | xy-1$

Thus, $\exists k \in \mathbb{Z}$ such that $nk = xy-1$.

I don't know where to go from here, though. Could anyone please help?

will
  • 31
  • From $xy\equiv 1\pmod{n}$ we can conclude that $\gcd(x,n)=1$. It follows that $x^{\varphi(n)}\equiv 1\pmod{n}$, where $\varphi$ is the Euler $\varphi$-function. So there is an $r$ (possibly much smaller than $\varphi(n)$) such that $x^r\equiv 1\pmod{n}$. – André Nicolas Feb 18 '15 at 17:29
  • Is there a way to bypass the part with Euler's $\phi$-function? I don't quite understand how that works, and would be much more comfortable proving the statement without its use. – will Feb 18 '15 at 17:39
  • Certainly. Prove that the product of units (invertible elements) is a unit. Then see the answer by Nate Eldredge. – André Nicolas Feb 18 '15 at 17:42
  • Thank you! That makes lots of sense. :) – will Feb 18 '15 at 17:45

1 Answers1

1

You can use the same argument as in Prove that every element of a finite group has an order.

Since $\mathbb{Z}_n$ is a finite set, the elements $x^1, x^2, x^3, \dots$ cannot all be distinct (pigeonhole principle). Hence there exist $m,n$ with $x^m = x^n$. Let's say $m<n$ and let $k=n-m$. Then we have $x^m = x^{m+k}$. Multiplying both sides by $y^m$, we get $1 = x^k$ as desired.

Community
  • 1
Nate Eldredge
  • 97,710