- #1

RJLiberator

Gold Member

- 1,095

- 63

## Homework Statement

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).

## Homework Equations

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?