My Math Forum Relationship between ord(a) and ord(a^k)
 User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

 June 13th, 2014, 05:52 PM #1 Member   Joined: May 2014 From: None of your business Posts: 31 Thanks: 0 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. Please help.
 June 13th, 2014, 10:49 PM #2 Senior Member   Joined: Mar 2012 Posts: 294 Thanks: 88 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! Thanks from Awesomo

 Tags orda, ordak, relationship

### the relationship between two numbers

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post WWRtelescoping Complex Analysis 6 February 23rd, 2014 09:54 AM Jhenrique Complex Analysis 2 November 12th, 2013 04:18 PM ScottGonzales Algebra 0 November 26th, 2012 09:40 AM mia6 Advanced Statistics 1 October 26th, 2008 08:01 PM dh273 Economics 2 July 1st, 2008 04:13 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top