My Math Forum (http://mymathforum.com/math-forums.php)
-   Abstract Algebra (http://mymathforum.com/abstract-algebra/)
-   -   Relationship between ord(a) and ord(a^k) (http://mymathforum.com/abstract-algebra/44593-relationship-between-ord-ord-k.html)

 Awesomo June 13th, 2014 05:52 PM

Relationship between ord(a) and ord(a^k)

I'm working on this question...

Prove that if a^m has order n, then m and n are relatively prime. [Hint: Assume m and n have a common factor q>1, so we can write m=m'q and n=n'q. Explain why (a^m)^n'=e then go from there.

To start things off, I'm not sure if I believe this to be true. Suppose (aa)^4=e and that ord(aa)=4. Well, then 4 and 2 are not relatively prime. Unless I'm making some error, which usually happens since I started this book, this looks wrong.

Regardless, I can see that if (a^m)^n' is equal to e, then n divides n', but n=n'q, so q can't be greater than 1.

But how to show this... idk. Something about primes and generally anything number theory that stumps me.

 Deveno June 13th, 2014 10:49 PM

You're leaving an important part of the question out. Since I've seen this before I think I can guess what it is. This is what you SHOULD be saying:

IF $a$ has order $n$ AND $a^m$ has order $n$, THEN $\text{gcd}(m,n) = 1$.

Before we prove this, let's look at a simple example:

Consider $G = \langle a\rangle = \{e,a,a^2,a^3,a^4,a^5\}$, where $a$ the generator of $G$ has order 6. Since we know $e$ has order 1 (duh!), let's find the orders of the other 4 elements.

$(a^2)^2 = a^4 \neq e$, so $a^2$ doesn't have order 2.
$(a^2)^3 = a^6 = e$, so $a^2$ has order 3.

$(a^3)^2 = a^6 = e$, so $a^3$ has order 2.

$(a^4)^2 = a^8 = (a^6)(a^2) = e(a^2) = a^2 \neq e$, so $a^4$ doesn't have order 2.
$(a^4)^3 = a^{12} = (a^6)^2 = e^2 = e$, so $a^4$ has order 3.

$(a^5)^2 = a^{10} = (a^6)(a^4) = e(a^4) = a^4 \neq e$, so $a^5$ doesn't have order 2.
$(a^5)^3 = a^{15} = (a^12)(a^3) = (a^6)^2(a^3) = (e^2)(a^3) = e(a^3) = a^3 \neq e$, so $a^5$ doesn't have order 3.

We could stop here, the order of $a^5$ has to divide the order of $G$, so 6 is the only possible order left, but we'll continue, for completeness' sake.

$(a^5)^4 = a^{20} = (a^{18})(a^2) = (a^6)^3(a^2) = (e^3)(a^2) = e(a^2) = a^2 \neq e$, so $a^5$ doesn't have order 4.
$(a^5)^5 = a^{25} = (a^24)(a) = (a^6)^4(a) = (e^4)(a) = ea = a \neq e$, so $a^5$ does not have order 5.

Finally, $(a^5)^6 = a^{30} = (a^6)^5 = e^5 = e$, so $a^5$ has order 6.

So let's look at the numbers between 0 and 5 (inclusive).

gcd(0,6) = 6, and $a^0 = e$ does not have order 6 (it has order 1).
gcd(1,6) = 1, and $a^1 = a$ DOES have order 6.
gcd(2,6) = 2, and $a^2$ does not have order 6 (it has order 3).
gcd(3,6) = 3, and $a^3$ does not have order 6 (it has order 2).
gcd(4,6) = 2, and $a^4$ does not have order 6 (it has order 3).
gcd(5,6) = 1, and $a^5$ DOES have order 6.

So the theorem is true for $n = 6$, at the very least.

So, let's suppose that $\text{gcd}(m,n) = d > 1$, and see what we can do with this (Yes, we're proving the "contrapositive", here. It happens).

We have: $m = dt$ for some (positive) integer $t$, and we have $n = du$ for some (positive) integer $u$. Clearly, $u < n$ since $d > 1$ (this is important!).

Now what we want to show is that in this case, the order of $a^m$ is LESS than $n$. What number should we try? How about $u$?

Ok, $(a^m)^u = a^{mu} = a^{(dt)u} = a^{(du)t} = a^{nt} = (a^n)^t$.

Since the order of $a$ is $n$, we know $a^n = e$.

Thus $(a^m)^u = (a^n)^t = e^t = e$.

Now, this doesn't prove that $u$ is the order of $a^m$, but it does prove that the order of $a^m$ is at MOST $u$, and since $u < n$, the order of $a^m$ is LESS than $n$ (and thus it surely ISN'T $n$).

************************

Note we didn't use anything about "primes", just what it means for two numbers to have a common divisor. We didn't even find out what that common divisor even was, which sure saves on a lot of computation time!

 All times are GMT -8. The time now is 08:14 AM.