ATAR Notes: Forum

VCE Stuff => VCE Mathematics => VCE Mathematics/Science/Technology => VCE Subjects + Help => VCE Specialist Mathematics => Topic started by: noname on February 19, 2012, 12:16:40 pm

Title: need some help on essentials ch 3 review question
Post by: noname on February 19, 2012, 12:16:40 pm: (http://i.imgur.com/KuCYU.png)

Hey everyone,
I just need some help with part c) in the image above.

Any help is greatly appreciated. :D
Title: Re: need some help on essentials ch 3 review question
Post by: noname on February 19, 2012, 12:25:49 pm: I just realised I need help with part d) as well.
(http://i.imgur.com/6vZHO.png)

Thanks in advance.
Title: Re: need some help on essentials ch 3 review question
Post by: paulsterio on February 19, 2012, 12:40:44 pm: I don't know why you'd get this on VCE Maths, but it's number theory.
Firstly, I'm going to call the Highest Common Factor the Greatest Common Divisor (gcd) from now on. It's more "correct" in some ways. Anyway,

(http://i39.tinypic.com/r7szr5.jpg)
Title: Re: need some help on essentials ch 3 review question
Post by: TrueTears on February 19, 2012, 12:51:35 pm: WDF? you guys actually learn some number theory in general maths?

SICK AS!

part b) of the question is one of the most famous theorems, called the fundamental theorem of arithmetic (http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic), not only is it a good applicable theorem, but the proof is also very cool!

Here's a cool proof I did ages ago from when I started number theory.

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!

part c) of the question is a corollary of the fundamental theorem of arithmetic (http://en.wikipedia.org/wiki/Least_common_multiple#Reduction_by_the_greatest_common_divisor)
Title: Re: need some help on essentials ch 3 review question
Post by: noname on February 19, 2012, 01:27:41 pm: The teacher hasn't actually taught us anything about "number theory" or whatever. In fact, I do not even know what all those symbols you guys used mean LOL. This question was just a part of the chapter review, so ... yeah.. :|

Well how would you go about doing part d? I'm assuming it's more algebraic? Hopefully ? haha
Title: Re: need some help on essentials ch 3 review question
Post by: paulsterio on February 19, 2012, 05:27:29 pm: Quote from: noname on February 19, 2012, 01:27:41 pm
The teacher hasn't actually taught us anything about "number theory" or whatever. In fact, I do not even know what all those symbols you guys used mean LOL. This question was just a part of the chapter review, so ... yeah.. :|

Well how would you go about doing part d? I'm assuming it's more algebraic? Hopefully ? haha

You won't encounter anything like that in GMA, highly doubt it, Essential exercises are usually a load of bs in my opinion :P

Btw, I'll have a look at d) later when I've finished eating if it hasn't been done, but LOL! you're hoping that it's MORE algebraic? :\ Don't you mean less - considering you've gotten sick of the symbols? :P
Title: Re: need some help on essentials ch 3 review question
Post by: pi on February 19, 2012, 05:40:19 pm: Quote from: noname on February 19, 2012, 01:27:41 pm
The teacher hasn't actually taught us anything about "number theory" or whatever. In fact, I do not even know what all those symbols you guys used mean LOL. This question was just a part of the chapter review, so ... yeah.. :|

Don't worry, I don't understand it either :P
Title: Re: need some help on essentials ch 3 review question
Post by: noname on February 20, 2012, 12:05:00 am: Quote from: paulsterio on February 19, 2012, 05:27:29 pm
Quote from: noname on February 19, 2012, 01:27:41 pm
The teacher hasn't actually taught us anything about "number theory" or whatever. In fact, I do not even know what all those symbols you guys used mean LOL. This question was just a part of the chapter review, so ... yeah.. :|

Well how would you go about doing part d? I'm assuming it's more algebraic? Hopefully ? haha

You won't encounter anything like that in GMA, highly doubt it, Essential exercises are usually a load of bs in my opinion :P

Btw, I'll have a look at d) later when I've finished eating if it hasn't been done, but LOL! you're hoping that it's MORE algebraic? :\ Don't you mean less - considering you've gotten sick of the symbols? :P

WOOPS YEAH LESS LOL

Quote from: Rohitpi on February 19, 2012, 05:40:19 pm
Quote from: noname on February 19, 2012, 01:27:41 pm
The teacher hasn't actually taught us anything about "number theory" or whatever. In fact, I do not even know what all those symbols you guys used mean LOL. This question was just a part of the chapter review, so ... yeah.. :|

Don't worry, I don't understand it either :P

Cool I'm on the same level as a 99.35 getter LOL :D
Title: Re: need some help on essentials ch 3 review question
Post by: Planck's constant on February 20, 2012, 05:27:30 pm: Quote from: noname on February 19, 2012, 12:25:49 pm
I just realised I need help with part d) as well.
(http://i.imgur.com/6vZHO.png)

Thanks in advance.

This is one answer for (i):

3470/5 = 694
3472/7 = 496
3474/9 = 386
3476/11 = 316

For (i) easy enough to get this result if you approach the problem as one of those intermediate AMC problems

* The first number is even and a multiple of 5 therefore it must be of the form 10a
* The second number = 10a + 2 but also divisble by 7, but it ends in 2 so it must be of the form 7(6+10b) ... as 6*7 = 42 minus 2 = multiple of 10
* The third number is 10a + 4, but also multiple of 9 etc etc ... of the form 9(6+10c)
* The fourth number is 10a + 6 but also 11(6+10d) etc

Stuff around a bit etc

I throw the challenge at TrueTears for either a 'hence' or other solution :)