# Thread: Number theory, order of an integer

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

2. 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 $\displaystyle \gcd(a,n)=\gcd(b,n)=1$
Then let $\displaystyle k,j$ be the orders of these integers respectively.
That is,
$\displaystyle a^k\equiv 1(\mbox{ mod }n)$
$\displaystyle b^j\equiv 1(\mbox{ mod }n)$
Where, $\displaystyle k,j$ are minimal.

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

,

,

,

### ordnb

Click on a term to search for related topics.