Abstract Algebra Abstract Algebra Math Forum

 June 13th, 2014, 06: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, 11: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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post WWRtelescoping Complex Analysis 6 February 23rd, 2014 10:54 AM Jhenrique Complex Analysis 2 November 12th, 2013 05:18 PM ScottGonzales Algebra 0 November 26th, 2012 10:40 AM mia6 Advanced Statistics 1 October 26th, 2008 09:01 PM dh273 Economics 2 July 1st, 2008 05:13 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      