1. The problem statement, all variables and given/known data 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). 2. Relevant equations Fundamental theorem of arithmetic: Every integer n >1 can be written uniquely (up to order) as a product of primes. 3. 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?