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

- anonymous

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- chestercat

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

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

- anonymous

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

- ganeshie8

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

Looking for something else?

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

## More answers

- anonymous

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

- anonymous

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

- ganeshie8

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

- anonymous

ok

- anonymous

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

- ganeshie8

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

- ganeshie8

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

- 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

- ganeshie8

are you on windows/mac ?

- anonymous

IS that the induction step btw?

- anonymous

i'm on windows 7

- anonymous

inductive*

- ganeshie8

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

- anonymous

ok hold on

- anonymous

should I choose "basic installation" ?

- ganeshie8

just click next keeping whatever is default

- anonymous

installed. Let me enter your id

- ganeshie8

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

- anonymous

I think i'm in

- anonymous

I can hear you

- anonymous

Control panel?

- anonymous

I can see your screen now

- anonymous

am I supposed to turn on Microphone setting or something?

- anonymous

uh... how so?

- anonymous

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

- anonymous

microphone*

- ganeshie8

degree of g(x) is less than k

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

- anonymous

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

- anonymous

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

- ganeshie8

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

- anonymous

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

- anonymous

right

- 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

- anonymous

right

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

- anonymous

oh ok.

- ganeshie8

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

- anonymous

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

- anonymous

for all x?

- ganeshie8

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

- anonymous

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

- anonymous

oh, ok ^^

- anonymous

by assumption?

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

- anonymous

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

- anonymous

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

- ganeshie8

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

- anonymous

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

- anonymous

uhm... I have no idea :D

- anonymous

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

- anonymous

right

- anonymous

wait why does p | a_n ?

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

- anonymous

rigt

- anonymous

contrapostive?

- ganeshie8

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

- anonymous

must be a rectangle?

- anonymous

oh

- anonymous

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

- 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

- anonymous

the sides must be equal?

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

- ganeshie8

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

- ganeshie8

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

- anonymous

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

- 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

- anonymous

p does not*

- 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

- anonymous

right g(x)

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

- anonymous

sorry, k-1 degree*

- anonymous

i don't know :D

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

- anonymous

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

- anonymous

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

- anonymous

why's that? what modulo law was used?

- anonymous

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

- anonymous

@ganeshie8

Looking for something else?

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