Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured Challenge Math Challenge by QuantumQuest #1

  1. Mar 16, 2017 #1
    Submitted by: @QuantumQuest
    Credit to: @stevendaryl

    RULES:

    1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
    2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
    3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
    4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

    CHALLENGE:
    Prove that if ##P(x), Q(x), R(x)## and ##S(x)## are all polynomials such that ##P(x^{5}) + xQ(x^{5}) + x^{2}R(x^{5}) = (x^{4} + x^{3} + x^{2} + x + 1)S(x)##, ##x - 1## is factor of ##P(x)##.
     
    Last edited: Mar 17, 2017
  2. jcsd
  3. Mar 16, 2017 #2

    Charles Link

    User Avatar
    Homework Helper

    @QuantumQuest Looks like a good problem. I tried working it for a few minutes=I don't see a simple solution. :) :)
     
  4. Mar 16, 2017 #3
    Let ##\sigma_1=1,\sigma_2,\ldots,\sigma_5## be all the roots of the polynomial ## x^5-1##. Then ##\sigma_2,\ldots,\sigma_5## are the roots of the polynomial ##x^4+x^3+x^2+x+1##. Substitute these roots to our equality:
    $$P(1)+\sigma_jQ(1)+\sigma_j^2R(1)=0,\quad j=2,3,4,5$$
    This system of linear equations must imply $$P(1)=Q(1)=R(1)=0$$ I guess :)
     
    Last edited: Mar 16, 2017
  5. Mar 16, 2017 #4

    Charles Link

    User Avatar
    Homework Helper

    If I may give an input here (I'm not really a judge=besides @QuantumQuest the judging is sort of being done by committee), this looks like a very good start, but the last step of showing ## P(1)=0 ## needs to be completed. If you write out the equations for ## j=2, \, j=3, \, and \, j=4 ##, you can get an answer for what ## P(1), Q(1), \, and \, R(1) ## needs to be. (By substitution method of the 3 equations and 3 unknowns.) I think it is then possible to show that this solution for ## P(1), Q(1), and \, R(1) ## is inconsistent with the 4th equation (## j=5 ##). This would likely result in the requirement that ## P(1)=Q(1)=R(1)=0 ## as @zwierz has conjectured. ## \\ ## Editing... I need to brush up on solutions for a set of linear homogeneous equations, but in any case, I do think the conjecture put forth by @zwierz is likely to be the case).
     
    Last edited: Mar 16, 2017
  6. Mar 16, 2017 #5

    fresh_42

    Staff: Mentor

    Four different solutions for a quadratic equation?
     
  7. Mar 16, 2017 #6

    Charles Link

    User Avatar
    Homework Helper

    It's a set of linear equations with constant coefficients. Without checking it explicity, it is possible that a couple of the four equations could get repeated, etc.
     
  8. Mar 16, 2017 #7

    fresh_42

    Staff: Mentor

    It's a quadratic equation over a field with four different solutions. ##P(1) = P(x^5)## modulo ##(x^4+x^3+x^2+x+1)## is a scalar.
     
  9. Mar 16, 2017 #8
    I have checked that. The rank of the matrix=3
     
  10. Mar 16, 2017 #9

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    Here's my approach:

    We are given that

    [itex]P(x^5) + x Q(x^5) + x^2 R(x^5) = (1+x+x^2 + x^3 + x^4)S(x)[/itex]

    Now, having done a lot of power series, I recognize that [itex]1+x+x^2 + x^3 + x^4 = \frac{1-x^5}{1-x}[/itex]. (To prove this, multiply both sides by [itex]1-x[/itex]). So let me rewrite our equation as follows:
    [itex]P(x^5) + x Q(x^5) + x^2 R(x^5) = \frac{1-x^5}{1-x} S(x)[/itex]

    So what that means is that if [itex]x \neq 1[/itex] but [itex]x^5 = 1[/itex], then the right-hand side is 0. Wait a minute! How can [itex]x^5 = 1[/itex] unless [itex]x=1[/itex]? If you use complex numbers, there are 5 fifth-roots of 1!

    Let [itex]r = e^{2 \pi i/5}[/itex]. Then our 5 roots of 1 are:

    [itex]1, r, r^2, r^3, r^4[/itex]

    Raise any of those to the 5th power, and you get [itex]r^{5n} = e^{2 n \pi i} = 1[/itex] for [itex]n=0,1,2,3,4[/itex].

    So letting x be any of the roots (other than 1) will make the right-hand side equal to zero. That means that it also makes the left-hand side zero. So for each [itex]j=1,2,3,4[/itex], we have [itex]P((r^j)^5) + (r^j) Q((r^j)^5) + (r^j)^2 R((r^j)^5) = 0[/itex]. Since for any j, we have that [itex](r^j)^5 = 1[/itex], then we have 4 equations:

    1. [itex]P(1) + r Q(1) + r^2 R(1) = 0[/itex]
    2. [itex]P(1) + r^2 Q(1) + r^4 R(1) = 0[/itex]
    3. [itex]P(1) + r^3 Q(1) + r^6 R(1) = 0 \Rightarrow P(1) + r^3 Q(1) + r R(1) = 0[/itex] (since [itex]r^6 = r^5 \cdot r = r[/itex])
    4. [itex]P(1) + r^4 Q(1) + r^8 R(1) = 0 \Rightarrow P(1) + r^4 Q(1) + r^3 R(1) = 0[/itex] (since [itex]r^8 = r^5 \cdot r^3 = r^3[/itex])
    This is 4 equations and only 3 unknowns, so the only possible solution is the trivial one: [itex]P(1) = Q(1) = R(1) = 0[/itex].

    So 1 is a zero of [itex]P(x)[/itex], which means [itex]P(x)[/itex] has a factor of [itex]x-1[/itex].
     
  11. Mar 16, 2017 #10

    fresh_42

    Staff: Mentor

    I still think post #3 is a complete and sufficient proof. Passing to ##\mathbb{Q}[x]/(x^4+x^3+x^2+x+1)## and using the irreducibility (thus being prime) solves the equation at once.
     
  12. Mar 16, 2017 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Edit: Ah, I missed the 5 in the original problem.
    The proof in post 3 should be sufficient, although it could have added that those roots are all different.
     
  13. Mar 16, 2017 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I missed the 5th power in the argument in the problem statement. See my edited post.
     
  14. Mar 16, 2017 #13

    Charles Link

    User Avatar
    Homework Helper

    The ## x=\sigma_j ## for some j is used to make the 4 equations. The coefficient of ## S(x) ##, (x^4+x^3+x^2+x+1), is zero for any choice of j=2,3,4,5. Meanwhile ## \sigma_j^5=1 ## for all j.
     
  15. Mar 16, 2017 #14

    Charles Link

    User Avatar
    Homework Helper

    We need to hear from @QuantumQuest , but I think the general consensus is that @zwierz has successfully solved it.
     
  16. Mar 16, 2017 #15

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Let ##P(x) = a_0 + a_1x + \dots a_n x^n## and ##S(x) = b_0 + b_1x + \dots b_m x_m##

    By comparing coefficients of ##x^0## we have:
    ##a_0 = b_0##

    Also, we have:

    ##a_1 = b_5 - b_0##

    To get this, compare the coefficients of ##x^3, x^4## and ##x^5##:

    ##x^3: \ 0 = b_0 + b_1 + b_2 + b_3## hence ##b_1 + b_2 + b_3 = -b_0##
    ##x^4: \ 0 = b_0 + b_1 + b_2 + b_3 + b_4## hence ##b_4 = 0##
    ##x^5: \ a_1 = b_1 +b_2 + b_3 + b_4 + b_5## hence ##a_1 = b_5 - b_0##

    Next: ##a_2 = b_{10} - b_5##

    ##x^8: \ 0 =b_4 + b_5 + b_6 + b_7 + b_8## hence ##b_6 + b_7 + b_8 = -b_5##
    ##x^9: \ 0 = b_5 + b_6 + b_7 + b_8 + b_9## hence ##b_9 = 0##
    ##x^{10}: \ a_2 = b_6 +b_7 + b_8 + b_9 + b_{10}## hence ##a_2 = b_{10} - b_5##

    The same argument applies for all coefficients modulo 5, giving, for ##k > 0##:

    ##a_k = b_{5k} - b_{5(k-1)}##

    This gives:

    ##a_0 + a_1 + \dots + a_n = b_{5n}##

    But, also ##b_{5(n+1)} = a_{n+1} + b_{5n} = b_{5n}##

    Hence ##b_{5k} = b_{5n}## for all ##k > n##, and so all these must be ##0##. So, finally we have:

    ##a_0 + a_1 + \dots + a_n = 0##, ##P(1) = 0## and ##(x-1)## is a factor of ##P(x)##.

    There must be a cleverer way!
     
  17. Mar 16, 2017 #16
    zwierz and Charles Link were speaking about the equation

    [tex]
    \left(\begin{array}{ccc}
    1 & \sigma_2 & \sigma_2^2 \\
    1 & \sigma_3 & \sigma_3^2 \\
    1 & \sigma_4 & \sigma_4^2 \\
    1 & \sigma_5 & \sigma_5^2 \\
    \end{array}\right)
    \left(\begin{array}{c}
    P(1) \\ Q(1) \\ R(1) \\
    \end{array}\right)
    = \left(\begin{array}{c}
    0 \\ 0 \\ 0 \\ 0 \
    \end{array}\right)
    [/tex]

    Yes, it can be concluded by an application by the Vandermonde determinant formula. It implies that the determinant of the [itex]3\times 3[/itex] upper block is non-zero.
     
  18. Mar 16, 2017 #17

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No need for linear algebra. I agree with @fresh_42

    ##P(1) + \sigma_j Q(1) + \sigma_j^2 R(1) = 0##

    is a quadratic in ##\sigma_j##, with at most ##2## distinct solutions for ##\sigma_j##.

    The 5th roots of 1 are clearly distinct.
     
    Last edited: Mar 16, 2017
  19. Mar 16, 2017 #18

    fresh_42

    Staff: Mentor

    I know. However, it's simply not necessary. To be honest this was how far I came, too. But the clue in post #3 doesn't need it. All that is really needed, is the fact, that the quotient ring doesn't have zero divisors and the extension is separable.
     
  20. Mar 16, 2017 #19

    QuantumQuest

    User Avatar
    Gold Member

    Do you need five equations?
     
  21. Mar 16, 2017 #20
    I see. The comments about polynomial division confused me. What was the point of those?

    Anyway, I think that three different solutions to the challenge can now be found from what has been written above.
     
    Last edited: Mar 16, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Math Challenge by QuantumQuest #1
  1. Challenging math riddle (Replies: 20)

  2. (Easy) Maths Challenge (Replies: 2)

Loading...