Turn on thread page Beta

Linear Algebra - Finding hcf and factorizing - University Level - Rep! watch

Announcements
    • Thread Starter
    Offline

    1
    ReputationRep:
    Hey,

    My linear algebra brain doesn't seem to get how to do the following questions (attached) - I don't really get how to divide polynomials et al, and don't understand the method I'd need to use to solve this. Can anyone show, and explain to me the methodology so that I understand for the future?

    Thanks in advance. Everyone who helps me understand/provides a method gets rep from me (in the coming few days/weeks), which is probably worth a fair bit.

    AI

    Attached Images
     
    Offline

    13
    ReputationRep:
    I'll tackle this with a general strategy in a latex friendly manner:

    I trust you know the Euclidean algorithm for finding the hcf. If not then look it up.

    bi) Want to find q and r such that f = qg + r and r=0 or deg(r) < deg(g)
    That's not so hard as f and g have the same degree!

    **** (x^3 + 2x) = (x^3 + 1) + (2x - 1) ****

    The next division of x^3+1 by 2x-1 is harder.

    Firstly get rid of the x^3 by subtracting a suitable multiple of 2x-1 from x^3+1. We'll build the quotient up on the left and the remainder on the right. We have to keep going until the remainder is zero or has degree less than that of 2x-1. That is, until it is constant.

    (x^3+1)-\frac{1}{2}x^2(2x-1) = \frac{1}{2}x^2 + 1

    The remainder on the right still has an x^2 term so take a suitable multiple of 2x-1 off both sides:

    (x^3+1)-(\frac{1}{2}x^2 + \frac{1}{4}x)(2x-1) = (\frac{1}{2}x^2 + 1) - \frac{1}{4}x(2x-1) = \frac{1}{4}x + 1

    Still too big so do the same again.

    (x^3+1)-(\frac{1}{2}x^2 + \frac{1}{4}x + \frac{1}{8})(2x-1) = (\frac{1}{4}x + 1) - \frac{1}{8}(2x-1) = \frac{9}{8}

    So

    **** (x^3+1) = (\frac{1}{2}x^2 + \frac{1}{4}x + \frac{1}{8})(2x-1) + \frac{9}{8} ****

    Next division is of 2x-1 by \frac{9}{8} which will leave remainder zero so the highest common factor is (any associate of) the last non zero remainder. ie, is 1.

    Now use the two starred equations to find polynomials a and b such that af + bg = 1.



    For c i and ii you play exactly the same game but when you want to divide by 2 say, you multiply by the multiplicative inverse of 2 in \mathbb{F}_3. Which is 2.


    For c iii. The only possibilities for factoring a cubic are 3 linear factors, a linear and a quadratic or irreducible. So just shove 0,1,2 into them (remembering to calculate in \mathbb{F}_3). If it's never zero then it's irreducible. Otherwise you find a root and can factorise into a quadratic and (x-a) where a is the root. You can just guess the quadratic. The x^2 coefficient and constant should be obvious and you only have 3 choices for the x coefficient.
    Offline

    15
    ReputationRep:
    b)i) One way to do this is to use algebraic long division and apply the euclidean algorithm. If you need to refresh either of these a quick google or wikipedia should be helpful.

    b)ii) is just a case of reversing the steps you say in i). You've probably done the exact same process for integers.

    c)i) 2 is a root of both the polynomials and hence x-2=x+1 is a factor by the remainder theorem. We need to check this is the hcf though! One way to do this is just by applying polynomial long division in the field of order 3.

    First divide x^3+1 into x^3+2x. We see x^3+2x=(x^3+1)+(2x-1) just as in the case over the rationals.

    Next we divide (2x-1) into (x^3+1). Using the algorithm for algebraic long division 2x would go into x^3 (1/2)x^2 times. This isn't what we want though since (1/2) isn't in the field of order 3. Instead note that (2x)(2x^2)=x^3 since 4=1 in our field. Continuing in this way we see that x^3+1=2x^2(2x-1)+(2x^2+1) and so we only need to find hcf(2x-1,2x^2+1).

    Finally we see 2x^2+1=x(2x-1)+(x+1) and so it remains to find hcf(2x-1,x+1). Clearly 2x-1=2x+2=2(x+1). Thus x+1 is the hcf.

    This process might have been a little hard to follow on screen but refresh long division and hopefully it will become clear, if not post back.

    c)ii) Just reverse the above process, as in b)ii).

    c)iii) Luckily both of these polynomials have roots. Use the remainder theorem to find a factor of degree 1 and divide out this factor using long division. Repeat this process.
    • Thread Starter
    Offline

    1
    ReputationRep:
    Thanks for that help. I'll scan in my method and answers in a bit so that you can see if I've understood all this correctly.
    • Thread Starter
    Offline

    1
    ReputationRep:
    Well, here's what I've done with your help and advice, but I'm still not quite sure of why we've done a couple of things, which I've pointed out in my answers - would anyone care to explain/elaborate? Also, are these solutions correct?

    b)i) + ii)


    c)i) + ii)


    c)iii)
    Attached Images
       
    Offline

    13
    ReputationRep:
    In the ring of polynomials the highest common factor is not unique. If h is a highest common factors then so is kh for any rational number k.

    In general, if R is a ring and h a highest common factor of f and g then the set of highest common factors of f and g is the set of associates of h (the set of hu, u a unit of R).

    In cii) Your second division isn't correct. The remainder has higher degree than the thing you're dividing by.

    In ciii) In your factorisation of g you haven't checked if the quadratic is irreducible.
    • Thread Starter
    Offline

    1
    ReputationRep:
    For c)iii), would the factorisation of g be first written as (x - 2)(x2 + 2x + 1), because when multiplied out -3x is the same as 0 in F3.

    And then that would become (x - 2)(x + 1)2, right?

    As for c)ii), I've been trying for ages to correct the mistake that you say is there, but I don't know quite what to do - would you care to elaborate please?
    Offline

    13
    ReputationRep:
    Apologies. I meant c part i.

    x^3 + 2x = (x^3 + 1) + (2x-1)

    For the next line you want q and r such that:

    (x^3 + 1) = (2x-1)q(x) + r(x)

    With r=0 or the degree of r less than the degree of (2x-1). Which is 1.

    c part iii is now correct. Though you can also write that as (x+1)^3.
    • Thread Starter
    Offline

    1
    ReputationRep:
    Ah, part c)i).

    Well, would I write it as (x3 + 1) = (2x - 1)(2x2 + x + 2) instead? I think that works...

    Does this mean that my answers for the values of a and b in c)ii) are wrong then?
    Offline

    13
    ReputationRep:
    Yeah. And then that shows that the hcf is the last non zero remainder which was 2x-1.

    The first division makes it obvious what a and b are... Very obvious!
    • Thread Starter
    Offline

    1
    ReputationRep:
    Is it really as simple as a = 1 and b = -1 for c)ii) then?

    Edit: You're very patient about all my idiotic mistakes.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: August 28, 2007

University open days

  • Manchester Metropolitan University
    Postgraduate Open Day Postgraduate
    Wed, 14 Nov '18
  • University of Chester
    Chester campuses Undergraduate
    Wed, 14 Nov '18
  • Anglia Ruskin University
    Ambitious, driven, developing your career & employability? Aspiring in your field, up-skilling after a career break? Then our Postgrad Open Evening is for you. Postgraduate
    Wed, 14 Nov '18
Poll
Should Banksy be put in prison?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.