| (7 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| + | =[[HW3_MA453Fall2008walther|HW3]], Chapter 3, Problem 9, [[MA453]], Fall 2008, [[user:walther|Prof. Walther]]= | ||
| + | ==Problem Statement== | ||
| + | Show that U(20) does not equal <k> for any k in U(20). [Hence U(20) is not cyclic.] | ||
| + | |||
| + | ---- | ||
| + | ==Discussion== | ||
| + | |||
The problem says show that U(20) does not equal <k> for any k in U(20). [Hence U(20) is not cyclic.] | The problem says show that U(20) does not equal <k> for any k in U(20). [Hence U(20) is not cyclic.] | ||
I was trying to understand Example 1 from the Chapter 3 in the text book. where it discusses U(15). | I was trying to understand Example 1 from the Chapter 3 in the text book. where it discusses U(15). | ||
| Line 6: | Line 13: | ||
Then it goes on to say to find the order of element 7, so |7| = 4 | Then it goes on to say to find the order of element 7, so |7| = 4 | ||
<math>7^1 = 7space 7^2 =4 space 7^3 = 13 space 7^4 = 1</math> | <math>7^1 = 7space 7^2 =4 space 7^3 = 13 space 7^4 = 1</math> | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Let U(a) = X where X is a group with several elements. Let Z = b + n*a, so all elements in X will satisfy gcd(a,b) = 1. | ||
| + | |||
| + | So for U(15) we'll get {1, 2, 4, 7, 8, 11, 13, 14} | ||
| + | |||
| + | To find an order of an element, y in X, we just have to find a power of the modulo where it will repeat itself. So | ||
| + | |||
| + | <math> 7^0 = 1 </math>, the remainder when 15|1 = 1 | ||
| + | |||
| + | <math>7^1 = 7 </math>, remainder = 7 | ||
| + | |||
| + | <math>7^2 = 49 </math>, remainder of 15|49 = 4 | ||
| + | |||
| + | <math>7^3 = 343 </math>, remainder of 15|343 = 13 | ||
| + | |||
| + | <math>7^4 = 2401 </math>, remainder of 15|2401 = 1 | ||
| + | |||
| + | The remainder of <math> 7^4 </math> is the same as <math> 7^0 </math>, and so we can end here since it the remainders will repeat itself | ||
| + | So, the order of |7| = 4 since it has to go through 4 numbers before it repeats itself again. | ||
| + | |||
| + | To make the calculation easier, we can see that | ||
| + | <math> 7^2 = 49 = (15*n + 4) </math> | ||
| + | <math> 7^3 = (15*n + 4) * 7 </math> | ||
| + | We know that <math> (15*n)*7 </math> is going to be divisible by 15, so we just have to find out what the remainder of <math> 15|4*7 </math>. | ||
| + | ---- | ||
| + | I just think it's funny that the back of the book tells us to "brute force" to solve this problem. I don't think I've ever used brute force in mathematics before. ;) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | I don't get why U(20) does not equal <k> for any k in U(20). Doesn't U(20) = <1> <3> <7> <9> <11> <13> <17> <19> | ||
| + | |||
| + | ---- | ||
| + | check the orders | ||
| + | ---- | ||
| + | Isn't this just the example from class? | ||
| + | ---- | ||
| + | [[HW3_MA453Fall2008walther|Back to HW3]] | ||
| + | |||
| + | [[Main_Page_MA453Fall2008walther|Back to MA453 Fall 2008 Prof. Walther]] | ||
Latest revision as of 16:04, 22 October 2010
HW3, Chapter 3, Problem 9, MA453, Fall 2008, Prof. Walther
Problem Statement
Show that U(20) does not equal <k> for any k in U(20). [Hence U(20) is not cyclic.]
Discussion
The problem says show that U(20) does not equal <k> for any k in U(20). [Hence U(20) is not cyclic.] I was trying to understand Example 1 from the Chapter 3 in the text book. where it discusses U(15). I am completely confused about what it is talking about:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14 } Then it goes on to say to find the order of element 7, so |7| = 4 $ 7^1 = 7space 7^2 =4 space 7^3 = 13 space 7^4 = 1 $
Let U(a) = X where X is a group with several elements. Let Z = b + n*a, so all elements in X will satisfy gcd(a,b) = 1.
So for U(15) we'll get {1, 2, 4, 7, 8, 11, 13, 14}
To find an order of an element, y in X, we just have to find a power of the modulo where it will repeat itself. So
$ 7^0 = 1 $, the remainder when 15|1 = 1
$ 7^1 = 7 $, remainder = 7
$ 7^2 = 49 $, remainder of 15|49 = 4
$ 7^3 = 343 $, remainder of 15|343 = 13
$ 7^4 = 2401 $, remainder of 15|2401 = 1
The remainder of $ 7^4 $ is the same as $ 7^0 $, and so we can end here since it the remainders will repeat itself So, the order of |7| = 4 since it has to go through 4 numbers before it repeats itself again.
To make the calculation easier, we can see that $ 7^2 = 49 = (15*n + 4) $ $ 7^3 = (15*n + 4) * 7 $ We know that $ (15*n)*7 $ is going to be divisible by 15, so we just have to find out what the remainder of $ 15|4*7 $.
I just think it's funny that the back of the book tells us to "brute force" to solve this problem. I don't think I've ever used brute force in mathematics before. ;)
I don't get why U(20) does not equal <k> for any k in U(20). Doesn't U(20) = <1> <3> <7> <9> <11> <13> <17> <19>
check the orders
Isn't this just the example from class?
