5

We can write $(x+1)^3 - x^3$ as the difference of two consecutive cubes, then simplify it to $3x^2 +3x+1$, which as the discriminant is less than $0$ we cannot write it as a product of two linear factors without using complex numbers, therefore the quadratic is always prime. Where is the flaw in this argument?

J. W. Tanner
  • 60,406
Nav Bhatthal
  • 1,057
  • 1
    $x^2+1$ doesn’t factor without complex numbers, but isn’t prime when $x=3$, for example – J. W. Tanner Jul 07 '23 at 14:55
  • Thanks for the counter example but is there an intuitive reasoning as to why its not true? – Nav Bhatthal Jul 07 '23 at 14:58
  • 4
    Not necessarily intuitive, but the key point is that the evaluation map $\mathbb{Z}[x] \to \mathbb{Z}$ is not (not even close) to an isomorphism. Factorizations in $\mathbb{Z}[x]$ become factorizations in $\mathbb{Z}$, but not all factorizations in $\mathbb{Z}$ are factorizations in $\mathbb{Z}[x]$. – Charles Hudgins Jul 07 '23 at 15:05
  • A lot of that went over my head but say I had a polynomial factored (with real factors), I can set each one equal to $1$ to find out when such number is prime. What you are saying is that this does not work for polynomials with complex factors? – Nav Bhatthal Jul 07 '23 at 15:07
  • No, that doesn't work for prime factors. In fact, no non-constant polynomial ever takes prime values for all values of $x$. – Sarvesh Ravichandran Iyer Jul 07 '23 at 15:19
  • I am not on about for all $x$, just setting each factor equal to $1$, then finding such $x$. Take $p(x) = x^2 -4x$, we can write $p(x) = x(x-4)$ then we have for $x=1$ or $x=5$ we have $p(x)$ is prime. – Nav Bhatthal Jul 07 '23 at 15:21
  • If you don't have a real factorization, then you can't set each factor equal to $1$? Clearly the approach will then fail for complex factorizations of polynomials. Prime values of such polynomials are more difficult to locate and do not involve factorizations. For the polynomial written by you, it is extremely clear as to which values yield primes and which do not. For those that don't factorize the question is much harder. – Sarvesh Ravichandran Iyer Jul 07 '23 at 15:22
  • 1
    What does "the quadratic is always prime" mean in the question? When you say "prime" here, do you mean irreducible polynomial, or something else? – Adam Rubinson Jul 07 '23 at 15:31
  • I mean that as you cannot simplify the polynomial (the output of the polynomial must have no integer factors) – Nav Bhatthal Jul 07 '23 at 15:33
  • You mean the output of the polynomial must be a prime number when $x$ is an integer? – Adam Rubinson Jul 07 '23 at 15:35
  • Yes which is obviously not true so I want to see the flawed logic in my argument. – Nav Bhatthal Jul 07 '23 at 15:38
  • 1
    @NavBhatthal That is not true in general.The concept of "unable to simplify the polynomial" is what is called irreducibility(in this case prime).The polynomial $3x^2+3x+1$ is irreducible in $\mathbb{Z}[x]$.However the evaluation map $ev_{a}:\mathbb{Z}[x]\longrightarrow Z$,i.e, $ev_{a}(f):=f(a)$ is a ring homomorphism.An extension of prime ideal need not be a prime ideal(in this case prime element in $\mathbb{Z}$).When $a=7$ you can see this is true.It is not true in general that irreducible in $\mathbb{Z}[x]$ means irreducible in $\mathbb{Z}$. – user631874 Jul 07 '23 at 15:41
  • also $3(\color{blue}5)^2+3(\color{blue}5)+1$ is not prime – J. W. Tanner Jul 07 '23 at 15:58
  • I understand that the polynomial is not prime for all $x$, but I want to know more about deducing when polynomials output prime numbers (for integer $x$). – Nav Bhatthal Jul 07 '23 at 16:01
  • If I understand you correctly,you would like to know for what integer $x$ will the polynomial $3x^2+3x+1$ give me a prime $p$ (if that's possible). – user631874 Jul 07 '23 at 16:38
  • Yes, and I thought initially that you can do this through factoring the polynomial. – Nav Bhatthal Jul 07 '23 at 16:39
  • First you can eliminate all primes of the form $3k+2$,for they will never satisfy our criterion.So,only for certain primes of the form $3k+1$,there is some $x\in Z$ such that $3x^2+3x+2$ is prime.Maybe you can find an argument from there for when that behaviour happens.And no,just polynomial factorization won't help. – user631874 Jul 07 '23 at 16:57
  • one way to think about this is that while $3x^2 + 3x + 1$ is irreducible, but for specific values of $x$, it is reducible. For $x=5$, $3x^2 + 3x + 1 = (x+2)(x+8)$ – sku Jul 08 '23 at 07:30

2 Answers2

2

A polynomial $a_0 + a_1 x + a_2 x^2 + \ldots + a_n {x_n}^n\ $ is called irreducible over $\mathbb{R}$ if it is not the product of two (non-trivial) polynomials, each with real coefficients.

An alternative way of saying "irreducible over $\mathbb{R}$" is: "Irreducible in $\mathbb{R}[x]$".

[The trivial factorisation of $a_0 + a_1 x + a_2 x^2 + \ldots + a_n {x_n}^n\ $ is $(a_0 + a_1 x + a_2 x^2 + \ldots + a_n {x_n}^n)(1).]$

You seem to think that just because a polynomial is irreducible , that this is enough for the polynomial to spit out a prime number when you feed it an integer. Firstly, you don't give any reasons as to why you think this might be true. Secondly, it isn't true. A simpler example than the one gave in the question is $f(x) = x^2 + 1$, which is irreducible in $\mathbb{R}[x]$ as the discriminant is $<0.$ However, $f(5), f(7), f(8),$ and many more are not prime numbers.

The fact that your polynomial is the general expression of the difference between two consecutive cubes has nothing to do with your actual question.

Edit:

my reasoning as to why the polynomial must output a prime if x is an integer is because the polynomial cannot be broken down into smaller factors (which would be integers as x is an integer)

Ah. Your reasoning is wrong. It is true that a reducible polynomial will spit out a composite (non-prime) integer for almost every input $x$ (except maybe some of the inputs that makes one of the factors equal to $1$). But this doesn't mean (and has nothing to do with) an irreducible polynomial will always spit out a prime number for every $x.$

Remember: A reducible polynomial is by definition a product of two polynomials, like: $x^2-1$ is reducible because $x^2-1=(x-1)(x+1).$ For almost all integer values of $x$ that you pass into this expression - other than $x=-1,0,1$ - the output will be a composite number, since if both factors are not $1$ then you will get a composite number by definition. There is no obvious comparative statement to be made or conclusion to be drawn if the polynomial is irreducible.

If you want to look further into whether or not sets like, $\{ x^2 + 1: x\in\mathbb{N}\}$ have infinitely many primes, then just be aware that this is an open problem known as Landau's fourth problem. If you are interested in this stuff then start with Dirichlet's theorem, which is known to be true, although even the proof of this is not easy.

Adam Rubinson
  • 20,052
  • Thanks for the answer, my reasoning as to why the polynomial must output a prime if $x$ is an integer is because the polynomial cannot be broken down into smaller factors (which would be integers as $x$ is an integer). If we have a polynomial with two real factors, we can set each one equal to $1$ to find out when the output is prime. Why can we not do this with irreducible polynomials? – Nav Bhatthal Jul 07 '23 at 16:07
  • Ok, I've updated my answer to reply to your comment. – Adam Rubinson Jul 07 '23 at 16:11
  • Thank you, is there an intuitive reasoning as to why the idea that a reducible polynomial can be thought of as a chain of integers multiplied (for integer $x$), but the same idea flops for irreducible ones. – Nav Bhatthal Jul 07 '23 at 16:13
  • Basically for reducible polynomials it is obvious. For irreducible polynomials it is not obvious. – Adam Rubinson Jul 07 '23 at 16:18
  • So there is no intuitive explanation? – Nav Bhatthal Jul 07 '23 at 16:25
  • 1
    @NavBhatthal There's really just no reason for polynomial irreducibility to say anything about primality of numbers. Sure, a reducible polynomial gives you a definite way to factor a number if that number happens to be in the range of the polynomial. But maybe that number has other factorizations that are different from how the polynomial splits. Why should polynomial irreducibility tell you anything about factorizations that might not come from polynomial factors? – Chris Brooks Jul 07 '23 at 16:34
  • @ChrisBrooks you said it better than I did. – Adam Rubinson Jul 07 '23 at 16:35
  • I think I can see the flaw in my thinking, so the "version" of the factorisation that the polynomial gives is not the only way to factorise such number? (Talking in terms of reducible polynomials) – Nav Bhatthal Jul 07 '23 at 16:36
  • That's not true: Each polynomial has a unique factorisation, in the same way that every number has a unique factorisation (the fundamental theorem of arithmetic). – Adam Rubinson Jul 07 '23 at 16:39
  • This all sending me in circles and I still dont understand why I cant find out when an irreducible polynomial is prime when its inputs are integers/ – Nav Bhatthal Jul 07 '23 at 16:44
  • @NavBhatthal This has nothing to do with reducibility or irreducibility of the polynomial.That's the point.It only depends on when $f(x)=p$,i.e,when is $x_{0}$ an integer if it is a solution of the polynomial $f(x)-p=0$. – user631874 Jul 07 '23 at 17:06
  • Making more sense now, you stated that knowing reducibility or not has no real help on the factorisation, just that it gives us one way to write out the "uniform product expression". It still remains true that this can help us find when reducible polynomials are prime though? I am not misunderstanding that am I? – Nav Bhatthal Jul 07 '23 at 17:14
2

You have successfully proven the following statement: $$\not\exists a, b, c, d \in \mathbb Z: \forall x\in \mathbb Z: (x+1)^3-x^3=(ax+b)(cx+d)\,.$$

You have not proven the following statement: $$\forall x\in \mathbb Z: \not\exists a, b, c, d \in \mathbb Z: (x+1)^3-x^3=(ax+b)(cx+d)\,.$$

The quantifiers are in the wrong order.

Bart Michels
  • 26,355
  • I have not used too much set notation, what does it mean if the funny symbols are the other way around (are they not just telling us that $a,b,c,d$ and $x$ are integers)? – Nav Bhatthal Jul 07 '23 at 17:11
  • $\forall$ means for all; $\not\exists$ means there does not exist – J. W. Tanner Jul 07 '23 at 17:26