# Show that n is either a prime or the product of two primes

1. Jun 8, 2015

### Shackleford

1. The problem statement, all variables and given/known data

Assume that n > 1 is an integer such that p does not divide n for all primes ≤ n1/3. Show that n is either a prime or the product of two primes. (Hint: assume to the contrary that n contains at least three prime factors. Try to derive a contradiction.)

2. Relevant equations

Divisibility, etc.

3. The attempt at a solution

Assume that there exists three primes such that n = p1p2p3.

I suspect that you need to somehow show that there is a prime less than the cubic root that does divide n, but I'm not sure how to show it.

2. Jun 8, 2015

### PeroK

It's difficult to give a hint without giving away the answer! That's a hint!

3. Jun 8, 2015

### wabbit

Edit : PeroK is right.

4. Jun 8, 2015

### Shackleford

Well, I thought that I had to show through some clever means that one of the factors is less than the cubic root.

5. Jun 8, 2015

### wabbit

Come on, think a little bit. Or rather, look - there's no clever trick, it's all here. Go back to the statement of the problem, what does it say ?

6. Jun 8, 2015

### Shackleford

Okay. I assume that it's three distinct prime factors and not the actual cubic root for some integer, e.g. 53 = 125. In that case, it's obviously contradicted. However, I can see that it implies that at least one of the primes is less than the cubic root. If they were larger, then you wouldn't get n.

7. Jun 8, 2015

### PeroK

$125 = 5^3$ is not a contradiction to what's proposed.

8. Jun 8, 2015

### Shackleford

To the condition that p does not divide n for all primes ≤ n1/3? If not, then that's why I assume that it's three distinct primes.

9. Jun 8, 2015

### PeroK

For $n = 125$ the primes $\le n^{1/3}$ are $2, 3$ and $5$. $125$ is divisible by one of these ($p =5$) so does not meet the criteria for $n$.

10. Jun 8, 2015

### geoffrey159

It says that the prime numbers that divide n are necessarily above its cubic root.

11. Jun 8, 2015

### Shackleford

Ah, yes. That's right. I was going the wrong way.

12. Jun 8, 2015

### Shackleford

So I was correct in post #6?

13. Jun 8, 2015

### geoffrey159

You must be tired and don't see it. As people said, there is very little room between the question and giving you the answer.

14. Jun 8, 2015

### Shackleford

Well, that and I am multitasking at work, so I'll probably see it when I get home.

15. Jun 8, 2015

### wabbit

16. Jun 8, 2015

### Shackleford

And that I should probably stop going to bed after midnight.

17. Jun 8, 2015

### wabbit

Ah yes I should try that too some time

18. Jun 8, 2015

### Shackleford

I must've read the problem too quickly. A product of three distinct primes would give you an integer larger than n because the primes that do divide n are larger than the cubic root. I sure hope that's right.

19. Jun 8, 2015

### wabbit

Yes.

20. Jun 8, 2015

### Shackleford

Thanks for the help and sorry for the brainfart. This is actually a four-week class, so it's moving right along.