6 ms·

7 is the largest prime followed by a cubic number

69 points by bwasti 8y ago

montenegrohugo 8y ago
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).
- tetha 8y ago
  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?
deleted 8y ago
[deleted]
BennyH26 8y ago
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?
- rubatuga 8y ago
  Definition of a prime. Only divisible by itself and one
- gizmo686 8y ago
  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.
  - bwasti 8y ago
    ah good catch on the typo, just fixed it
    - amluto 8y ago
      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.
      - bwasti 8y ago
        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
        frankmcsherry 8y ago
        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.
        amluto 8y ago
        Aside from the 1 vs -1 issue, the proof finds all integers x such that p is prime. So I think it’s fine.
        amluto 8y ago
        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.
kowdermeister 8y ago
What's the deal with all these $ symbols?
- bwasti 8y ago
  Assuming you have JavaScript disabled, that is latex notation.
  - kowdermeister 8y ago
    I have not disabled JS, no console errors and all privacy extensions are turned off. edit: it's loaded now just fine, odd.
  - huhtenberg 8y ago
    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.js?config=TeX-MML-AM_CHTML 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.
    - bwasti 8y ago
      thanks for the heads up. The site is self-hosting mathjax now
- jmgao 8y ago
  It's TeX and you have Javascript off.
- johnsonjo 8y ago
  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 http://www.math.ucla.edu/~robjohn/math/mathjax.html.
kapauldo 8y ago
Nicely done
Tomminn 8y ago
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.
- jpegslayer 8y ago
  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.
  - Tomminn 8y ago
    See update, I realized my facepalm at roughly the same time as you:)
- bwasti 8y ago
  not only that, but if p is prime and p = 2^n-1 then n is also prime proof: https://jott.live/texdown/mersenne https://jott.live/texdown/mersenne
  - tejtm 8y ago
    > if p is prime and p = 2^n-1 then n is also prime for clarity p = (2^n)-1

69 points by bwasti 8y ago

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).

tetha 8y ago
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?

deleted 8y ago

[deleted]

BennyH26 8y ago

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?

rubatuga 8y ago
Definition of a prime. Only divisible by itself and one
gizmo686 8y ago
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.
- bwasti 8y ago
  ah good catch on the typo, just fixed it
  - amluto 8y ago
    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.
    - bwasti 8y ago
      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
      - frankmcsherry 8y ago
        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.
        amluto 8y ago
        Aside from the 1 vs -1 issue, the proof finds all integers x such that p is prime. So I think it’s fine.
      - amluto 8y ago
        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.

kowdermeister 8y ago

What's the deal with all these $ symbols?

bwasti 8y ago
Assuming you have JavaScript disabled, that is latex notation.
- kowdermeister 8y ago
  I have not disabled JS, no console errors and all privacy extensions are turned off. edit: it's loaded now just fine, odd.
- huhtenberg 8y ago
  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.js?config=TeX-MML-AM_CHTML 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.
  - bwasti 8y ago
    thanks for the heads up. The site is self-hosting mathjax now
jmgao 8y ago
It's TeX and you have Javascript off.
johnsonjo 8y ago
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 http://www.math.ucla.edu/~robjohn/math/mathjax.html.

kapauldo 8y ago

Nicely done

Tomminn 8y ago

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.

jpegslayer 8y ago
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.
- Tomminn 8y ago
  See update, I realized my facepalm at roughly the same time as you:)
bwasti 8y ago
not only that, but if p is prime and p = 2^n-1 then n is also prime proof: https://jott.live/texdown/mersenne https://jott.live/texdown/mersenne
- tejtm 8y ago
  > if p is prime and p = 2^n-1 then n is also prime for clarity p = (2^n)-1