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

TrueTears · « **Reply #480 on:** December 21, 2009, 08:21:38 pm »

Hey can someone show me how to prove the FTA?

humph · « **Reply #481 on:** December 21, 2009, 08:44:31 pm »

The proof(s) on Wikipedia are very "natural": see http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
I also seem to remember Hardy and Wright's book "An Introduction to the Theory of Numbers" having quite a few proofs (and it's a great book too, albeit quite outdated).

TrueTears · « **Reply #482 on:** December 21, 2009, 08:45:29 pm »

Cool, thanks humph checking it out now

kamil9876 · « **Reply #483 on:** December 21, 2009, 08:50:12 pm »

the most crucial part of the step is to prove Euclid's lemma: if p|ab then p|a or p|b. (p is prime).

Most textbook approach is with bezout's identity, but Gauss had a different proof in his Disquisitiones Arithmeticae which was posted in the first page of this thread

TrueTears · « **Reply #484 on:** December 22, 2009, 01:24:47 am »

I like the following proof the best

Assume that there are numbers which can not be expressed as a product of primes. Let the smallest possible number of this kind be $m$ .

$m$ can not be $1$ since $1$ is neither composite nor prime. $m$ can not be prime since the PPF of a prime number is just itself. Thus $m$ must be a composite number.

Let the composition of $m = ab$ where $\{a,b\} < m$

Since $m$ was the smallest number that can not be expressed as a product of primes, this means $a$ and $b$ can be expressed as a product of primes and consequently we get $m = ab$ where $a$ and $b$ can be both expressed as primes. Contradiction!

Thus $m$ can also be expressed as a product of primes.

Lemma 1: If $p$ is a prime and $p|a_1a_2a_3 \cdots a_n$ then $p|a_i$ for some $i$ .

Lemma 2: If $p$ and $q$ are primes and $e$ is a natural number and $p|q^e$ then $p=q$ .

Let's assume that for some number $k$ that there are $2$ (at least) ways of expressing its PPF.

$\therefore k = p_1^{f_1}p_2^{f_2}p_3^{f_3} \cdots p_n^{f_n} = q_1^{e_1}q_2^{e_2}q_3^{e_3} \cdots q_m^{e_m}$

Clearly for all $\mbox{n}$ , $p_n|k$

$\implies p_n| q_1^{e_1}q_2^{e_2}q_3^{e_3} \cdots q_m^{e_m}$

By Lemma 1 $p_n|q_m^{e_m}$ for any $m$ .

By Lemma 2 $p_n=q_m$

This means that for all $\mbox{n}$ and all $m$ there are values of $p$ which equals to those of $q$ . For example, $p_3$ could equal to $q_5$ , or $p_6=q_3$ etc. This also means we have created a bijection between $p$ and $q$ such that $n = m$ .

Therefore if the number $k$ has $2$ PPF's then the prime number 'base' will be exactly the same, the only different would be in the powers, namely $f_n$ and $e_m$ .

Now since each $p_n$ has a corespondent equivalent $q_m$ we can rewrite $k$ as:

$p_1^{f_1}p_2^{f_2}p_3^{f_3} \cdots p_n^{f_n} = p_1^{e_1}p_2^{e_2}p_3^{e_3} \cdots p_n^{e_n}$

$p_1^{f_1-e_1}p_2^{f_2}p_3^{f_3} \cdots p_n^{f_n} = p_2^{e_2}p_3^{e_3} \cdots p_n^{e_n}$

$\mbox{LHS}|p_1$ however $\mbox{RHS}$ can not be divided by $p_1$ unless for some $2 \le j \le n$ such that $p_j = p_1$

But since $p_1 \neq p_2 \neq p_3 \neq \cdots \neq p_n$ we have a contradiction!

Therefore FTA is proven to be true.

TrueTears · « **Reply #485 on:** December 22, 2009, 01:28:47 am »

Proving the uniqueness and understanding the process took me the whole night, it drove me crazy z.z.z.

kamil9876 · « **Reply #486 on:** December 22, 2009, 01:40:49 am »

yeah, just remember that a few things were assumed without loss of generality. example: you assumed that $f_1>e_1$ since we knew that some two corresponding powers must be non-equal. But yeah it's quite obvious to see how important Euclid's lemma was and I think its proof is the most non-trivial part.

TrueTears · « **Reply #487 on:** December 22, 2009, 01:41:59 am »

Yeap, very powerful

humph · « **Reply #488 on:** December 22, 2009, 01:58:15 am »

The Fundamental Theorem of Arithmetic is pretty damn important on its own. For example, it is equivalent to the fact that
$\sum^{\infty}_{n=1}{\frac{1}{n^s}} = \prod_{p}{\frac{1}{1 - p^{-s}}},$
where the product is taken over all primes $p$ , and $s$ is some complex variable with real part greater than 1. This is the Euler product for the Riemann zeta function, famous for its central role in the unsolved Riemann hypothesis.
More interestingly, the fact that the meromorphic extension of the Riemann zeta function to the open half-plane $\Re(s) > 0$ has no zeroes along the line $\Re(s) = 1$ is equivalent to the Prime Number Theorem
$\pi(x) \sim \frac{x}{\log x},$
where $\pi(x)$ is the function that counts how many primes are lesser than or equal to $x$ ; this is perhaps the central result of the field of multiplicative number theory.

TrueTears · « **Reply #489 on:** December 22, 2009, 03:30:09 am »

Anyways my first set of fun number theory questions~!

~~1. Prove that the fraction $\frac{n^3+2n}{n^4+3n^2+1}$ is in lowest terms for every positive integer $\mbox{n}$~~

~~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)}$~~

~~3. Prove that consecutive Fibonacci numbers are always relatively prime.~~

4. Show that $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ can never be an integer. (I'm thinking of showing $\lim_{n \to \infty}\sum_{k=2}^{n}\frac{1}{k}$ diverges to a value... or something along those lines, probs wrong heh)

TrueTears · « **Reply #490 on:** December 22, 2009, 12:28:40 pm »

Actually 4 is just the harmonic series, how do you show that it diverges to a non-integer value?

kamil9876 · « **Reply #491 on:** December 22, 2009, 01:04:29 pm »

I remember posting 4 as a challenge once lol

Suppose the sum of the first n terms is an integer m, multiply both sides by n!:

$m*n!=2*3*4..n + 1*3*4..n + 1*2*4...n + .... (n-1)!$

Now consider the biggest prime number p, in the sequence 1,2,3...n.

m*n! is divisible by p. All the terms on the RHS are divisible by p except for the pth term. This is because the kth term is a product of all numbers between 1 and n except for k. Therefore if $k\neq p$ the kth term is divisible by p. If $k=p$ then the kth term is missing p. But no other factor of this term is divisible by p since they are made of prime factors smaller than p. Denote the kth term as $t_k$ :

$t_p=m*n! - t_1 - t_2... - t_{p-1} - t_{p+1}...-t_n$

So the LHS is not divisible by p, but the RHS is since it is a linear combination of multiples of p, a contradiction.

edit: actually, I think there is a flaw with this proof since it assumes that for every integer n, there exists a prime p such that p<n<2p, and i do not know if this is true.

However an alternate proof is this: multiply both sides by the biggest power of 2(call this $2^k$ ), then multiply it by the biggest power of 3, then multiply it by the biggest power of 5 etc. eventually we get some equation like in the previous attempt at a proof, that is one that involves only integers. Now the $t_{2^k}$ term is not an even number, but the rest must be and so we get a contradiction since we get:

even numer=sum of even numbers + odd number.

1.) $n^3+2n=n(n^2+2)$ , $n^4+3n^2+1=(n^2+2)(n^2+1)-1$

any prime that divides the numerator must divide either n or $n^2+2$ .

Suppose p divides n. Then:

$\frac{n^4+3n^2+1}{p}=\frac{n^4+3n^2}{p} + \frac{1}{p} \notin \mathbb{N}$ hence p does not divide the denominator.

Suppose p divides $n^2+2$ :
$<br />\frac{n^4+3n^2+1}{p}=\frac{(n^2+2)(n^2+1)}{p} - \frac{1}{p} \notin \mathbb{N}$ hence p does not divide the numerator.

Therefore no prime can divide both the numerator and denominator. Hence they are relatively prime and so in lowest terms.

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

TrueTears · « **Reply #492 on:** December 22, 2009, 03:11:46 pm »

Thanks kamil for Q 4. I actually thought of another method, but I'm kind stuck at the end.

$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ is just the Zeta function $\zeta (1)$

Consider the sequence $1 + \frac{1}{4} + \frac{1}{4} + \cdots + \frac{1}{4}$

Clearly $\frac{1}{3} + \frac{1}{4} \ge \frac{1}{4} + \frac{1}{4}$

$\implies \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} \ge \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}$

So clearly the sum of $\zeta (1) \ge 1 + \frac{1}{4} + \frac{1}{4} + \cdots + \frac{1}{4}$

However $1 + \frac{1}{4} + \frac{1}{4} + \cdots + \frac{1}{4}$ clearly diverges, which means $\zeta (1)$ diverges as well.

But how can I relate this to the question?

TrueTears · « **Reply #493 on:** December 22, 2009, 04:04:36 pm »

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

I remember posting 4 as a challenge once lol

Suppose the sum of the first n terms is an integer m, multiply both sides by n!:

$m*n!=2*3*4..n + 1*3*4..n + 1*2*4...n + .... (n-1)!$

Now consider the biggest prime number p, in the sequence 1,2,3...n.

m*n! is divisible by p. All the terms on the RHS are divisible by p except for the pth term. This is because the kth term is a product of all numbers between 1 and n except for k. Therefore if $k\neq p$ the kth term is divisible by p. If $k=p$ then the kth term is missing p. But no other factor of this term is divisible by p since they are made of prime factors smaller than p. Denote the kth term as $t_k$ :

$t_p=m*n! - t_1 - t_2... - t_{p-1} - t_{p+1}...-t_n$

So the LHS is not divisible by p, but the RHS is since it is a linear combination of multiples of p, a contradiction.

edit: actually, I think there is a flaw with this proof since it assumes that for every integer n, there exists a prime p such that p<n<2p, and i do not know if this is true.

Actually if you use Bertrand's postulate for any natural $\mbox{n}$ at least one prime exists $n < p < 2n$ .

Now set $n = \frac{n}{2}$

$\frac{n}{2} < p < n$

Now assume we pick the largest $p$ within this interval.

$\implies n < 2p < 2n$

$\therefore p < n < 2p$

kamil9876 · « **Reply #494 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

Search the forums now!

We have moved!

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

TrueTears

Re: TT's Maths Thread

humph

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

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

Recent Posts

User:
Password: