Hacker News Reader

Comment by BennyH26 | Hacker News Reader

The proof states: "For n to be prime either x² + x + 1 = 1 or x - 1 = 1"

Could somebody tell me why each of the factor components must be equal to one?

I believe there is a typo, and it should say "for p to be prime".

Since p = (x^2 + x + 1)(x - 1), and both of those factors are integers, if both factors were not 1, then we would have demonstrated a factoring of p; therefore p would be composite.

If you wanted to be super formal, you would have to deal with the possibility that the factors were -1, but that is more of an uninteresting technicality.

ah good catch on the typo, just fixed it

There’s another minor error. The proof states:

> For $ p $ to be prime either $ x^2 + x + 1 = 1 $ or $ x - 1 = 1 $.

That’s not quite true. In general, if p is prime and p=a·b for integers a and b, then at least one of a and b is 1 or -1. The rest of the proof still works since, as you say, x != 0, so x + 1 != -1.

I'll leave that omitted to keep things concise. I think it is quite common to assume a domain of natural numbers when talking about primes.

> then at least one of a and b is 1 or -1

I think you mean exactly one of a and b is 1 or -1

To be pedantic, shouldn't you also need to rule out the possibility that x is a negative number? For example, x = -1 satisfies your quadratic equation, but because we are doing an odd power of x you can rule it out.

Aside from the 1 vs -1 issue, the proof finds all integers x such that p is prime. So I think it’s fine.

You can’t just assume a range of natural numbers in this context. You have a prime p that is equal to f(x) for some polynomial f with integer coefficients and some integer x. You observe that f(x)=a(x)b(x) where a and b are also polynomials with integer coefficients. It does not follow that a and b are non-negative. As an example, let f(x)=x^3-2x^2-3x+6. Then a(x)=x-2 and b(x)=x^2-3. Now you could try to argue that, if f(x) is prime, then one of a(x) and b(x) is 1, so x is 2 or 3, but f(2)=0 and f(3)=6, so f(x) can’t be prime for integer x. But you would be wrong, and, indeed, f(1)=2, which is prime.

You really do have to consider negative factors.

that's a great counter example! updated the post

You linked to the reply URL, which works only for logged-in users. Please consider using this instead:

https://news.ycombinator.com/item?id=17904921

done

Much appreciated, thank you

Definition of a prime. Only divisible by itself and one

Reply on news.ycombinator.com