Number Theory interest

Discussion in 'Physics & Math' started by RJBeery, Oct 7, 2009.

  1. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    So I came across some old notes of mine from 10 or 15 years ago and thought I would share the discovery that sparked my interest in number theory...

    \(f(x) = x^{2}-x+c\) [eqn 1], with c = {3, 5, 11, 17, 41}

    Any number theorists here will recognize this as Euler-Rabinowitsch prime generating polynomials (I wasn't aware of this at the time - I was but a lowly 'armchair mathematician'

    Please Register or Log in to view the hidden image!

    ). I simply found them amazing because these equations will yield nothing but primes for x = 1..(c-1)!

    The discovery that I believe to be novel is that analyzing the form of x itself is sufficient to determine whether f(x) shall yield a prime. Specifically, when x is an integer of the form

    \(x = \frac{i(i-1)}{j}+i+cj\) [eqn 2], with integer i and j > 0

    then we know f(x) is composite, otherwise f(x) yields nothing but primes. Furthermore, when f(x) is composite we know that

    \(f(x) = \frac{(i^2+ij+cj^2)(i^2+(j-2)i+cj^2-j+1)}{j^{2}}\) [eqn 3]

    and one of the multiplicands in the numerator is invariably* a multiple of the divisor \(j^2\), resulting in two (not necessarily prime) factors of f(x). Very little practical use but I thought it might spark someone else's interest in the fascinating field of number theory. Also, I was hoping that someone with more of a mathematical background might have some insight on what is going on with these equations. I know that the set of c = {3, 5, 11, 17, 41} has to do with these numbers being of a certain class and having discriminant -163, but at that point I'm in over my head...

    *Must this always be the case? It is true for values of x to roughly 2.5 billion, and I suspect that the answer is yes due to the restriction on the possible combinations of {i, j} that result in an integer value for x in equation 2, but I never proved it. Maybe someone here could?
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. temur man of no words Registered Senior Member

    Messages:
    1,330
    Yes, it is simply because you choose i(i-1) to be divisible by j in order for x to be an integer.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    Thanks temur. Is this obvious to you? Can you show this algebraically? I suspect the same thing but mine is simply supposition.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Ok let me break down this post to try to understand it with questions of my own.

    Ok what does f(x) mean to you because to me it means y just written as f(x) for identification purposes if you had multipe equations of that type.
    umm isn't it obvious that the sequence you wrote does have to do with the equation you wrote because it is equal to c which is one of the variables in your equation. Also what you by what is going on with them? they're three different equations.
     
    Last edited by a moderator: Oct 8, 2009
  8. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    Yeah, I'm a Comp Sci graduate, so f(x) is familiar to me but equivalent to "y" I suppose.
    Well, Science Man, what I meant to write is that the formula "f(x)=x^2 - x + c" produces a prime for all values 0 < x < c when c = {3, 5, 11, 17, 41}". I apologize if there is a more succinct way of stating this.
    This was just a secondary question that I had which is, "must it always be the case that j^2 is a divisor of either of the two multiplicands in the numerator in equation 3" given the restrictions of x being an integer in equation 2?
     
  9. ok so since you're solving for f(x) aka y and 0 < x < c now lets substitute 3 for c 0<x<3 so is x al numbers between 0 and 3?

    This was just a secondary question that I had which is, "must it always be the case that j^2 is a divisor of either of the two multiplicands in the numerator in equation 3" given the restrictions of x being an integer in equation 2?[/QUOTE]

    I googled multiplicands and got "a number being multiplied by a multiplier" what does mutiplier mean? When googled that it went in reverse/vice versa on me.
    By the way I don't mean to question you in an offeneding way I just want to understand this thing you brought to the table. Please don't got annoyed by me.
     
  10. temur man of no words Registered Senior Member

    Messages:
    1,330
    i and j are such that x is an integer. Therefore f(x) must be an integer, which means that "one of the multiplicands in the numerator is invariably a multiple of the divisor". I think "factor" is more often used than "multiplicand".
     
  11. Roughnet13888 Registered Member

    Messages:
    1
    Well said.
     
  12. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    Yes the formula for c = 3 is rather trivial, I agree. But I find it pretty fantastic that (when we set c = 41) x^2 - x + 41 produces 40 consecutive and distinct primes!

    I used the term multiplicand to mean "one of the items being multiplied together". In other words, when x is of the proper form in equation 2 then you may calculate what the factors are of equation 1 by using equation 3.

    Agreed!

    But this is where I don't follow! Because f(x) is an integer we know that the first summand in equation 1 is also an integer, so i(i-1) is divisible by j. But I don't immediately see why that necessitates that either (i^2+ij+cj^2) or (i^2+(j-2)i+cj^2-j+1) is divisible by j^2...
     
  13. temur man of no words Registered Senior Member

    Messages:
    1,330
    Otherwise f(x) would not be an integer, would it?

    I missed something which is the possibility that each of the two factors can be divisible by j so the product is divisible by j^2.
     
  14. rpenner Fully Wired Valued Senior Member

    Messages:
    4,833
    Conway has a short bit on this I think in his shiny book on Number theory -- don't have it with me right now.

    http://books.google.com/books?id=cLEhHELiwrQC
    Pages 224-226, dealing with the tenth discriminant problem and the Heegner numbers of complex number systems which support unique factorization.
     
    Last edited: Oct 8, 2009
  15. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    temur: Yes that seems to be a possibility but this doesn't actually happen. j^2 either divides the first or the second factor for values of x up to 2.5 billion. Because the second factor has "+1" it makes sense that j would not divide both...
     
  16. temur man of no words Registered Senior Member

    Messages:
    1,330
    So you have a proof: Denote

    A = i^2 + ij + cj^2

    B = i^2 + (j-2)i + cj^2 - j +1

    We know that j^2 divides AB. We want to show that j does not divide both A and B. We have (in mod j)

    A - B = 2i - 1 = i + (i-1)

    Since x is an integer we know that j divides i(i-1). But j cannot divide both i and i-1. So A-B is not divisible by j, which means j cannot divide both A and B.
     
  17. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    temur: excellent logic! Reading this it occurred to me that I can be more specific about the factors of f(x) (presuming that x is of the proper form described in eqn 2):

    If j divides i, then the factors of f(x) are

    \(\frac{(i^2+ij+cj^2)}{j^{2}} and (i^2+(j-2)i+cj^2-j+1)\)

    otherwise they are

    \(\frac{(i^2+(j-2)i+cj^2-j+1)}{j^{2}} and (i^2+ij+cj^2)\)
     
  18. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    The BIG question is this: what values of x are not able to be represented in the form of equation 2? (A trivial example is all x < c). An answer to this question would allow for arbitrarily large primes to be generated. Does anyone know any Diophantine tricks?
     
  19. temur man of no words Registered Senior Member

    Messages:
    1,330
    Nice!

    Why?
     
  20. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    It's due to the nature of equations 1 and 2. If x is of the proper form described in eqn 2 then f(x) is composite, otherwise f(x) is prime. If we had a method to find arbitrarily large values of x which could not be represented by eqn 2, then we could also find arbitrarily large prime numbers by calculating f(x).
     
  21. temur man of no words Registered Senior Member

    Messages:
    1,330
    How do you know f(x) is prime if x is not as in eqn 2?
     
  22. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    Eqn 2 comes from analyzing the composites, so it's empirical rather than a proper proof.

    Here's the usage:

    Example1:
    158*(157)+11 = 24817; (x=158, c=11, f(x)=24817) [eqn 1]
    Since
    158 = (13(13-1)/12)+13+11*12; (x=158, i=13, j=12, c=11) [eqn 2]
    f(x) is composite. In fact, we know that
    f(x) = (1/12^2)(13^2+13*12+11*12^2)(13^2+(12-2)*13+11*12^2-12+1) =
    (1/144)(1909)(1872) = 1909*13 = 24817 [eqn 3]

    Example2:
    161*(160)+11 = 25771; (x=161, c=11, f(x)=25771)
    But because 161 cannot be expressed in terms of (i(i-1)/j)+i+cj
    we know that 25771 IS PRIME.
     

Share This Page