Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

ok

Answer 8

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

Answer 9

did you get below part of the proof

Answer 10

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

Answer 11

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

Answer 12

are you on windows/mac ?

Answer 13

IS that the induction step btw?

Answer 14

i'm on windows 7

Answer 15

inductive*

Answer 16

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

Answer 17

ok hold on

Answer 18

should I choose "basic installation" ?

Answer 19

just click next keeping whatever is default

Answer 20

installed. Let me enter your id

Answer 21

click on "Meeting" and enter below id

m14-003-342

Answer 22

I think i'm in

Answer 23

I can hear you

Answer 24

Control panel?

Answer 25

I can see your screen now

Answer 26

am I supposed to turn on Microphone setting or something?

Answer 27

uh... how so?

Answer 28

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

Answer 29

microphone*

Answer 30

degree of g(x) is less than k

Answer 31

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\)

Answer 32

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

Answer 33

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

Answer 34

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

\(w_1, w_2, \ldots, w_k\) satisfy \(g(x)\)

Answer 35

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

Answer 36

right

Answer 37

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

Answer 38

right

Answer 39

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?

Answer 40

oh ok.

Answer 41

\(f(x)=x^9 + 2x^3 \)
\(g(x) = 8x^9 + 9x^3\)

then
\(f(x) \equiv g(x) \pmod 7\)

Answer 42

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

Answer 43

for all x?

Answer 44

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

Answer 45

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

Answer 46

oh, ok ^^

Answer 47

by assumption?

Answer 48

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 ?

Answer 49

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

Answer 50

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

Answer 51

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

Answer 52

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

Answer 53

uhm... I have no idea :D

Answer 54

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

Answer 55

right

Answer 56

wait why does p | a_n ?

Answer 57

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\)

Answer 58

rigt

Answer 59

contrapostive?

Answer 60

consdier below conditional :

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

Answer 61

must be a rectangle?

Answer 62

oh

Answer 63

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

Answer 64

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

Answer 65

the sides must be equal?

Answer 66

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 ?

Answer 67

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\)

Answer 68

that p divides the leading coefficient. But let me confirm that

IF A and B, then C

Suppose A and ~C, then ~B

right?

Answer 69

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

?

Answer 70

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

Answer 71

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

Answer 72

p does not*

Answer 73

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

Answer 74

right g(x)

Answer 75

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!

Answer 76

sorry, k-1 degree*

Answer 77

i don't know :D

Answer 78

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}\)

Answer 79

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

Answer 80

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

Answer 81

why's that? what modulo law was used?

Answer 82

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

Answer 83

@ganeshie8