Author Topic: TT's Maths Thread (Read 145928 times) Tweet Share

TrueTears · « **Reply #555 on:** December 29, 2009, 02:19:51 pm »

Quote from: kamil9876 on December 29, 2009, 01:59:34 am

suppose it is redducible, then:

$f(x)=(b_qx^q....+b_0)(c_rx^r...+c_0)$

$b_qc_r=a_n$ is not divisible by $p$ , hence $b_q$ and $c_r$ are both not divisible by $p$ . $b_0c_0=a_0$ is divisible by $p$ , but not by $p^2$ , thus one of these terms is not divisible by $p$ , say WLOG $c_0$ .

$<br />a_1=c_0b_1+c_1b_0$

but $a_1$ is divisibly by $p$ , $c_1b_0$ is (since $c_1$ is). $c_0b_1$ must therefore be divisible by $p$ , but since $c_0$ isn't then $b_1$ must be.

hence so far we now know that $b_1$ and $b_0$ are divisible by $p$ .

$a_2=c_0b_2+c_1b_1+c_2b_0$

now we use a similair argument to show that b_2 is divisible by p. Hence we keep doing this until we get b_q is divisibly by p, which contradicts what we know. Eventually this proof is tantamount to the technique used in this old problem we solved earlier (problem 1)

What if say $a_0=2, b_0 = 4$ and $c_0 = 6$

Ain't $b_0$ and $c_0$ both divisible by $2$ ?

TrueTears · « **Reply #556 on:** December 29, 2009, 02:56:59 pm »

Yeap I get the rest kamil, very nice proof and same notation as the international maths olympiad question we did earlier in the month

So yeah it's just that one query...

kamil9876 · « **Reply #557 on:** December 29, 2009, 03:08:32 pm »

$c_0=a_0b_0=2*4\neq 6$

in general if $a_0=qp, b_0=rp$

$a_0b_0=qr (p^2)$ hence $p^2|c_0$ in this case.

TrueTears · « **Reply #558 on:** December 29, 2009, 03:19:53 pm »

Quote from: kamil9876 on December 29, 2009, 03:08:32 pm

$c_0=a_0b_0=2*4\neq 6$

in general if $a_0=qp, b_0=rp$

$a_0b_0=qr (p^2)$ hence $p^2|c_0$ in this case.

OH I see, lol I forgot the $p^2$ can not divide $a_0$ .

TrueTears · « **Reply #559 on:** December 29, 2009, 04:53:17 pm »

Consider the p-th cyclotomic polynomial $\phi_p(x) = 1+x+x^2+ \cdots +x^{p-1}$ where $p$ is a prime. Show that $\phi_p(x)$ is irreducible.

Why doesn't Eisenstein's criterion work?

$p^2$ does not divide $1$ .

$p$ does not divide the coefficient of $x^{p-1}$

But there are no $p$ that can divide the coefficients of all the $x$ terms since they are all $1$ ...

Doesn't this mean its reducible?

kamil9876 · « **Reply #560 on:** December 29, 2009, 05:25:40 pm »

In general: "A imples B" is not equivalent to "(not A) implies (not B)"

Specifically: So even though the criterion cannot be applied, that does not mean that the conclusion that the criterion would arrive at if applicable (that the polynomial is irreducible) is false.

TrueTears · « **Reply #561 on:** December 29, 2009, 05:27:26 pm »

Quote from: kamil9876 on December 29, 2009, 05:25:40 pm

In general: "A imples B" is not equivalent to "(not A) implies (not B)"

Specifically: So even though the criterion cannot be applied, that does not mean that the conclusion that the criterion would arrive at if applicable (that the polynomial is irreducible) is false.

Ah okay, so then how would you prove it is irreducible if Eisenstein's criterion can't be applied?

humph · « **Reply #562 on:** December 29, 2009, 06:42:27 pm »

Try making the substitution $x \mapsto x+1$ and then apply Eisenstein. Finally, use the fact that if $f(x+1)$ is irreducible, then so is $f(x)$ .

TrueTears · « **Reply #563 on:** December 29, 2009, 10:01:17 pm »

Quote from: humph on December 29, 2009, 06:42:27 pm

Try making the substitution $x \mapsto x+1$ and then apply Eisenstein. Finally, use the fact that if $f(x+1)$ is irreducible, then so is $f(x)$ .

But if you sub in x+1 doesn't that change the question? It's a totally different function?

zzdfa · « **Reply #564 on:** December 29, 2009, 10:38:37 pm »

Its a totally different function but if you can prove that function is irreducible then it implies that the original function is irreducible too (why?).

TrueTears · « **Reply #565 on:** December 29, 2009, 11:20:26 pm »

Ahh okay I think I understand the logic now.

Thanks guys.

$\phi_p(x) = 1+x+x^2+ \cdots +x^{p-1} \implies \phi_p(x) = \frac{x^p-1}{x-1}$

$\phi_p(x+1)$ is reducible iff $\phi_p(x)$ is reducible.

So assume $\phi_p(x)$ is reducible.

$\phi_p(x+1) = \frac{(x-1)^p-1}{x}$

$\frac{(x-1)^p-1}{x} = \frac{\binom{p}{0}x^p + \binom{p}{1}x^{p-1} + \binom{p}{2}x^{p-2} + \cdots + \binom{p}{p-1}x + \binom{p}{p}-1}{x}$

$\implies \phi_p(x+1) = \binom{p}{0}x^{p-1} + \binom{p}{1}x^{p-2} + \binom{p}{2}x^{p-3} + \cdots + \binom{p}{p-1}$

Now applying Eisenstein's criterion: $p$ does divide all coefficients except for the coefficient of $x^{p-1}$

$p^2$ certainly does not divide $\binom{p}{p-1}$ since $\binom{p}{p-1}=p$

Therefore $\phi_p(x+1)$ is irreducible. Contradiction!

So $\phi_p(x)$ is irreducible.

TrueTears · « **Reply #566 on:** December 30, 2009, 11:14:21 pm »

Prove that if a positive integer $m$ is not a perfect square, then $\sqrt{m}$ is irrational.

Cool simple question, wanted to share it around xD

kamil9876 · « **Reply #567 on:** December 30, 2009, 11:27:37 pm »

if it's not a square, then it cannot be an integer. and so it must be of the form:

$\frac{\prod p^{e^i}}{\prod q_i^{f^i}}$ . Where the numerator and denominator are relatively prime and the denominator is not 1 (not the empty product). Can the nth power of such a number be an integer? This proves it not just for square root, but for nth root.

TrueTears · « **Reply #568 on:** December 31, 2009, 01:12:42 am »

Yeap that's right.

So we assume $\sqrt{m}$ is rational thus $\sqrt{m} = \frac{a}{b} \implies m = \frac{a^2}{b^2}$ for some positive integer $a$ and $b$ . Assume that the trivial case $a = b$ is not included, thus $a \neq b$ .

Now for $m$ to be a perfect square, $\frac{a}{b}$ must be an integer, thus $a>b$ .

$a = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}p_{k+1}^{e_{k+1}}p_{k+2}^{e_{k+2}}p_{k+3}^{e_{k+3}} \cdots p_{k+n}^{e_{k+n}}$

$b = p_1^{f_1}p_2^{f_2} \cdots p_k^{f_k}$

$\implies \frac{a}{b} = \frac{p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}p_{k+1}^{e_{k+1}}p_{k+2}^{e_{k+2}}p_{k+3}^{e_{k+3}} \cdots p_{k+n}^{e_{k+n}}}{p_1^{f_1}p_2^{f_2} \cdots p_k^{f_k}} = p_1^{e_1-f_1}p_2^{e_2-f_2}p_3^{e_3-f_3} \cdots p_k^{e_k-f_k}p_{k+1}^{e_{k+1}}p_{k+2}^{e_{k+2}}p_{k+3}^{e_{k+3}} \cdots p_{k+n}^{e_{k+n}}$

$\implies \frac{a^2}{b^2} = p_1^{2(e_1-f_1)}p_2^{2(e_2-f_2)}p_3^{2(e_3-f_3)} \cdots p_k^{2(e_k-f_k)}p_{k+1}^{2e_{k+1}}p_{k+2}^{2e_{k+2}}p_{k+3}^{2e_{k+3}} \cdots p_{k+n}^{2e_{k+n}}$

Since $e_i-f_i \ge 0$ that means the exponents in the PPF of $\frac{a^2}{b^2}$ are all multiples of $2$ .

Thus $m$ is a perfect square.

This means $m$ is a perfect square iff $\sqrt{m}$ is an integer.

Therefore if $\sqrt{m}$ is irrational, $m$ is not a perfect square.

Actually kamil raised a good point.

What if $\sqrt{m}$ is rational?

Let's assume $\sqrt{m}$ is rational which means $\sqrt{m} = \frac{a}{b}$

Thus $(a,b) = 1$

So $m = \frac{a^2}{b^2}$ but $\left(a^2,b^2\right) = 1 \implies m \in \mathbb{Q}$

But $m$ must be an integer, so contradiction.

The only option left now is that if $\sqrt{m}$ is irrational then $m$ to be not a perfect square.

kamil9876 · « **Reply #569 on:** December 31, 2009, 01:39:02 am »

something feels sticky

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 145928 times) Tweet Share

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

humph

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Recent Posts

User:
Password: