Math is funny. There's an infinite amount of primes, and even though we know a lot of them there's still more left (read:infinite). But at the same time, with high-school level algebra we can prove that the largest prime followed by a cubic number is 7.
The proof is really simple, but the fact is quite unintuitive (at least for me).
That is number theory. Number theory is at the same time extremely profound and very very blunt.
Every prime is double of an integer + 1, except for 2. This follows because primes are integers, integers are either 2 times n or 2 times n+1 and numbers representable as 2 times n have 2 as a prime factor, if n > 1. Hence, except for 2.
Overall, number theory is one example to me how very, very simple concepts are actually hard - because you're not trained to look for them. The proof is just ... obvious once pointed out. But why would you look for it with such simple manners?
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.
> 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.
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.
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.
More specifically, when I open the page by clicking on the HN link or copy-pasting the URL into the bar and pressing Enter, the page renders OK. If I am to reload the page with Ctrl-R after that, it shows up in raw $ markup and no amount of refreshing helps. Furthermore, full reload (via Ctrl-Refresh) yields that 425 response.
So if p=x^n-1 is prime, one of the factors must be equal to 1. If the first factor is 1, this implies x=0 and so the second factor is -1. Therefore the second factor must be 1, and x=2.
Therefore if x^n-1 is prime, x must be 2. Damn that's cool. At first I thought any number 2^n-1 would be prime, but then I realized that obviously the left hand factor can have subfactors. Which is to say I remembered 15 exists.
30 comments
[ 3.4 ms ] story [ 67.9 ms ] threadThe proof is really simple, but the fact is quite unintuitive (at least for me).
Every prime is double of an integer + 1, except for 2. This follows because primes are integers, integers are either 2 times n or 2 times n+1 and numbers representable as 2 times n have 2 as a prime factor, if n > 1. Hence, except for 2.
Overall, number theory is one example to me how very, very simple concepts are actually hard - because you're not trained to look for them. The proof is just ... obvious once pointed out. But why would you look for it with such simple manners?
Could somebody tell me why each of the factor components must be equal to one?
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.
> 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.
> 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
You really do have to consider negative factors.
https://news.ycombinator.com/item?id=17904921
edit: it's loaded now just fine, odd.
More specifically, when I open the page by clicking on the HN link or copy-pasting the URL into the bar and pressing Enter, the page renders OK. If I am to reload the page with Ctrl-R after that, it shows up in raw $ markup and no amount of refreshing helps. Furthermore, full reload (via Ctrl-Refresh) yields that 425 response.
Just FYI.
Suppose p=x^n-1 is prime.
Note that:
So if p=x^n-1 is prime, one of the factors must be equal to 1. If the first factor is 1, this implies x=0 and so the second factor is -1. Therefore the second factor must be 1, and x=2.Therefore if x^n-1 is prime, x must be 2. Damn that's cool. At first I thought any number 2^n-1 would be prime, but then I realized that obviously the left hand factor can have subfactors. Which is to say I remembered 15 exists.
Primes of this form are called Mersenne primes if you want more information on them.
proof: https://jott.live/texdown/mersenne
for clarity p = (2^n)-1