A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Explain this proof of polynomial congruences by George Andrews. I don't get where it says: "However p (not divide symbol) aₒ, and since the w_i are mutually incongruent, the difference between any two w_i is not divisible by p." How so? https://books.google.com/books?id=eVwvvwZeBf4C&lpg=PA58&pg=PA72#v=onepage&q&f=false

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    It's actually on the next page after you click on the link, but you might wanna read the proof first

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think it's saying, if a is incongruent b mod c, then c does not divide (a-b)

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that is lagrange's theorem, one of the most important theorems in group theory

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh ok. But can you please explain the statement above? ^^

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    why doesn't p divide the difference of any of the two w_i? I was thinking it's true by definition

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    before explaining that, let me ask you a question from the same proof

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    The proof use both induction and contradiction at the same time. I'm still trying to figure the general layout of the proof

  9. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    did you get below part of the proof |dw:1441691724959:dw|

  10. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    why must \(g(x)\) be congruent to \(0\) for "every" integer \(x\) ?

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think I did. But let me explain to see if I really did. But book first proved base cases for n = 0 and n = 1. Now it assumed that f(x) is a polynomial with k degree but with (k+1) mutually incongruent solutions

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    are you on windows/mac ?

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    IS that the induction step btw?

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'm on windows 7

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    inductive*

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    see if you can install teamviewer http://download.teamviewer.com/download/TeamViewer_Setup_en.exe

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok hold on

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    should I choose "basic installation" ?

  19. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    just click next keeping whatever is default

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    installed. Let me enter your id

  21. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    click on "Meeting" and enter below id m14-003-342

  22. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think i'm in

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I can hear you

  24. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Control panel?

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I can see your screen now

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    am I supposed to turn on Microphone setting or something?

  27. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    uh... how so?

  28. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I am supposed to connect a physical micrphone to my computer?

  29. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    microphone*

  30. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    degree of g(x) is less than k

  31. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so \(g(x)\) satisfies induction assumption but \(g(x)\) has \(k\) roots so it must be the case that ALL coefficients of \(g(x)\) are divisible by \(p\)

  32. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hold on, let me re-read the part that you posted

  33. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the w's are the roots of f(x) right?

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \(w_1, w_2, \ldots, w_k, w_{k+1}\) satisfy \(f(x)\) \(w_1, w_2, \ldots, w_k\) satisfy \(g(x)\)

  35. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait, how do w1, ..., wk satisfy g(x)??

  36. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right

  37. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh ok, if you plug any value of w1, ..., wk, in for x, we get: g(x) = f(x), for all x of w1,...wk

  38. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right

  39. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, but what does g(x) = f(x) mean though? Does it mean g(x) ≡ f(x) (mod p) for all x of w1, ... ,wk?

  40. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh ok.

  41. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \(f(x)=x^9 + 2x^3 \) \(g(x) = 8x^9 + 9x^3\) then \(f(x) \equiv g(x) \pmod 7\)

  42. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, so you're saying [(x^9 + 2x^3) - (8x^9 + 9x^3) ]/7 is an integer for some x

  43. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    for all x?

  44. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    [(x^9 + 2x^3) - (8x^9 + 9x^3) ]/7 is an integer for "every" x

  45. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    let me simplify it using wolfram alpha to see. Hold on

  46. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh, ok ^^

  47. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    by assumption?

  48. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Induction assumption : every polynomial of degree \(n\) less than \(k\) has at most \(n\) incongruent solutions mod prime \(p\) \(g(x)\) satisfies induction assumption since degree is less than \(k\) also \(g(x)\) has \(k\) incongruent solutoins so it must be the case that ALL coefficients of \(g(x)\) are divisible by \(p\), why ?

  49. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what do yo mean by coefficients of g(x)? you mean the constants in front of the x's?

  50. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so you're saying g(x) congruent f(x) congruent 0 because the coefficients of g(x) are divisible by p?

  51. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    g(x) congruent 0 for all x because the coefficients of g(x) are divisible by p

  52. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh oh i see. You're saying g(x) congruent 0 (mod p) because the coefficients of g(x) are divisiple by p

  53. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    uhm... I have no idea :D

  54. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you're asking why all the coeffient of g(x) are divisible by p

  55. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right

  56. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait why does p | a_n ?

  57. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Induction assumption : If the degree of polynomial is \(n\) and if it is less than \(k\), then it has at most \(n\) incongruent solutions mod prime \(p\) provided \(p\nmid a_n\)

  58. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    rigt

  59. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    contrapostive?

  60. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    consdier below conditional : If a quadrilateral has four right angles, and if all sides are equal, then it is a square

  61. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    must be a rectangle?

  62. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh

  63. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think i'm starting to see what you're trying to get at.

  64. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    there is some quadrilateral that you know that has four right angles and you also happen to know that it is a square what can you say about its sides

  65. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the sides must be equal?

  66. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you know that the degree of g(x) is less than k and you also happen to know that g(x) has "k" incongruent solutions what can you say about its leading coefficient ?

  67. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Induction assumption : If the degree of polynomial is \(n\) and if it is less than \(k\), then it has at most \(n\) incongruent solutions mod prime \(p\) provided \(p\nmid a_n\)

  68. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that p divides the leading coefficient. But let me confirm that IF A and B, then C Suppose A and ~C, then ~B right?

  69. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \((A\land B) \implies C \\\iff\\ (A\land \neg C) \implies \neg B\) ?

  70. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so what I said is correct? about A,B,C

  71. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so about the assumption: A = p divides leading coefficient B = f(x) has n degree C = f(x) has at most n incongruent solutions

  72. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    p does not*

  73. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so about the assumption: A = p does not divide the leading coefficient B = g(x) has degree n which is less than k C = g(x) has at most n incongruent solutions

  74. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right g(x)

  75. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, so since g(x) has k-1 (which less than k), but it has k incongruent solutions, therefor P must divide the leading coefficient!

  76. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    sorry, k-1 degree*

  77. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i don't know :D

  78. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    since \(p\mid a_k\), \(g(x) \equiv 0x^{k}+a_{k-1}x^{k-1}+\cdots + a_1x+a_0 \\\equiv a_{k-1}x^{k-1}+\cdots + a_1x+a_0 \pmod{p}\)

  79. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    since p | a_k, a_k congrent 0 (mod p) right

  80. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'm still puzzled at why you replaced a_k with 0

  81. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    why's that? what modulo law was used?

  82. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry if I'm slow. Going from integer to polynomial is big jump for me XD

  83. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8

  84. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.