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

Conjecture
Badges: 0
Rep:
?
#1
Report Thread starter 6 years ago
#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
reply
SimonM
Badges: 18
Rep:
?
#2
Report 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
reply
Conjecture
Badges: 0
Rep:
?
#3
Report Thread starter 6 years ago
#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
reply
SimonM
Badges: 18
Rep:
?
#4
Report 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
reply
jack.hadamard
Badges: 4
Rep:
?
#5
Report 6 years ago
#5
Tim Gowers' Proving the Fundamental Theorem of Arithmetic may be of some use.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

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

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%

Watched Threads

View All