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

TrueTears · « **Reply #525 on:** December 24, 2009, 09:53:14 pm »

Quote from: kamil9876 on December 24, 2009, 09:26:21 pm

yeah. let by that logic, a generalisation would be sd(ab)> a * sd(b). where sd is sum of divisors.

Ah okay, so the 15k acts like a lower bound? Thus it doesn't matter how much more we add to it since it is larger than 12k anyway

TrueTears · « **Reply #526 on:** December 24, 2009, 10:44:53 pm »

Quote

4. Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression.

The arithmetic progression is in the form $a_n = a_1 + (n-1)d$

Let the three primes be $x,y,z$ .

WLOG assume $x>y>z$

Now assume $x,y,z$ are three terms of an arithmetic progression and $z^{\frac{1}{3}}$ is the first term of the progression.

$y^{\frac{1}{3}} = z^{\frac{1}{3}} + kd \cdots [1]$

$x^{\frac{1}{3}} = z^{\frac{1}{3}} + md \cdots [2]$

Where $\{k,m\} \in \mathbb{N}$ and $d$ is the common difference.

$[1] \times m \implies my^{\frac{1}{3}} = mz^{\frac{1}{3}} + mkd$

$[2] \times k \implies kx^{\frac{1}{3}} = kz^{\frac{1}{3}} + mkd$

$[1] \times m - [2] \times k \implies my^{\frac{1}{3}} - kx^{\frac{1}{3}} = (m-k)z^{\frac{1}{3}}$

$\left(my^{\frac{1}{3}} - kx^{\frac{1}{3}}\right)^3 = \left((m-k)z^{\frac{1}{3}}\right)^3$

$m^3y - k^3x - 3my^{\frac{1}{3}}kx^{\frac{1}{3}}\left(my^{\frac{1}{3}} - kx^{\frac{1}{3}}\right) = (m-k)^3z$

$m^3y - k^3x - 3my^{\frac{1}{3}}kx^{\frac{1}{3}}\left((m-k)z^{\frac{1}{3}}\right) = (m-k)^3z$

$3my^{\frac{1}{3}}kx^{\frac{1}{3}}\left((m-k)z^{\frac{1}{3}}\right) = -(m-k)^3z + m^3y - k^3x$

$y^{\frac{1}{3}}x^{\frac{1}{3}}z^{\frac{1}{3}} = \frac{-(m-k)^3z + m^3y - k^3x}{3mk(m-k)}$

$(yxz)^{\frac{1}{3}} = \frac{-(m-k)^3z + m^3y - k^3x}{3mk(m-k)}$

Since $x,y,z$ are all distinct primes the cube root of the product of any $3$ primes is irrational, however the $\mbox{RHS}$ is clearly rational.

Thus contradiction!

But... how do you prove the product of 3 primes is never a cube?

kamil9876 · « **Reply #527 on:** December 24, 2009, 11:01:38 pm »

u might wanna do the m=k case seperately, so that your RHS really is rational and not undefined. (ie work from your third last line, since you didn't do any division before that point, and the result follows easily from it)

Quote

But... how do you prove the product of 3 primes is never a cube?

$n^3=(\prod p_i^{e_i})^3=\prod p_i^{3e_i}$

Thus all cubes have their prime powers as multiples of 3 (in fact, k is a cube iff all prime powers are multiples of 3).

But $xyz=(x^1)(y^1)(z^1)$ hence not multiples of 3.

TrueTears · « **Reply #528 on:** December 24, 2009, 11:03:02 pm »

Quote from: kamil9876 on December 24, 2009, 11:01:38 pm

u might wanna do the m=k case seperately, so that your RHS really is rational and not undefined. (ie work from your third last line, since you didn't do any division before that point, and the result follows easily from it)

Quote
But... how do you prove the product of 3 primes is never a cube?

$n^3=(\prod p_i^{e_i})^3=\prod p_i^{3e_i}$

Thus all cubes have their prime powers as multiples of 3 (in fact, k is a cube iff all prime powers are multiples of 3).

But $xyz=(x^1)(y^1)(z^1)$ hence not multiples of 3.

How can $m=k$ ? They are 3 distinct primes.

Ahh easy proof, thanks

TrueTears · « **Reply #529 on:** December 24, 2009, 11:11:31 pm »

Okay some challenge ones to finish off

1. Prove that any integer greater than or equal to 7 can be written as a sum of 2 relatively prime integers, both greater than 1. For example, 22 and 15 are relatively prime, and thus $37=22+15$ represents the number 37 in the desired way.

2. Since $24=3+5+7+9$ , the number 24 can be written as the sum of at least two consecutive odd positive integers. Can 2005 be written as the sum of at least 2 consecutive odd positive integers? What about 2006?

~~3. The sequence $a_1,a_2, \cdots$ of natural numbers satisfies $\text{GCD}(a_i,a_j) = \text{GCD}(i,j)$ for all $i \neq j$ . Prove that $a_i=i \ \forall \ i$~~

4. Let $r \in \mathbb{N}$ . Show that $\binom{p^r}{k}$ is a multiple of $p$ for $0 < k < p^r$ .

kamil9876 · « **Reply #530 on:** December 24, 2009, 11:33:47 pm »

1.)

say we want to do this for n.

case 1: n is odd

then n-2 and 2 are appropriate summands, clearly relatively prime since n-2 is odd.

case 2i: n=2k with k even

k+1 and k-1 are appropriate summands since no d>1 divides them both. Proof: suppose k+1=ad, k-1=bd. Then:

k+1-(k-1)=ad-bd
2=d(a-b)

hence the only possibility is d=2, d is a divisor of k+1 (an odd number), so it cannot be 2.

case2ii: n=2k, with k odd:

then k-2 and k+2 are our desired summands. Suppose that for some d>1, ad=k+2, bd=k-2

k+2-(k-2)=d(a-b)
4=d(a-b)

hence we're left with the possiblity that d is 2 or 4. But it cannot be these since d is a factor of an odd number, so it has to be odd.

These cases exhuast all possibilities for n.

kamil9876 · « **Reply #531 on:** December 24, 2009, 11:37:07 pm »

a good way to experiment/play with number 3 is to try to prove specific cases to see what techinques will work. e.g: try to prove $a_1=1$ , then try to prove $a_2=2$ etc. and try to refine your method for some more general cases.

TrueTears · « **Reply #532 on:** December 24, 2009, 11:37:52 pm »

Quote from: kamil9876 on December 24, 2009, 11:37:07 pm

a good way to experiment/play with number 3 is to try to prove specific cases to see what techinques will work. e.g: try to prove $a_1=1$ , then try to prove $a_2=2$ etc. and try to refine your method for some more general cases.

Yeah, that's actually what I am attempting atm

TrueTears · « **Reply #533 on:** December 25, 2009, 09:49:15 pm »

Quote

3. The sequence $a_1,a_2, \cdots$ of natural numbers satisfies $\text{GCD}(a_i,a_j) = \text{GCD}(i,j)$ for all $i \neq j$ . Prove that $a_i=i \ \forall \ i$

Finally I can put an end to this question, it's been driving me nuts!

First assume $a_i \neq i$

Therefore for some $i$ , let's call it $m$ , $a_m \neq m$

$\implies (a_m, a_{2m}) = (m,2m) = m$

$\implies \frac{a_m}{m} = k$ for some $k$

$\therefore a_m = km$

Now $(a_{km}, a_{2km}) = (km,2km) = km$

$\therefore km | a_{km} \implies a_m | a_{km}$

$\implies (a_m, a_{km}) = a_m = km$

But $(a_m, a_{km}) = (m, km) = m$ Contradiction!

Thus $a_m = m$ so $a_i = i \ \blacksquare$

kamil9876 · « **Reply #534 on:** December 25, 2009, 09:51:45 pm »

nice one

even simpler than mine

TrueTears · « **Reply #535 on:** December 25, 2009, 10:00:00 pm »

omg i feel like a rock has been lifted off me, this question was driving me insane seriously.

TrueTears · « **Reply #536 on:** December 26, 2009, 02:38:31 am »

Quote from: TrueTears on December 24, 2009, 11:11:31 pm

2. Since $24=3+5+7+9$ , the number 24 can be written as the sum of at least two consecutive odd positive integers. Can 2005 be written as the sum of at least 2 consecutive odd positive integers? What about 2006?

Let $S$ be the sum of a sequence of consecutive odd numbers.

$S = (2k+1)+(2k+3)+(2k+5)+ \cdots + (2k+2n-1)$ where $k \ge 0$ and $n \ge 2$

$S = \frac{n}{2}\left(2k+1+(2k+2n-1)\right) = \frac{n}{2}\left(4k+2n)\right) = n(2k+n)$

The PPF of $2005 = (401)(5)$

$\implies (401)(5) = n(2k+n)$

$\implies n = 5$

$\therefore 2k+5 = 401 \implies k = 198$

Subbing that back into our original expression for $S$ yields:

$S = (2(198)+1)+(2(198)+3)+(2(198)+5)+(2(198)+7)+(2(198)+9) = 2005$

$2006$ won't work because either $\text{n}$ and $(2k+n)$ are both odd or both even, but $2006 = 2 \times 1003$ , ie $\text{n}$ is even and $(2k+n)$ is odd. Contradiction!

kamil9876 · « **Reply #537 on:** December 27, 2009, 12:49:31 am »

Quote from: TrueTears on December 24, 2009, 11:11:31 pm

4. Let $r \in \mathbb{N}$ . Show that $\binom{p^r}{k}$ is a multiple of $p$ for $0 < k < p^r$ .

the thing is:

$\frac{p^r(p^{r}-1)....(p^{r}-k+1)}{1*2*3....*k}$

Define the sequences

$A=(p^r, p^r-1..., p^r-k+1)$

$B=(1,2,3...k)$

now both sequences are strings of consecutive numbers.

Lemma1:

in a sequence of any $k$ consecutive numbers, the the number of multiples of $a$ is either $\lfloor\frac{k}{a}\rfloor$ or $\lceil \frac{k}{a} \rceil$

Proof: exercise

Lemma2: if the sequence from lemma1 has a multiples of $a$ as its first element, then the number of multiples of $a$ is exactly $\lceil \frac{k}{a} \rceil$ . If the sequence is {1,2,3....k} then the number of multiples of a is exactly $\lfloor \frac{k}{a} \rfloor$

Proof: more exercise

Lemma3: The two lemmas above imply that the number of multiples of $p^i$ in A is greater than or equal to the number of multiples of $p^i$ in B.

Now from each multiple of p, factor out one p and u get:

$\frac{p^{a_1}}{p^{b_1}} * (... )$

where $a_1 \geq b_1$ by lemma3.

The thing inside the bracket has a new numerator and a new denominator. So we have two new sequences $A_1$ and $B_1$ where these sequences are the previous ones with the power of p lowered by 1 in each multiple of p. The number of multiples of $p$ in $A_1$ is precisely equal to the number of multiples of $p^2$ in $A$ , and likewise for $B_1$ and $B$ . Therefore if we do this process again to get:

$\frac{p^{a_1}}{p^{b_1}}\frac{p^{a_2}}{p^{b_2}} * (... )$

with $a_2\geq b_2$ by lemma 3. If we keep doing this process we eventually get to:

$\frac{p^{a_1}}{p^{b_1}}\frac{p^{a_2}}{p^{b_2}}...\frac{p^{a_r}}{p^{b_r}} * (... )$

where in this case $a_r=1, b_r=0$ since there is only one multiple of $p^r$ in $A$ , and no multiples of $p^r$ in $B$ .

TrueTears · « **Reply #538 on:** December 27, 2009, 02:31:21 pm »

Quote from: TrueTears on December 24, 2009, 11:11:31 pm

4. Let $r \in \mathbb{N}$ . Show that $\binom{p^r}{k}$ is a multiple of $p$ for $0 < k < p^r$ .

$\binom{p^r}{k} = \frac{(p^r-k+1)(p^r-k+2) \cdots (p^r-2)(p^r-1)p^r}{(k)(k-1)(k-2) \cdots (3)(2)(1)}$

If $k-1$ has factors of $p$ then $k-1 = qp^s$ where $q$ is some constant and $s<r$ .

Looking at the factor $(p^r-(k-1))$ in the numerator, if we paired up $(p^r-(k-1))$ and $(k-1)$ we would have $\frac{(p^r-(k-1))}{k-1}$ .

$\implies \frac{p^r}{k-1} - \frac{k-1}{k-1} = \frac{p^r}{qp^s}-1 = \frac{p^{r-s}}{q}-1$

If $k-2$ had factors of $p$ then $k-2 = cp^w$ where $c$ is some constant and $w<r$

$\implies \frac{p^r-(k-2)}{k-2} = \frac{p^{r-w}}{c} - 1$

There could be more factors of $p$ in the denominator but WLOG let's say these $2$ are the only ones.

Then we would have $\binom{p^r}{k} = \frac{\left(\frac{p^{r-s}}{q}-1\right)\left(\frac{p^{r-w}}{c} - 1\right) \cdots (p^r-2)(p^r-1)(p^r)}{(k) \cdots (3)(2)(1)}$

$\implies \frac{\left(\frac{p^{r-s}p^{r-w}}{qc} - \frac{p^{r-s}}{q} - \frac{p^{r-w}}{c} + 1\right) \cdots (p^r-2)(p^r-1)(p^r)}{(k) \cdots (3)(2)(1)}$

$\implies \frac{p^{r-s}\left(\frac{p^{r-w}}{qc} - \frac{1}{q} - \frac{p^{r-w}}{cp^{r-s}} + \frac{1}{p^{r-s}}\right) \cdots (p^r-2)(p^r-1)(p^r)}{(k) \cdots (3)(2)(1)}$

Therefore it is a multiple of $p$ .

If there were more "pairs" then we could always factor out a $p^{i}$ where $i < r$

TrueTears · « **Reply #539 on:** December 27, 2009, 11:11:20 pm »

1. Prove that $\text{GCD}(a_1, .. . ,a_k) = \text{GCD}(\text{GCD}(a_1, a_2), a_3, . .. ,a_k)$

How to prove this using Euclid's Algorithm?

~~2. Show that $c|a$ and $c|b$ iff $c|(a,b)$~~

Search the forums now!

We have moved!

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

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

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Recent Posts

User:
Password: