Question: Let n> 1 be an integer which is not prime. Prove that there exists a prime p such that p|n and p≤ sqrt(n).
Fundamental theorem of arithmetic: Every integer n >1 can be written uniquely (up to order) as a product of primes.
The Attempt at a Solution
Pf. By the F.T.O.A. there exists a prime p such that p|n. [this proves part 1 of the question
We can write n = pq where q,p ∈ℤ and 1 ≤p, q ≤n.
Suppose p ≤ q. For contradiction, assume p > sqrt(n).
Then q ≥ p > sqrt(n). However, if this is true, then:
n = pq > sqrt(n)sqrt(n) > n, and we have a contradiction.
so p ≤ sqrt(n).
I feel moderately confident with this proof. Are there any holes that you detect?