## 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

1. anonymous

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

2. anonymous

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

3. ganeshie8

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

4. anonymous

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

5. anonymous

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

6. ganeshie8

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

7. anonymous

ok

8. anonymous

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

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

10. ganeshie8

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

11. anonymous

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

are you on windows/mac ?

13. anonymous

IS that the induction step btw?

14. anonymous

i'm on windows 7

15. anonymous

inductive*

16. ganeshie8

17. anonymous

ok hold on

18. anonymous

should I choose "basic installation" ?

19. ganeshie8

just click next keeping whatever is default

20. anonymous

installed. Let me enter your id

21. ganeshie8

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

22. anonymous

I think i'm in

23. anonymous

I can hear you

24. anonymous

Control panel?

25. anonymous

I can see your screen now

26. anonymous

am I supposed to turn on Microphone setting or something?

27. anonymous

uh... how so?

28. anonymous

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

29. anonymous

microphone*

30. ganeshie8

degree of g(x) is less than k

31. ganeshie8

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

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

33. anonymous

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

34. ganeshie8

$$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

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

36. anonymous

right

37. anonymous

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

right

39. anonymous

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

oh ok.

41. ganeshie8

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

42. anonymous

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

43. anonymous

for all x?

44. ganeshie8

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

45. anonymous

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

46. anonymous

oh, ok ^^

47. anonymous

by assumption?

48. ganeshie8

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

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

50. anonymous

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

51. ganeshie8

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

52. anonymous

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

uhm... I have no idea :D

54. anonymous

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

55. anonymous

right

56. anonymous

wait why does p | a_n ?

57. ganeshie8

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

rigt

59. anonymous

contrapostive?

60. ganeshie8

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

61. anonymous

must be a rectangle?

62. anonymous

oh

63. anonymous

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

64. ganeshie8

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

the sides must be equal?

66. ganeshie8

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

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

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

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

70. anonymous

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

71. anonymous

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

p does not*

73. ganeshie8

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

right g(x)

75. anonymous

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

sorry, k-1 degree*

77. anonymous

i don't know :D

78. ganeshie8

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

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

80. anonymous

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

81. anonymous

why's that? what modulo law was used?

82. anonymous

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

83. anonymous

@ganeshie8