Prove/Disapprove n2 + 3n + 1 is prime for n > 0

[blackle]

Prove or disprove that n2 + 3n + 1 is always prime for integers n > 0.

I am at a complete loss. I don't even know where to begin.
Following are the formulas that I feel might be relevant:

1) a and b are relatively prime if their GCD(a, b) = 1
2) If a and b are positive integers, there exists s and r, such that GCD(a, b) = sa + tb
3) If ac ~ bc(modm) and GCD(c, m) = 1, then a ~ b(modm)

~ stands for is congruent

Any help would be appreciated. All I need to is a guiding stone to the solution.

 

[lanedance]

I haven't attempted it, but it seems like induction would be a good one to try

 

[Mark44]

If n² + 3n + 1 were composite, it could be factored into (n + a)(n + b) for some integer values a and b.

 

[lanedance]

welcome to pf by the way ;)

 

[lanedance]

If n² + 3n + 1 were composite, it could be factored into (n + a)(n + b) for some integer values a and b.

much easier

 

[Mark44]

I second lanedance's welcome.

This problem makes me think of another one I saw a long time ago, where you're supposed to prove or disprove that n² + n + 41 is prime for all positive integers n. As it turns out, when n = 40, you get 40² + 40 + 41 = 40² + 2*40 + 1 = (40 + 1)², which is obviously not prime.

 

[lkh1986]

Let f(n) = n^2 + 3n + 1

When n = 1, f(1) = 5, which is a prime.
When n = 2, f(2) = 11, also a prime.
When n = 3, f(3) = 19, also a prime.
When n = 4, f(4) = 29, also a prime.
When n = 5, f(5) = 41, also a prime.
How about when n = 6? f(6) will give you what value? Is the value prime or composite? :)

 

[D H]

If n² + 3n + 1 were composite, it could be factored into (n + a)(n + b) for some integer values a and b.

Correction: If n² + 3n + 1 were composite, it could be factored into a_bb_n for some n.

1) a and b are relatively prime if their GCD(a, b) = 1
2) If a and b are positive integers, there exists s and r, such that GCD(a, b) = sa + tb
3) If ac ~ bc(modm) and GCD(c, m) = 1, then a ~ b(modm)

Those are *some* of the tools you would need to prove it.

Any help would be appreciated. All I need to is a guiding stone to the solution.

Hint: One way to disprove the conjecture "all positive integers are even" is to say "1 is odd". One counterexample is all that is to disprove a universal statement.

 

[Mark44]

If n² + 3n + 1 were composite, it could be factored into (n + a)(n + b) for some integer values a and b.

Correction: If n² + 3n + 1 were composite, it could be factored into a_bb_n for some n.

Aren't we saying essentially the same thing? My n + a is your a_b and my n + b is your b_n (or vice versa).

 

[D H]

Aren't we saying essentially the same thing?

I don't think so. My interpretation of your post is that you were giving a hint to the OP regarding the ability/inability to factor ²+3n+1 into the form (n+a)(n+b), where a and b are some fixed integers.

If that interpretation is correct we are saying something quite different.

 

[blackle]

Thank you! That was of great help :)

 

[Mark44]

I don't think so. My interpretation of your post is that you were giving a hint to the OP regarding the ability/inability to factor ²+3n+1 into the form (n+a)(n+b), where a and b are some fixed integers.

If that interpretation is correct we are saying something quite different.

Yes, your interpretation is correct, but I'm not seeing the difference, unless the difference involves a qualifier.

For n² + 3n + 1 to be composite how is saying that it must factor into (n + a)(n + b) for some integers a and b different from saying that it factors into a_nb_n?

Maybe a different example would be enlightening, say n² + 19n + 34. This polynomial is factorable into (n + 2)(n + 17), so for an integer n, n² + 19n + 34 is composite. Is the difference between these two examples the difference between "for some" and "for all?"

 

[D H]

Maybe a different example would be enlightening, say n² + 19n + 34. This polynomial is factorable into (n + 2)(n + 17), so for an integer n, n² + 19n + 34 is composite. Is the difference between these two examples the difference between "for some" and "for all?"

Exactly. That n²+19n+34 factors into (n+2)(n+17) means that n²+19n+34 is a composite number for all positive integers. Always. That n²+3n+1 does not factor merely means that n²+3n+1 is not always a composite number. It does not means that it is always prime.

There is no such thing as a non-constant polynomial that yields a prime for all integers n.

 

[Mark44]

OK, I get it now. The number theory class was several decades ago...