Number theory, order of an integer

**suedenation** · November 20th 2006, 09:28 PM

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!!!

**ThePerfectHacker** · November 21st 2006, 05:53 AM

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.

Thread: Number theory, order of an integer

LinkBack

Thread Tools

Display

Number theory, order of an integer

Similar Math Help Forum Discussions

Textbooks on Galois Theory and Algebraic Number Theory

Groups of order p^{e}m contains subgroups of order p^r for every integer r<=e.

Order of Integer Questions

Number theory integer proofs

order of an integer

Search Tags