# Proof any non-prime can be written as a product of prime factors?Watch

Announcements
#1
I was wondering if anyone knew/could link me to a proof of this. I know the proof that there's infinite primes (which stems from this) but I am curious about how you'd go about proving this one? Thankyou!

P.S. I am not an undergraduate so may not have come accross certain things needed, but any links to what's needed would be appreciated!
0
6 years ago
#2
Definition of a prime: any number whose only factors are one and itself (except 1).

Therefore a non-prime, n, must have a factor k which isn't one or itself, less than n. Using strong induction we can see that that k and n/k can be factored into primes, therefore n can be.
0
#3
(Original post by SimonM)
Definition of a prime: any number whose only factors are one and itself (except 1).

Therefore a non-prime, n, must have a factor k which isn't one or itself, less than n. Using strong induction we can see that that k and n/k can be factored into primes, therefore n can be.
I think I get the general jist of that If the factors of n didn't eventually factor into primes, there would be an infinite number of factors which is impossible? Just wondering, what is strong induction? Is it similar to "normal" proof by induction?
0
6 years ago
#4
(Original post by Conjecture)
I think I get the general jist of that If the factors of n didn't eventually factor into primes, there would be an infinite number of factors which is impossible? Just wondering, what is strong induction? Is it similar to "normal" proof by induction?
Yes. Strong induction we assume our statement (here "all numbers factor into a product of primes") is true for all numbers less than n. Normal induction we only assume our statement is true for n-1.

(The two forms are actually equivalent)
0
6 years ago
#5
Tim Gowers' Proving the Fundamental Theorem of Arithmetic may be of some use.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• The University of Law
The Bar Series: Applications and Interviews - London Bloomsbury campus Postgraduate
Thu, 17 Oct '19
• Cardiff Metropolitan University
Sat, 19 Oct '19
• Coventry University
Sat, 19 Oct '19

### Poll

Join the discussion

#### How has the start of this academic year been for you?

Loving it - gonna be a great year (140)
17.83%
It's just nice to be back! (212)
27.01%
Not great so far... (281)
35.8%
I want to drop out! (152)
19.36%