A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

praxer

  • one year ago

help!

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

    1 Attachment
  2. praxer
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @SithsAndGiggles

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

    Hey!

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

    why to check integer roots of a polynomial modulo is used. I am bit confused with such notion. Anyone please explain the use of modulo precisely in proving that polynomial has no integer roots.

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

    which notation ?

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

    1 Attachment
  7. praxer
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    wait! is it about the constant term being divisible by 2. I get this ?!! But why 2

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

    2 has nothing to do with the problem since 1) the coefficients are integers and 2) you're looking for integer roots, you are allowed to use modular arithmetic here

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

    consider a quick example : \[P(x) = x^2-2x +1 = 0 \] suppose \(n\) is an integer root, then we have : \[P(n) = n^2-2n+1 = 0\] we are allowed to take mod both sides because we're dealing with integers (n and all coefficients are integers)

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

    taking mod 2 both sides you get \[ n^2-2n+1 \equiv 0 \pmod{2}\] which is same as \[ n^2+1 \equiv 0 \pmod{2}\]

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

    computations get simpler in modular arithmetic, observe that middle -2n term has just disappeared in mod2!

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

    they are picking mod2 because it is simpler

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

    It doesn't matter which modulus, \(m\), you pick it will be true everywhere.

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

    so is below statement clear ? If \(n\) is an integer root of a polynomial \(P(x)\) with integer coeffcients, then \(P(n) \equiv 0 \pmod{m}\).

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

    yes! now for the question. Can the same technique be used. Like f(x)=(x-a)(x-b)(x-c)(x-d)r(x)+5 and.......?????

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

    what same technique ? do you have a solution ?

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

    The actual problem turns out to be much simpler, we don't need fancy modular arithmetic etc...

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

    okay ! :)

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

    Lets first look at a rough sketch of \(f(x)\) since \(f(a)=f(b)=f(c)=f(d)=5\), the graph looks something like : |dw:1438956400888:dw|

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

    Pull that graph down by \(5\) units and call it \(g(x)\). where does \(g(x)\) cut the x axis ?

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

    a,b,c,d

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

    Yes, so it is easy to see that \(a,b,c,d\) are the roots of the polynomial \(g(x)\) (pulled down by \(5\) units version of \(f(x)\))

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

    so \(g(x)\) will be of form : \[g(x) = (x-a)(x-b)(x-c)(x-d)h(x)\] where \(h(x)\) is some other polynomial with integer coeffcients

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

    f(x)=(x−a)(x−b)(x−c)(x−d)h(x)+5 ???

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

    Yes, rearrange and get : \[f(x)-5 = (x-a)(x-b)(x-c)(x-d)h(x)\]

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

    suppose there exists an integer \(k\) such that \(f(k) = 8\), plugin \(x = k\) in above equation : \[f(k)-5 = (k-a)(k-b)(k-c)(k-d)h(k)\\~\\8-5= (k-a)(k-b)(k-c)(k-d)h(k)\\~\\ 3=(k-a)(k-b)(k-c)(k-d)h(k)\\\]

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

    Notice that the right hand side is a product of \(4\) integers but the left hand side is a prime number what can you say ?

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

    CONTRADICTION AND THERE EXIST NO INTEGER K

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

    why is it a contradiction ?

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

    we can have : \(3 = 1*1*1*3\) right ?

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

    cause primes have only factors

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

    only factors

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

    so what

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

    only 2

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

    primes have only 2 "distinct" positive factors

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

    as you saw, we can write \(3\) as product of \(4\) factors : \(1*1*1*3\)

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

    so thats not really a contradiction

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

    okay then what will it be called?? Btw I have a doubt. May I ??

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

    I'm saying that is not a reason for contradiction

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

    sure, ask

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

    first the why it was used by induction on n and second the use of inductive assumtion

    1 Attachment
  42. praxer
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1. Assume is fixed and use induction on 2.hence by the inductive assumption In many proof writing, inductive is being used I know the theory but induction andsolve the +2 question. But many times it is confusing

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

    what do you know about induction ?

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

    well frankly speaking I know that it is like true for n=1 and then if the given condition is true for n=k+1 whenever it is true for n=k then it is true for all natural numbers.

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

    why is it so ? do you have a proof for that statement ?

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

    Prove this : If : 1) The statement is true for \(n=1\) 2) The statement is true for \(n=k+1\), whenever it is true for \(n=k\) Then : the statement is true for all integers greater than \(1\) too.

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

    not now, when you're free, go through that proof of "why/how induction works" and try to understand :)

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

    Its not hard but you just need to see it once and understand

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

    okay! one thing what do you understand from the page like using the term induction on n. I want to have a normal idea of what others feel when they read that line. :)

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

    Notice that there are several variables in that problem : \(k,n\) etc you need to clear on what variable you're picking to "induct on".

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

    They chose \(n\) to induct on

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

    but you may pick \(k\) to induct on too : 1) show that the statement is true for \(k=1\) 2) show that the statement is true for \(k=t+1\), whenever it is true for \(k=t\)

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

    ** Notice that there are several variables in that problem : \(k,n\) etc you need to \(\color{red}{\text{be}}\) clear on what variable you're picking to "induct on".

  54. 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.