- #1

- 362

- 0

## Homework Statement

Let gcd(h,k)=1, o(a)=h, o(b)=k, show that o(ab)=hk

## Homework Equations

o(a)= order of a modulo n

o(a)=k iff k is smallest integer,[itex] a^k=1 mod n[/itex]

## The Attempt at a Solution

to prove o(ab) l hk, no problem, just need to show [itex](ab)^{hk}=1 mod n[/itex]

and to prove hk l o(ab), use division algorithm

let, hk=p*o(ab)+q , [itex]0\leq q<p[/itex]

it can be shown that [itex](ab)^q=1 mod n[/itex], this will imply q=0, so o(ab) l hk

and i really think i didn't make any mistake, but i didn't use that gcd(h,k)=1.

can help me anywhere i wrong? or is this gcd(h,k)=1 is unnecessary?

Last edited: