1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory - fields, multiplication table

Tags:
  1. Sep 14, 2016 #1

    Rectifier

    User Avatar
    Gold Member

    The problem
    Consider field ##(F, +, \cdot), \ F = \{ 0,1,2,3 \}##
    With the addition table:

    87RcyQA.png

    Find a multiplication table.

    The attempt
    Please read the most of my answer before writing a reply.

    My solution was
    $$
    \begin{array}{|c|c|c|}
    \hline \cdot & 0 & 1 & 2 & 3 \\\hline
    0 & 0 & 0 & 0 & 0 \\\hline
    1 & 0 & 1 & 2 & 3 \\\hline
    2 & 0 & 2 & 0 & 2 \\\hline
    3 & 0 & 3 & 2 & 1 \\\hline
    \end{array}
    $$

    The solution in the book was
    F4JEOWo.png

    I don't really understand how they get ##2 \cdot 2 = 3## and ##3 \cdot 3 = 2## and ##3 \cdot 2 = 2 \cdot 3 = 1##. I know that multiplication in a field is commutative so a \cdot b = b \cdot a thus ##3 \cdot 2 = 2 \cdot 3 ## but I dont know why it is 1 and not 2.

    Lets take one of these as example:
    ##2 \cdot 2## is 4 right? Then when we calculate the the remainder in respect to 4 ( as it is 4 elements in the field and a field is by definition a commutative ring, right? and we want the answer to be another element in the ring) so it becomes 0. That is ##R_4(4) = 0##. For ##3 \cdot 3 = 9## which produces the remainder ##R_4(9)=1##.



    Could someone please help me with what I am doing wrong and how I should solve it instead? Please be specific. Tell me how I should tackle this problem.I am not asking for a solution but for the procedure for these kinds of problems.
     
  2. jcsd
  3. Sep 14, 2016 #2

    jedishrfu

    Staff: Mentor

    To solve these kinds of problem you must remember that multiplication is in fact multiple additions and so 3 x 3 means 3 + 3 + 3 and you must use the addition table to determine that 3 + 3 is 0
    and hence 3 + 3 + 3 = (3 + 3) + 3 = 0 + 3 = 3
     
  4. Sep 14, 2016 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The fact that multiplication is repeated addition holds for ordinary numbers with the usual definitions. It may not---or at least, need not---hold for the field(s) in this question. I think that in this question there are several different possible multiplication tables, so there are really several different possible fields. (Note that the question asked for a multiplication table.)
     
  5. Sep 14, 2016 #4

    jedishrfu

    Staff: Mentor

    Good point!

    The book answer looks like a shift operator.
     
  6. Sep 14, 2016 #5

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    There is only one solution. (As it is homework, I'll write only hints.)
    • For all elements is ##-x=\,##?
    • ##(3 \cdot 3 - 1 \cdot 1) = (3+1) \cdot (3-1)## gives one condition
    • ##3 \cdot 2 = (2+1) \cdot 2## gives another condition
    Now for ##3 \cdot 3 \in \{0,1,2,3\}## all but one can be ruled out by the fact that it has to be a field.
     
    Last edited: Sep 14, 2016
  7. Sep 14, 2016 #6
    This question does not look right. The use of 2 & 3 is the problem, mostly syntax, but does obscure semantics.The finite field of order 4 is a second degree extension of the finite field of order 2; so will work modulo 2. Means the addition table is incorrect as well, from mod 2 perspective. There must be a new element introduced that is the zero of x^2 + x + 1 = 0, over F2 = {0,1}. The addition table given is confusing in that it uses 2 & 3 when it should not, because you can see neither mod 2 nor mod 4 work with these symbols to give the addition table shown; they behave as the zeros of the polynomial x^2 + x + 1 = 0; usually given symbol as lower case alpha or something other than 2 or any other numeric symbol. I am thinking that maybe it was intended as a simplification, but just makes things worse. I could elaborate more, but do not want to answer question, being an assignment.
     
  8. Sep 14, 2016 #7

    jedishrfu

    Staff: Mentor

    Where did you get the specifics of the problem? I didn't see these in the OP's post.

    Don't answer if you feel it will give away the solution though.
     
  9. Sep 14, 2016 #8
    Sorry, is it a assignment question or a personal exploration problem?
     
  10. Sep 14, 2016 #9

    jedishrfu

    Staff: Mentor

    An assignment from the looks of it, you should look at all PF posts as possible assignments unless others have posted comments and it then appears not to be or the cat is out of the bag.
     
  11. Sep 14, 2016 #10

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I don't understand your question. I thought the specifics are: Given a field and an addition table, what is the multiplication table?
    So I just proposed to apply the distribution law without substituting the products by elements, just by writing them ##2\cdot 2 ,2\cdot 3## and ##3 \cdot 3## and using the addition table where possible (and of course ##1 \cdot 1 = 1##).
     
  12. Sep 14, 2016 #11

    jedishrfu

    Staff: Mentor

    I didn't mean to imply anything it just seemed that you had listed specifics that I didn't see and figured I missed something. I guess I've forgotten that given a field implies a lot.
     
  13. Sep 14, 2016 #12

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    No, it was as simple as: Given three unknowns, ##2 \cdot 2,2 \cdot 3, 3 \cdot 3##, which equations are among them, That led me to the distribution law.
     
  14. Sep 14, 2016 #13

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    First question to ask (and answer):
    What is the definition of a field?

    Notice that in your proposed definition of multiplication, 2 has no (multiplicative) inverse.
     
  15. Sep 14, 2016 #14
    The problem is bad notation on the books part; should never use numeric symbols e.g. 2 & 3. Because the solution is adding a new element that solves the polynomial x^2 + x +1 = 0; which 2 & 3 do not, looking mod 2 or 4. The book is using '2' & '3' not as usual 2 & 3. With there notation, '2' solves x^2 + x + 1 = 0 mod2, which looks really weird; and why I'm saying the book is bad. Remember the finite field of order 4 is a 2nd degree extension of the field of order 2; you have the adjoin a zero of that polynomial; similar to extending real numbers to complex by adding i = (-1)^(.5). So, this book is using '2' & '3' as the new adjoined elements. This horrible notation from the book has led those down the wrong path; it's like trying to extend reals to complex by adjoining other real numbers, instead of some completely new "number". I hope this is getting through, I can reiterate if needed.
     
  16. Sep 14, 2016 #15

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    This is not my opinion.

    The way it is presented is, that there exists a field with four elements. It is automatically clear that the role of these elements cannot be the same as within the integers. Furthermore it is far better than naming four elements ##a,b,c,d## which is too abstract to keep in mind. Whereas the notation by numbers trains people to exactly define what is meant as needed everywhere in mathematics. We also often denote elements in ##\mathbb{Z}_5## and similar by numbers. I don't see any reason why it should be handled differently here.

    There is everything alright with the book.
     
  17. Sep 14, 2016 #16

    Rectifier

    User Avatar
    Gold Member

    Thank you for all of your comments! I really appreciate the hints I have received,

    First of all, it is a problem from a book (not an assignment that I should hand in, I am doing it just to get hang of the theory in the book as for all problems I have ever posted on PF but that does not really matter since there is almost no way to tell if a user posts an assignment disguised as a problem from a book so we should follow the guidelines :D ).


    So, what I get from the comments is that I should somehow use the addition table to solve the problem (a question for later: what if we didn't have that addition table to start with?)

    it is ##x## as it is an additive inverse and so are ##1,2,3##. I don't get your other hints though.

    As@SammyS mentioned in #13, 2 didn't have an multiplicative inverse in my multiplication table which is wrong by definition (since there always exists an inverse in a field) so we know that my table is wrong without looking at the key table.
     
    Last edited: Sep 14, 2016
  18. Sep 14, 2016 #17

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Yes, by ##-x## I meant the number that solves ##x + (-x) = 0## And yes, ##x=-x## as you said (and deleted). I only mentioned it, because it makes your calculations easier. It means that you won't have to distinguish between addition and subtraction: ##x+y = x -y##. This way you won't have to calculate every "##-##" on its own but you may look up the addition in the table instead, e.g. ##2-1=2+1=3## or ##3-1=3+1=2##.
     
  19. Sep 14, 2016 #18

    Rectifier

    User Avatar
    Gold Member

    I know that by definition that additive inverse to 1 is its negative self right? I end up with ##1-1=0## which is by definition written as ##1 + (-1) = 0## and according to addition table (you take one term and add it to one another) I end up with two different versions of these additive inverses:
    ##1 + (-1) = 0## or ##1 -1 = 0## for definition and
    ##1 + 1 = 0## for the addition table :,(
     
  20. Sep 14, 2016 #19

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    ##1-1=0## is simply a short version of ##1 + (-1)=0##. It means the same. And the addition table shows you ##x+x=0## for any number.
    This is the same as saying ##x=-x##.
    Important here are two things:

    1) Do not take any addition for granted. Look them up instead. Exception: ##x-x= 0## and ##x+0=x## by definition of ##0##.
    2) Do not take the numbers ##2 \cdot 2 \,,\, 2 \cdot 3 \,,\, 3 \cdot 3## as if you knew the result. Here ##1## is the exception, because ##x\cdot 1 = x## by definition.

    With that and the equations I gave you, ##3 \cdot 3 - 1 \cdot 1 = 3 \cdot 3 - 1 = (3+1) \cdot (3-1) ## and ##3 \cdot 2 = (2+1)\cdot 2 = 2 \cdot 2 + 2 \cdot 1##
    you can consecutively deal with the cases ##3 \cdot 3 = 0## , ##3 \cdot 3 = 1## , etc. and see which one will lead to impossible solutions and which doesn't. Btw. I did not take 3=2+1 as naturally given, I looked it up!
     
  21. Sep 14, 2016 #20

    Rectifier

    User Avatar
    Gold Member

    Thank you so much for your help so far!

    So in an addition table there is no addition but only subtraction?
    1 - 3 = 1 - 3 + 4 (as it is mod 4) = 1 + 1 = 2
    1 - 1 = 0 and so on

    EDIT:
    It does not seem to work for 2 - 3 = 2 - 3 + 4 = 3 but the table gives 1.


    How do you get that equation? Are you deriving it from the fact that ##3 \cdot 3 = 1## \cdot 1## and thus ##3 \cdot 3 - 1 \cdot 1 =0## ?

    EDIT 2:
    I think that my head has had enough of math for today. I will sleep on this information and hopefully I will understand it tomorrow.
     
    Last edited: Sep 14, 2016
  22. Sep 14, 2016 #21

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    There is of course addition. That's how it's made and meant. And of course you can read subtractions out of it, too.
    Row 2 (number ##1##) and column 3 (number ##2##) gives you ##3## in the table, which means ##1+2=3##
    If you read it inside out, you get a subtraction: Search ##3## in the row that is label with ##2##, i.e. the third row, and look up the label of the column, here the second column (where we have found the ##3##), that is labeled by ##1##. Then you have performed ##3-2=1##.
    So the table gives you both, depending how you read it.
    My remark that for all ##x## hold ##x=-x## means essentially that all minus signs can be treated as plus signs in this special case here.
    Please immediately forget ##\mod 4## here. It has nothing to do with ##\mod 4## or ##\mathbb{Z}_4##. Nothing.
    I even would have added the additional exercise to show, that this field is different from ##\mathbb{Z}_4##. The latter cannot be a field!
    Do you know why? If you answer this question, then this will help you a lot to rule out the false possibilities for ##3 \cdot 3##.
    (Hint: ##3 \cdot 3 = 0## cannot be. Why?)

    So all you have is the elements, the addition between them and the laws that a field has to obey:
    associativity, distributivity, etc.
     
    Last edited: Sep 14, 2016
  23. Sep 14, 2016 #22

    rcgldr

    User Avatar
    Homework Helper

    Why is this called a field? Since the only defined operations are addition and multiplication (no subtraction, no division), shouldn't this be called a ring?
     
    Last edited: Sep 14, 2016
  24. Sep 14, 2016 #23

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    It satisfies the axioms for a field.
     
  25. Sep 14, 2016 #24

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    If you insist on the ring structure, what are its maximal ideals?
     
  26. Sep 14, 2016 #25

    rcgldr

    User Avatar
    Homework Helper

    With only addition defined, it wasn't clear that the ring would also be a field until I understood the math behind the addition and multiplication tables.

    The addition table is based on binary exclusive or. For example 3 + 2 = 11 + 10 = 01 = 1.

    The multiplication is binary multiplication using xor instead of add, modulo 7 (binary coefficient polynomial x^2 + x + 1).
    2*2 mod 7 = 10*10 mod 111 = (000 + 100) mod 111 = 100 mod 111 = 011 = 3
    3*3 mod 7 = 11*11 mod 111 = (011 + 110) mod 111 = 101 mod 111 = 010 = 2

    This would be a finite field. Subtraction is also xor, so effectively the same as addition. The division table can be generated from the multiplication table. Every non-zero number is a power of 2, 2^0 = 1, 2^1 = 2, 2^2 = 3, so 2 (x + 0) would be a primitive (alpha) for the field. This also works with 3, 3^0 = 1, 3^1 = 3, 3^2 = 2, so 3 (x + 1) would also be a primitive (alpha).

    I'm wondering if the students in this class were supposed to be aware of the exclusive or operator.
     
    Last edited: Sep 15, 2016
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted