## praxer one year ago help!

1. praxer

2. praxer

@SithsAndGiggles

3. ganeshie8

Hey!

4. praxer

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

which notation ?

6. praxer

7. praxer

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

8. ganeshie8

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

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

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

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

12. ganeshie8

they are picking mod2 because it is simpler

13. ganeshie8

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

14. ganeshie8

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

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

what same technique ? do you have a solution ?

17. ganeshie8

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

18. praxer

okay ! :)

19. ganeshie8

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

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

21. praxer

a,b,c,d

22. ganeshie8

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

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

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

25. ganeshie8

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

26. ganeshie8

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

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

CONTRADICTION AND THERE EXIST NO INTEGER K

29. ganeshie8

why is it a contradiction ?

30. ganeshie8

we can have : $$3 = 1*1*1*3$$ right ?

31. praxer

cause primes have only factors

32. praxer

only factors

33. ganeshie8

so what

34. praxer

only 2

35. ganeshie8

primes have only 2 "distinct" positive factors

36. ganeshie8

as you saw, we can write $$3$$ as product of $$4$$ factors : $$1*1*1*3$$

37. ganeshie8

so thats not really a contradiction

38. praxer

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

39. ganeshie8

I'm saying that is not a reason for contradiction

40. ganeshie8

41. praxer

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

42. praxer

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

what do you know about induction ?

44. praxer

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

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

46. ganeshie8

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

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

48. ganeshie8

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

49. praxer

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

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

They chose $$n$$ to induct on

52. ganeshie8

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

** 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".