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

[Shackleford]

Homework Statement

Assume that n > 1 is an integer such that p does not divide n for all primes ≤ n^1/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.)

Homework Equations

Divisibility, etc.

The Attempt at a Solution

Assume that there exists three primes such that n = p₁p₂p₃.

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.

 

[PeroK]

Homework Statement

Assume that n > 1 is an integer such that p does not divide n for all primes ≤ n^1/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.)

Homework Equations

Divisibility, etc.

The Attempt at a Solution

Assume that there exists three primes such that n = p₁p₂p₃.

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.

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

 

[wabbit]

Edit : PeroK is right.

 

[Shackleford]

Well, if so then p1, p2, and p3 each divide n, so what do you conclude ?

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

 

[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 ?

 

[Shackleford]

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 ?

Okay. I assume that it's three distinct prime factors and not the actual cubic root for some integer, e.g. 5³ = 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.

 

[PeroK]

Okay. I assume that it's three distinct prime factors and not the actual cubic root for some integer, e.g. 5³ = 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.

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

 

[Shackleford]

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

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

 

[PeroK]

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

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

 

[geoffrey159]

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

 

[Shackleford]

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

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

 

[Shackleford]

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

So I was correct in post #6?

 

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

 

[Shackleford]

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.

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

 

[wabbit]

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

Now you know how efficient your multitasking is.

 

[Shackleford]

Now you know how efficient your multitasking is.

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

 

[wabbit]

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

Ah yes I should try that too some time

 

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

 

[wabbit]

Yes.

 

[Shackleford]

Yes.

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