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

TrueTears · « **Reply #495 on:** December 22, 2009, 04:19:10 pm »

Quote from: kamil9876 on December 22, 2009, 04:14:03 pm

lulz yes, but it's nice to have a simple and elementary proof. Though it just goes to show how intuitive bertrand's postulate is

Lol yeah when you did it, you didn't even think about proving it haha

TrueTears · « **Reply #496 on:** December 22, 2009, 09:27:42 pm »

Quote from: kamil9876 on December 22, 2009, 01:04:29 pm

3.) suppose some integer $d>1$ , divides $f_{n+1}$ and $f_{n+2}$ then $f_n=f_{n+2}-f_{n+1}$ hence $d|f_n$ . Now $f_{n-1}=f_{n+1}-f_n$ hence $d|f_{n-1}$ . Now $f_{n-2}=f_{n}-f_{n-1}$ hence $d|f_{n-2}$ ... etc and we can imagine continuing this process until we get to $d|f_3$ and $d|f_4$ which is false since no integer greater than 1 divides both of these(2 and 3).

lol kamil, I love this proof of yours so simple!!

kamil9876 · « **Reply #497 on:** December 22, 2009, 09:30:07 pm »

actually, it can be stated in an even shorter way

. Suppose n is the smallest integer such that $f_n$ and $f_{n+1}$ has some d>1 that divides them both. Then d divides $f_{n-1}$ and so the result is also true for n-1. but n-1<n and this contradicts n being the smallest! LOL

TrueTears · « **Reply #498 on:** December 22, 2009, 09:31:45 pm »

Quote from: kamil9876 on December 22, 2009, 09:30:07 pm

actually, it can be stated in an even shorter way . Suppose n is the smallest integer such that $f_n$ and $f_{n+1}$ has some d>1 that divides them both. Then d divides $f_{n-1}$ and so the result is also true for n-1. but n-1<n and this contradicts n being the smallest! LOL

hahahaha, that's such a cool question.

TrueTears · « **Reply #499 on:** December 22, 2009, 11:55:14 pm »

Quote

2. Let $\{a,b,c\} \in \mathbb{N}$ , show that $\frac{[a,b,c]^2}{[a,b][b,c][c,a]} = \frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$

Let $a = p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}$

$b = p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}$

$c = p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}$

Where $p_i$ is a prime for all $i \in [1,n]$ and $\{e_i,f_i,g_i\} \in \mathbb{N}$

$[a,b] = p_1^{\text{max}(e_1,f_1)}p_2^{\text{max}(e_2,f_2)} \cdots p_n^{\text{max}(e_n,f_n)}$

$[b,c] = p_1^{\text{max}(f_1,g_1)}p_2^{\text{max}(f_2,g_2)} \cdots p_n^{\text{max}(f_n,g_n)}$

$[c,a] = p_1^{\text{max}(g_1,e_1)}p_2^{\text{max}(g_2,e_2)} \cdots p_n^{\text{max}(g_n,e_n)}$

$[a,b,c] = p_1^{\text{max}(e_1,f_1,g_1)}p_2^{\text{max}(e_2,f_2,g_2)} \cdots p_n^{\text{max}(e_n,f_n,g_n)}$

WLOG assume $e_n \ge f_n \ge g_n \ \forall \ n$

$[a,b][b,c] = \left(p_1^{\text{max}(e_1,f_1)}p_2^{\text{max}(e_2,f_2)} \cdots p_n^{\text{max}(e_n,f_n)}\right)\left(p_1^{\text{max}(f_1,g_1)}p_2^{\text{max}(f_2,g_2)} \cdots p_n^{\text{max}(f_n,g_n)}\right) = \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)$

$\implies \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)[c,a] = \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{\text{max}(g_1,e_1)}p_2^{\text{max}(g_2,e_2)} \cdots p_n^{\text{max}(g_n,e_n)}\right)$

$\implies \mbox{RHS} = \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right) = \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)^2\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)$

$[a,b,c]^2 = \left(p_1^{\text{max}(e_1,f_1,g_1)}p_2^{\text{max}(e_2,f_2,g_2)} \cdots p_n^{\text{max}(e_n,f_n,g_n)}\right)^2 = \left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)^2$

$\therefore \mbox{LHS} = \frac{\left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)^2}{\left(p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}\right)^2\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)} = \frac{1}{\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)}$

$(a,b) = p_1^{\text{min}(e_1,f_1)}p_2^{\text{min}(e_2,f_2)} \cdots p_n^{\text{min}(e_n,f_n)}$

$(b,c) = p_1^{\text{min}(f_1,g_1)}p_2^{\text{min}(f_2,g_2)} \cdots p_n^{\text{min}(f_n,g_n)}$

$(c,a) = p_1^{\text{min}(g_1,e_1)}p_2^{\text{min}(g_2,e_2)} \cdots p_n^{\text{min}(g_n,e_n)}$

$(a,b,c) = p_1^{\text{min}(e_1,f_1,g_1)}p_2^{\text{min}(e_2,f_2,g_2)} \cdots p_n^{\text{min}(e_n,f_n,g_n)}$

$(a,b)(b,c) = \left(p_1^{\text{min}(e_1,f_1)}p_2^{\text{min}(e_2,f_2)} \cdots p_n^{\text{min}(e_n,f_n)}\right)\left(p_1^{\text{min}(f_1,g_1)}p_2^{\text{min}(f_2,g_2)} \cdots p_n^{\text{min}(f_n,g_n)}\right) = \left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)$

$\implies \left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)(c,a) = \left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)\left(p_1^{\text{min}(g_1,e_1)}p_2^{\text{min}(g_2,e_2)} \cdots p_n^{\text{min}(g_n,e_n)}\right) = \left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)$

$\implies \left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)^2$

$(a,b,c)^2 = \left(p_1^{\text{min}(e_1,f_1,g_1)}p_2^{\text{min}(e_2,f_2,g_2)} \cdots p_n^{\text{min}(e_n,f_n,g_n)}\right)^2 = \left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)^2$

$\therefore \mbox{RHS} = \frac{\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)^2}{\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)\left(p_1^{g_1}p_2^{g_2} \cdots p_n^{g_n}\right)^2} = \frac{1}{\left(p_1^{f_1}p_2^{f_2} \cdots p_n^{f_n}\right)} = \mbox{LHS}$

$\mbox{Q.E.D}$

TrueTears · « **Reply #500 on:** December 22, 2009, 11:57:53 pm »

Actually is that right? Since my whole argument was based on the assumption $e_n \ge f_n \ge g_n \ \forall \ n$ , I'm not sure if I can do that...

zzdfa · « **Reply #501 on:** December 23, 2009, 12:00:50 am »

my first thought: did you try using the fact that (a,b)=a*b/[a,b] before going through all that

a sometimes useful way of thinking:

gcd can be interpreted as the intersection of the prime factors and lcm can be interpreted as the union of the prime factors.

example:
pfactors of 96 are {2,2,2,2,2,3}
pfactors of 60 are {2,2,3,5}

intersection is {2,2,3}

so gcd is 2*2*3=12.

similar thing with lcm. the union of the pfactors of 96 and 60 is {2,2,2,2,2,3,5}, so lcm is 480.

using the above interpretation, [a,b]=a*b/(a,b) is just principle of inclusion-exclusion.

TrueTears · « **Reply #502 on:** December 23, 2009, 12:01:57 am »

Quote from: zzdfa on December 23, 2009, 12:00:50 am

my first thought: did you try using the fact that (a,b)=a*b/[a,b] before going through all that

lol I didn't even know that result

, how do you prove it?

zzdfa · « **Reply #503 on:** December 23, 2009, 12:10:02 am »

Quote from: TrueTears on December 22, 2009, 11:57:53 pm

Actually is that right? Since my whole argument was based on the assumption $e_n \ge f_n \ge g_n \ \forall \ n$ , I'm not sure if I can do that...

no that assumption was fine. are you sure you know what WLOG means?

\\

TrueTears · « **Reply #504 on:** December 23, 2009, 12:10:58 am »

Quote from: zzdfa on December 23, 2009, 12:00:50 am

my first thought: did you try using the fact that (a,b)=a*b/[a,b] before going through all that

a sometimes useful way of thinking:

gcd can be interpreted as the intersection of the prime factors and lcm can be interpreted as the union of the prime factors.

pfactors of 96 are {2,2,2,2,2,3}
pfactors of 60 are {2,2,3,5}

intersection is {2,3}

so gcd is 2*3=6.

similar thing with lcm.

using the above interpretation, [a,b]=a*b/(a,b) is just principle of inclusion-exclusion.

Wait isn't the intersection $\{2,2,3\}$ ?

Quote from: zzdfa on December 23, 2009, 12:10:02 am

Quote from: TrueTears on December 22, 2009, 11:57:53 pm
Actually is that right? Since my whole argument was based on the assumption $e_n \ge f_n \ge g_n \ \forall \ n$ , I'm not sure if I can do that...
no that assumption was fine. are you sure you know what WLOG means?

\\

Yeah I do, without loss of generality but I when I reread what I did I thought it was wrong.

zzdfa · « **Reply #505 on:** December 23, 2009, 12:12:03 am »

ahh yep youre right^^

lol i meant 'do you know what without loss of generality means' not 'do you know what WLOG stands for' :p

kamil9876 · « **Reply #506 on:** December 23, 2009, 12:14:53 am »

strictly speaking, you can assume that WLOG $e_i \ge f_i \ge g_i$ for some i, but not for all. However this proof can be executed just by focusing on one prime number, say p, rather than all of them. Notice also that the equation is symmetric in the variables proving it for one prime power is enough since the primes only 'interact' with themselves. (~~Another way to justify using only one prime power is to notice that gcd(x,y)*gcd(z,w)=gcd(xz,zw) if x and z are relatively prime; w and y are relatively prime, and likewise for lcm~~).

by request, my soln (probably the same):

let $a_1=p^A, b_1=p^B, c_1=p^C$ and assume WLOG that $A\leq B \leq C$

lcm(a,b,c)=max(A,B,C)=C
lcm(a,b)=B
lcm(a,c)=C
lcm(b,c)=C

gcd(a,b,c)=min(A,B,C)=A
gcd(a,b)=A
gcd(a,c)=A
gcd(b,c)=B

plugging these values in we see the equation is true as both sides become 1/B.

Now if we do this on all the individual 'pure prime powers' the equation is true, since p was arbitrary and we can always do the WLOG thing since the equation is symmetric, and so we can relabel as we like and it won't change the truth of the equation. Now you can multiply all these equations together to get one big equation, which changes it into the equation for a,b,c using the fact:

"gcd(x,y)*gcd(z,w)=gcd(xz,zw) if x and z are relatively prime; w and y are relatively prime, and likewise for lcm"

Notice that B is the middle number (again showing some nice symmetry

). So yeah, actually just do your big general approach, works best, and then split it into a product into many little products that involve only the single prime, and then just prove that for each of these products, you get the 'middle number' both for lcm and gcd. and yeah result easily follows from here. (this is ussually a good approach, to focus on single primes and then take the product of all the singles).

ie for clarity:

$RHS=\prod_{i=1}^n \frac{p_i^{2min(e_i, f_i, g_i)}}{p_i^{min(e_i,f_i)}p_i^{min(g_i,f_i)}p_i^{min(e_i,g_i)}}$
$=\prod_{i=1}^n \frac{1}{p_i^B_i}$

where $B_i$ is the 'middle number' for $e_i, f_i, g_i$ .

And same thing for LHS.

TrueTears · « **Reply #507 on:** December 23, 2009, 12:18:29 am »

Quote from: zzdfa on December 23, 2009, 12:12:03 am

ahh yep youre right^^

lol i meant 'do you know what without loss of generality means' not 'do you know what WLOG stands for' :p

lol haha, it means, you are not losing any information or falsifying anything when you make that assumption right?

zzdfa · « **Reply #508 on:** December 23, 2009, 12:22:08 am »

Quote from: kamil9876 on December 23, 2009, 12:14:53 am

strictly speaking, you can assume that WLOG $e_i \ge f_i \ge g_i$ for some i, but not for all. However this proof can be executed just by focusing on one prime number, say p, rather than all of them. Notice also that the equation is symmetric in the variables proving it for one prime power is enough since the primes only 'interact' with themselves. (Another way to justify using only one prime power is to notice that gcd(x,y)*gcd(z,w)=gcd(xz,zw) if x and z are relatively prime; w and y are relatively prime, and likewise for lcm).

doesnt he only assume it for e_n f_n and g_n though? so the assumption is valid right?/

kamil9876 · « **Reply #509 on:** December 23, 2009, 12:36:52 am »

that's what he preached, but not what he practiced.

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 147055 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

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Recent Posts

User:
Password: