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?

Huh, I never realized this was this simple. Fleshing out the general case the post mentions.

Suppose p=x^n-1 is prime.

Note that:

  x^n - 1  = (x^n + x^(n-1) +... + x^2 + x) 
            -(      x^(n-1) +... + x^2 + x +1)

  =>x^n-1  = (x^(n-1) + x^(n-2) + ... + x + 1)(x-1)

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.

What about for n=4? I think the issue is that you're supposing that 2^n-1 is already prime.

Primes of this form are called Mersenne primes if you want more information on them.

See update, I realized my facepalm at roughly the same time as you:)

not only that, but if p is prime and p = 2^n-1 then n is also prime

proof: https://jott.live/texdown/mersenne

> if p is prime and p = 2^n-1 then n is also prime

for clarity p = (2^n)-1

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.

Much appreciated, thank you

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

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

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.

Definition of a prime. Only divisible by itself and one

What's the deal with all these $ symbols?

It's TeX and you have Javascript off.

If all else fails you might be able to use this MathJax bookmarklet that’s used on the stackexchange chat http://www.math.ucla.edu/~robjohn/math/mathjax.html.

Assuming you have JavaScript disabled, that is latex notation.

I'm too seeing raw $ markup. Nothing's blocked, no console errors, but there's a "425 No Reason Phrase" response for https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax..., not sure if it's relevant. That's in recent Firefox.

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.

thanks for the heads up. The site is self-hosting mathjax now

I have not disabled JS, no console errors and all privacy extensions are turned off.

edit: it's loaded now just fine, odd.