# Number theory, order of an integer

• Nov 20th 2006, 09:28 PM
suedenation
Number theory, order of an integer
Hi, do you guys know how to do this question? It's one of my assignment questions, pls help.......

Q: Show that if n is a positive integer, and a and b are integers relatively prime to n such that (ordna, ordnb)=1, then ordn(ab)=ordna x ordnb

Thanks alot!!!
• Nov 21st 2006, 05:53 AM
ThePerfectHacker
Quote:

Originally Posted by suedenation
Hi, do you guys know how to do this question? It's one of my assignment questions, pls help.......

Q: Show that if n is a positive integer, and a and b are integers relatively prime to n such that (ordna, ordnb)=1, then ordn(ab)=ordna x ordnb

Thanks alot!!!

Let $\gcd(a,n)=\gcd(b,n)=1$
Then let $k,j$ be the orders of these integers respectively.
That is,
$a^k\equiv 1(\mbox{ mod }n)$
$b^j\equiv 1(\mbox{ mod }n)$
Where, $k,j$ are minimal.

Now, $\gcd(ab,n)=1$ so the order of $ab$ exists. We note that, $(ab)^{kj}\equiv 1 (\mbox{ mod }n)$
Because, $(ab)^{kj}=(a^k)^j\cdot (b^j)^k$
So the order of $ab$ is $d$ and must be a divisor of $kj$. Since $\gcd(k,j)=1$ we must have by Euclid's Lemma that $d|k, d|j$. Thus, the order of $k,j$ is actually smaller, that is, $\frac{k}{d},\frac{j}{d}$ unless $d=1$ which is this case here.