Factoring over the integers

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
TSR launches Learn Together! - Our new subscription to help improve your learning 16-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
Search Thread
Advanced Search
Sign in to Reply
  1. Perpetuallity's Avatar
    1 01-06-2012  12:05
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Factoring over the integers
    Consider a binary homogeneous polynomial of degree two in two variables.

    q(x, y) = ax^2 + bxy +cy^2

    I'm concerned with factoring such polynomials quickly. For example, how could I factor 6x^2 +25xy +14y^2 over the integers quickly?
  2. SimonM's Avatar
    2 01-06-2012  12:10
    • PS Helper
    • TSR Idol
    • Posts: 9,190
    Re: Factoring over the integers
    By "factor" I assume you mean write as a product of linear factors mx+ny?

    In which case I suspect the quickest way would be to solve the quadratic:

    aX^2+bX+c = 0 = a(X-r_1)(X_r_2)

    Then you have:

    a(x-r_1y)(x-r_2y)

    So for you're example, we get:

    6(x+2/3)(x+7/2) = (3x+2)(2x+7)
    Last edited by SimonM; 01-06-2012 at 12:11.
  3. Perpetuallity's Avatar
    3 01-06-2012  12:16
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by SimonM)
    By "factor" I assume you mean write as a product of linear factors mx+ny?

    In which case I suspect the quickest way would be to solve the quadratic:

    aX^2+bX+c = 0 = a(X-r_1)(X_r_2)

    Then you have:

    a(x-r_1y)(x-r_2y)

    So for you're example, we get:

    6(x+2/3)(x+7/2) = (3x+2)(2x+7)
    Thanks, that's far better than my current method.
  4. Perpetuallity's Avatar
    4 01-06-2012  13:24
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    Also, how could I factor expressions of the form x^n \pm y^n. As an example, how could I factor x^5 - y^5 ?

    x^3 - y^3 = (x-y)(x^2 +xy +y^2) is a starting point, I guess.

    Edit: Just realised that for even n, factoring x^n - y^n is trivial.
    Last edited by Perpetuallity; 01-06-2012 at 13:44.
  5. bestofyou's Avatar
    5 01-06-2012  13:26
    • TSR Demigod
    • Location: Anratcitca Raescrh Stiaton
    • Posts: 5,088
    Re: Factoring over the integers
    is this A-level?
  6. Perpetuallity's Avatar
    6 01-06-2012  13:39
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by bestofyou)
    is this A-level?
    Hard to say, really. Its probably a little harder than A-Level but easier than BMO.

    But saying that, the study of quadratic forms can get quite technical when you introduce fields and such.

    I'm just looking for shortcuts here, of course I could just expand loads and loads of terms, but I really don't want to.
    Last edited by Perpetuallity; 01-06-2012 at 13:41.
  7. nuodai's Avatar
    7 01-06-2012  13:44
    • PS Helper
    • TSR Legend
    Re: Factoring over the integers
    (Original post by Perpetuallity)
    Also, how could I factor expressions of the form x^n \pm y^n. As an example, how could I factor x^5 - y^5 ?

    x^3 - y^3 = (x-y)(x^2 +xy +y^2) is a starting point, I guess.

    Edit: Just realised that its trivial for even n, factoring x^n - y^n is trivial.
    I'm not convinced.

    For instance, x^4-y^4=(x-y)(x^3 + x^2y + xy^2 + y^3) can be factorised further.
  8. Perpetuallity's Avatar
    8 01-06-2012  13:46
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by nuodai)
    I'm not convinced.

    For instance, x^4-y^4=(x-y)(x^3 + x^2y + xy^2 + y^3) can be factorised further.
    Perhaps trivial was the wrong word to use. Symmetrical was what I had in mind.

    Edit: But saying that, x^5 - y^5 has symmetry too, so what I wrote before was tosh. For clarity, I meant symmetry in the non linear factor.

    Edit 2: Letting n=6, we get x^6 - y^6 = (x^3 +y^3)(x^3 - y^3)= (x-y)(x+y)(x^2 -xy + y^2)(x^2 +xy +y^2)

    Does there exist some theorem that generalises such results?:holmes:
    Last edited by Perpetuallity; 01-06-2012 at 14:03.
  9. Glutamic Acid's Avatar
    9 01-06-2012  14:23
    • TSR Legend
    • Location: E.I.R.E. / S.E. / Cam
    Re: Factoring over the integers
    (Original post by Perpetuallity)
    Perhaps trivial was the wrong word to use. Symmetrical was what I had in mind.

    Edit: But saying that, x^5 - y^5 has symmetry too, so what I wrote before was tosh. For clarity, I meant symmetry in the non linear factor.

    Edit 2: Letting n=6, we get x^6 - y^6 = (x^3 +y^3)(x^3 - y^3)= (x-y)(x+y)(x^2 -xy + y^2)(x^2 +xy +y^2)

    Does there exist some theorem that generalises such results?:holmes:
    Sort of. x^p - y^p = (x-y)(x^{p-1} + x^{p-2}y + ... + xy^{p-2} + y^{p-1}) is the best you have when p is a prime. (If we had a factorization then we'd have a factorization when y = 1, and this shows that it cannot be done.)
  10. Perpetuallity's Avatar
    10 01-06-2012  14:34
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by Glutamic Acid)
    Sort of. x^p - y^p = (x-y)(x^{p-1} + x^{p-2}y + ... + xy^{p-2} + y^{p-1}) is the best you have when p is a prime. (If we had a factorization then we'd have a factorization when y = 1, and this shows that it cannot be done.)
    And I suppose x^{2k+1} + y^{2k+1} = (x+y)(x^{2k} - x^{2k-1}y + x^{2k-2}y^2 -...+y^{2k}).
  11. SimonM's Avatar
    11 01-06-2012  14:34
    • PS Helper
    • TSR Idol
    • Posts: 9,190
    Re: Factoring over the integers
    Cyclotomic polynomials are the way to go here:

    X^n-1 = \prod_{d|n} \Phi_d(X) so we can write:

    x^n-y^n = \prod_{d|n} y^{\phi(d)}\Phi_d(x/y)
  12. Perpetuallity's Avatar
    12 01-06-2012  15:03
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by SimonM)
    Cyclotomic polynomials are the way to go here:

    X^n-1 = \prod_{d|n} \Phi_d(X) so we can write:

    x^n-y^n = \prod_{d|n} y^{\phi(d)}\Phi_d(x/y)
    I'm quite new to number theory and am quite excited by seeing the Euler Totient function entwined in that product, although I've never really studied cyclotomic polynomials in any real depth! Thanks.
    Last edited by Perpetuallity; 01-06-2012 at 15:12.
  13. SimonM's Avatar
    13 01-06-2012  15:12
    • PS Helper
    • TSR Idol
    • Posts: 9,190
    Re: Factoring over the integers
    (Original post by Perpetuallity)
    I'm quite new to number theory and am quite excited by seeing the Euler Totient function entwined in that product, although I've never really studied cyclotomic polynomials! Thanks.
    They're quite interesting and easily accessible to an A-level student. (Although it's possible to treat them in complicated unaccessible ways).

    The reason it appears is because \deg \Phi_d = \phi(d)

    The reason \deg \Phi_d = \phi(d) is because there are \phi(d) primitive dth roots of unity.

    The reason there are \phi(d) dth roots of unity is because if \zeta is a primitive dth root of unit so is \zeta^k for (k,d) = 1 and these are the only other possibilities.
  14. Perpetuallity's Avatar
    14 01-06-2012  15:22
    • Exalted and Worshipped Member
    • Location: Wales
    • Posts: 910
    Re: Factoring over the integers
    (Original post by SimonM)
    They're quite interesting and easily accessible to an A-level student. (Although it's possible to treat them in complicated unaccessible ways).

    The reason it appears is because \deg \Phi_d = \phi(d)

    The reason \deg \Phi_d = \phi(d) is because there are \phi(d) primitive dth roots of unity.

    The reason there are \phi(d) dth roots of unity is because if \zeta is a primitive dth root of unit so is \zeta^k for (k,d) = 1 and these are the only other possibilities.
    Ah I see, makes much much more sense now.
Sign in to Reply
Search Thread
Advanced Search
Share this discussion:  
Useful resources

Articles:

Study Help rules and posting guidelinesStudy Help Member of the Month nominationsGuide to MathematicsMathematics resourcesMathematics websitesMathematics revision notes in the TSR wikiCambridge Assessment admissions tests (including STEP)How to use LaTeXCareers in Mathematics

Useful Dates:

Quick Link:

Unanswered Maths Threads

Groups associated with this forum:

View associated groups
Article updates
Moderators

We have a brilliant team of more than 60 volunteers looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is moderated by:

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

Shortcuts

Get Started

TSR Group

Using TSR

Info

Connect with TSR

Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.