The importance of primes Log Out | Topics | Search
Moderators | Register | Edit Profile

Ask NRICH » Archive 2010-2011 » Please Explain » The importance of primes « Previous Next »

Author Message
Turnip
Regular poster

Post Number: 73
Posted on Thursday, 07 July, 2011 - 10:03 am:   

Hi

I've been reading on purplemath that 'you most often want to find the ''prime factorisation" of a number' http://www.purplemath.com/modules/factnumb.htm . This is something I keep coming across and I've seen things where people draw prime number tree etc. Trouble is I've been factoring in algebra, solving equations, giving answers in surds etc for months now and I've never been thinking of it as 'prime' factorisation? Am I missing a trick here?? When is prime factorisation used???
Daniel Fretwell
Veteran poster

Post Number: 1419
Posted on Thursday, 07 July, 2011 - 11:14 am:   

Well as far as you should be concerned, factorising polynomials and factorising numbers are two different things.

The prime factorisation of a whole number is an important thing. It can be proved that every whole number bigger than 2 can be factorised into a product of powers of prime numbers...and this can be done in a unique way!

The fact that this exists lets us do lots of things. Sometimes it helps us to solve equations where we only want whole number solutions. These are called Diophantine equations.

It also lets us prove things like "if a,b are coprime and are such that ab is a cube number then both a and b are cube numbers too".

There are probably other uses of prime factorisation that I have missed, I am sure other people will come up with some nicer examples.
Daniel Fretwell
Veteran poster

Post Number: 1420
Posted on Thursday, 07 July, 2011 - 11:16 am:   

Another good use of the prime factorisation is that it gives us a nice way to find the highest common factor and the least common multiple of two numbers.
Turnip
Regular poster

Post Number: 74
Posted on Thursday, 07 July, 2011 - 12:07 pm:   

Hi Daniel, can you expand upon this please? Or anyone else?? What's the process involved?
Daniel Fretwell
Veteran poster

Post Number: 1422
Posted on Thursday, 07 July, 2011 - 05:35 pm:   

What do you want to know about?

The easy thing to do in maths is to place things in "method boxes". But not all things in maths are of the form "you do this then you do that...", sometimes we have to be creative and a bit clever in what we use and how.

The prime factorisation of an integer has just turned out to be a useful tool throughout the history of maths in solving many problems.

So for the result I mentioned above we might think "ok so lets write [inline]a[/inline] and [inline]b[/inline] in terms of prime factorisations":

[inline]a = p_1^{e_1}p_2^{e_2} ... p_n^{e_n}[/inline]

[inline]b = q_1^{f_1}q_2^{f_2} ... q_m^{f_m}[/inline]

So that [inline]ab = p_1^{e_1}p_2^{e_2} ... p_n^{e_n}q_1^{f_1}q_2^{f_2} ... q_m^{f_m}[/inline]. Now [inline]a[/inline] and [inline]b[/inline] are coprime so they share no prime factors, in other words none of the [inline]p_i[/inline]'s equal any of the [inline]q_i[/inline]'s.

Now [inline]ab[/inline] is a cube number so all of the powers of "different primes" in the above factorisation of [inline]ab[/inline] must be divisible by 3. So [inline]e_1, e_2, ..., e_n, f_1, f_2, ..., f_m[/inline] are all divisible by 3. But this means that [inline]a[/inline] and [inline]b[/inline] themselves must be cube numbers.

(Of course there is a flaw in this, we assumed that both [inline]a,b > 1[/inline] in order to have the factorisation but in the case where one of them equal 1 or 0, it is obvious that the result holds).
Turnip
Regular poster

Post Number: 75
Posted on Thursday, 07 July, 2011 - 05:46 pm:   

Even more basic than that... What's the method for finding highest common factor or least common multiple using primes? I think there's a technique I'm missing rather than using 'times tables' to find LCM etc??
Daniel Fretwell
Veteran poster

Post Number: 1423
Posted on Thursday, 07 July, 2011 - 06:06 pm:   

Lets do an example.

Let our two integers be 18 and 12.

Lets express these two numbers in their unique prime factorisations:

[inline]18 = 2\times 9 = 2\times 3^2[/inline]
[inline]12 = 3\times 4 = 2^2 \times 3[/inline]

Now the highest common divisor is by definition the highest number that divides both of these numbers. Now if we consider the prime factorisation of the highest common factor (assuming it isnt 1) then it can only contain 2's or 3's (since only 2 and 3 appears in both of the factorisations above).

The highest power of 2 allowed in the factorisation of the HCF is 1 (since this is the smallest power of 2 in the two factorisations above, if we allowed a higher power of 2 then the resulting number wouldnt divide 18).

Similarly, the highest power we can allow for 3 in the factorisation of the HCF is 1 because this is the smallest power of 3 appearing above (any higher and this number wouldnt divide 12).

So HCF[inline](18,12) = 2^1 \times 3^1 = 6[/inline] as expected.

As for the LCM, we do like above but now look at the highest powers that appear (the reasoning is similar). So the biggest power of 2 appearing is 2 and the biggest power of 3 appearing is 2, thus LCM[inline](18,12) = 2^2 \times 3^2 = 36[/inline] as expected.
Turnip
Frequent poster

Post Number: 76
Posted on Thursday, 07 July, 2011 - 09:26 pm:   

Dan your the man! What a great explanation.

Thanks
patfla
New poster

Post Number: 1
Posted on Saturday, 23 July, 2011 - 08:42 pm:   

Non-mathematician but well educated layman who's long been interested in math.

A title like "the importance of primes" catches my attention immediately since it's something I've studied and thought about for some time.

Primes most recently came up in an "In Our Time" broadcast with Melvyn Bragg the host (that's perhaps an American term) and, among others, Marcus du Sautoy, a professor of mathematics at Oxford, among the guests. du Sautoy's name seems to pop up frequently. In addition to several appearances on "In Our Time", he has a number of books in a genre I call "science/math for the educated layperson." which, interestingly, has become a fairly noticeable publishing market.

In particular, my feeling is that when professional mathematicians discuss primes they never (at least in my experience) give the 'real' reason for the importance of primes. I may be wrong in either claim.

The real reason (which I want to check in this post) has to do with the Fundamental Theorem of Arithmetic which says the same as above which is that every non-prime integer > 1 can be expressed as a unique factorization of primes. That it's "fundamental" and has to do with immediately recognizable "arithmetic" should alert almost any educated person to its importance.

So what is this saying (according to me)? Most people would think of the integers as fundamental. They're the building blocks of arithmetic - right? Well - no. The Fundamental Theory of Arithmetic says that the integers can be _built_ out of the primes.

That is, you (or say God) could start with just the primes - which appear not to be orderly - and build the integers which most people consider to be very orderly.

And so the integers are derived, and not fundamental. The primes are more elemental which is OK so far but what's bewildering is that as much as mathematicians has tried to determine some sequence, pattern or structure to the primes, they've largely failed.

2, 3, 5, 7, 11, 13, 17, etc - no function will produce this sequence. However, so much as putting it that way is probably a contradiction.

Actually the attempts have been completely unsuccessful. For example, there's the Riemann conjecture, one of the outstanding problems in mathematics which says all non-trivial roots of the zeta function has real part 1/2.

The zeta is, in some sense and one assumes with a great deal of work, derived from the distribution of primes. Its roots are where the function = 0. So some faint glimmer of the structure of the primes to be found in the conjecture (not yet proved) is that they're all complex numbers - but every one has real part 1/2. Very interesting obviously.

But what does it all mean then? I'm not sure that even professional mathematicians can tell us.

There seem to be two schools of thought: either mathematics represent properties of the human brain or it represents properties of the universe. I believe that latter which then means that we're talking about something as fundamental to the universe and its origins as say the Standard Model in physics.
Daniel Fretwell
Veteran poster

Post Number: 1457
Posted on Sunday, 24 July, 2011 - 12:18 am:   

There are functions that give the prime numbers!

If we define the function f on the natural numbers by:

f(n) = nth prime number

Then you get outputs f(1), f(2), ... being the sequence of prime numbers.

There are other more helpful functions that produce the prime numbers but I think the thing you are getting at is that there is no formula to calculate the nth prime exactly, depending on n.

I also think there is more understood about the Riemann Hypothesis than you think!
patfla
New poster

Post Number: 2
Posted on Sunday, 24 July, 2011 - 01:30 am:   

Oops - I meant to say

Actually the attempts have NOT been completely unsuccessful

The NOT is rather important. And then I proceed on to the Riemann Hypothesis. Actually, my understanding is that there's been a great deal of mathematics done that assumes the Riemann hypothesis as true and proceeds from there. So it if proved false, a good bit of current mathematics would be invalidated.

Although this doesn't speak to understandings of the Riemann Hypothesis itself. Certainly a great deal of work has been done on it - as well as, say, the zeta function.

I'm not sure I understood your point about functions that produce the primes numbers. You say that such exist but then say
that there is no formula to calculate the nth prime exactly, depending on n.

Maybe what you're referring to is (I forget the name) 'iterative' functions where you calculate the first result (2) and then _using that result_ you can produce the next in the sequence. That is, you have to have result n-1 (the n-1th prime) to produce prime # n?
Daniel Fretwell
Veteran poster

Post Number: 1458
Posted on Sunday, 24 July, 2011 - 10:58 am:   

See this:

http://pds16.egloos.com/pds/201002/16/25/JonesSatoWadaWiens.pdf

The primes are "represented" by this 25th degree polynomial in 26 variables so this is a function that gives the prime numbers as outputs but it is not a function of n.

We would like a formula for prime numbers depending just on n so that when you plug n into it you get the nth prime (kind of like a "box" that lets you put any positive whole number in and gives out that prime).

So far there hasnt been one found (apart from silly examples like the one given above f(n) = nth prime).

The Riemann hypothesis is simple to state but very difficult to understand (you need to know about complex numbers and complex functions) and the relations with the prime numbers isnt easy to see either (you need to look up the Euler product form of the zeta function). Chances are the zeta function you are referring to is only the basic one defined when [inline]Re(s)>1[/inline], the RH is not about this function but an extended one.

In fact we have to use the fundamental theorem of arithmetic to be able to get the link with prime numbers.

There are generalisations of the Riemann zeta function in other number fields, and there is always an Euler product relating to the "primes" (i.e. prime ideals) of the ring of integers. Again, this is formed using the fact that factorisation of ideals into prime ideals in the ring of integers is also unique. There are similar "Riemann Hypotheses" for each of these too. The standard Riemann zeta function comes from the case where the number field is the field of rational numbers.
azerbajdzan
Veteran poster

Post Number: 934
Posted on Sunday, 24 July, 2011 - 01:57 pm:   

In the given article there is polynomial of degree 25 in 26 variables. There is sentence: "an improvement to 21 variables and 21 degree was made" ... so I do not understand, why they didn't used that polynomial instead of the 25 degree and 26 variables. Wouldn't it be simpler?

Your "silly" example is as "silly" as the polynomial formula in that article if we want to generate some primes with it.
To produce a prime with that polynomial you have to set for variable "k" such a value that k+2 is prime. So you first have to know the prime k+2 to produce the same prime... it is exactly same as with your example f(n) = n-th prime.
But I do not think their formula is silly from the other point of view ... it just proves the existence of such polynomials and perhaps represents some properties of primes.
Daniel Fretwell
Veteran poster

Post Number: 1459
Posted on Sunday, 24 July, 2011 - 02:43 pm:   

Well I called mine silly because some people might think it isnt really a formula for the prime numbers (since you would have to know the nth prime in order to output it).

I do not actually think it is silly since it does provide a function...just not one that is helpful in actually computing primes.

Anyway, as I am pointing out, there are functions that generate primes but not one that does exactly what we want.
patfla
New poster

Post Number: 3
Posted on Sunday, 24 July, 2011 - 08:53 pm:   

No the zeta function I was referring to is the extended one as described here:

http://en.wikipedia.org/wiki/Riemann_zeta_function

The extension(s) and many other Riemann-hypothesis topics of interest were, I thought, well explained here:

http://www.amazon.com/Prime-Obsession-Bernhard-Greatest-Mathematics/dp/0452285259/ref=ntt_at_ep_dpt_ 1

I know that some consider Derbyshire's politics not to their taste which is not really of concern to me. I'm more concerned with the fact that he's written at least two books on higher mathematics that I've enjoyed. The one above and this one:

http://www.amazon.com/Quantity-Real-Imaginary-History-Algebra/dp/0452288533/ref=ntt_at_ep_dpt_3

> Anyway, as I am pointing out, there are functions that
> generate primes but not one that does exactly what we want.

Maybe there's a conjecture somewhere to the effect that this cannot exist - as in the quintic. Heh.

I'll have a look at the pdf - should be interesting. Thanks.
Daniel Fretwell
Veteran poster

Post Number: 1460
Posted on Monday, 25 July, 2011 - 12:16 am:   

I read those books a few years ago and really enjoyed them. Of course they arent written to be complete accounts of the topics and actually they only scratch the surface of the main ideas but they get the idea across.

There do exist formulae to generate the primes but yeah, like I say...there are none that exist that can actually compute primes, without having to use some kind of recursion.
Ashwin
Prolific poster

Post Number: 311
Posted on Monday, 25 July, 2011 - 04:04 pm:   

I have always been curious to know what all will be possible once RH is proved . (but could not get to anything perhaps due to less understanding)
Daniel Fretwell
Veteran poster

Post Number: 1465
Posted on Monday, 25 July, 2011 - 06:06 pm:   

I am no expert on the Riemann Hypothesis but the uses are not simple to explain, nor are they illuminating to non-specialists.

See:

http://en.wikipedia.org/wiki/Riemann_hypothesis#Arguments_for_and_against_the_Riemann_hypothesis

for partial answers to your question. Essentially, Riemann's famous paper deals with quite indepth results on the distribution of prime numbers. What is now known as the Riemann Hypothesis was a result that Riemann assumed in order to prove the rest (if I remember rightly he thought it was obvious).

It became a quest to prove this result.
azerbajdzan
Veteran poster

Post Number: 943
Posted on Monday, 25 July, 2011 - 06:53 pm:   

I am not sure that he thought it was obvious. I read that he mentioned somewhere that his quick attempt for the proof was unsuccessful and that he had some more important things to do (in his point of view) so he left it unproven.
Daniel Fretwell
Veteran poster

Post Number: 1466
Posted on Monday, 25 July, 2011 - 07:09 pm:   

Ah, seems more likely. I do not read german so could not read the paper.

Add Your Message Here
Posting is currently disabled in this topic. Contact your discussion moderator for more information.

Topics | Last Day | Last Week | Tree View | Search | Help/Instructions | Program Credits Administration