Loading ...
Sorry, an error occurred while loading the content.

Speculation concerning the primes and composites of A = 25x^2 + y^2.

Expand Messages
  • Aldrich
    {A,x,y,F,m : positive integers} Consider for a moment the values of A that are +/- 1 mod 10. Exclude all values of A with Gcd(A,y) 1, as well as all
    Message 1 of 1 , Aug 4, 2012
      {A,x,y,F,m : positive integers}

      Consider for a moment the values of 'A' that are
      +/- 1 mod 10. Exclude all values of 'A' with
      Gcd(A,y) > 1, as well as all values that are powers
      of a prime. If one of the remaining 'A' values appears
      more than once it is composite, but if it appears once
      only then it is prime, and all of them will be composed
      solely of +1 mod 4 primes. Factors for the composite
      terms may be found by putting the values of two of their
      (x,y) pairs into the formula
      F = Gcd (A, (x2-x1)*(y1+y2) + (x2 + x1)*(y1-y2)).

      In my number theory books chaos generally reigns among
      the patterns of primes and composites produced by the
      binary quadratic forms cited there and most of the time
      there is no correlation between the number of factors
      of a term and the number of times it appears as a value.
      I could find no mention of rare forms such as
      A = 25x^2 + y^2, A = 1320x^2 + y^2, A = 5x^2 + 5xy + y^2,
      A = 2x^2 + 2xy + y^2, etc. that make primes, composites
      and excluded values easily identifiable in well ordered
      equations, even though the last two of these together have
      as values three quarters of the entire set of primes!
      (+3 mod 4 primes that are also +/- 3 mod 10 are not covered).Certainly it seems possible that the kind of
      symmetry exhibited by these structures may turn out to be
      useful and there is still some hope that an obscure
      chapter or two on the topic may reside somewhere in the
      archives. However neither Hardy/Wright nor Crandall/
      Pomerance identify them as a category unto themselves.

      One obvious strategy for exploiting their characteristics
      is simply to develop a search method to see how many times
      a desired value or a batch of values occurs among all the
      'A' values of a similar size. The difficulty with this
      approach is that the results can be incomplete unless the
      entire range of y is traversed. Fortunately, this problem
      may be ameliorated somewhat.

      For my test number I chose x = 44398336 and y = 258399491
      yielding A = 116050602938281481, with the goal of
      demonstrating its primality or finding factors. It was
      not hard to write a little programming routine to
      discover that 'A' values ending in 1481 will be located
      somewhere on each of only 88 rows of y repeated in a
      cycle of 5000. Of these possibilities many can be
      eliminated because for each modulus (m prime) only a bit
      more than half of the remaining y will have a term
      somewhere that ends in 1481 and also has the same residue
      for some A mod m as the test number (here m = 3,7,11,13,17,19,23,31,61,157 and 211). If several arrays
      are built identifying which y values may still possess
      another copy of the target integer using the chosen
      moduli then we find that of about 340000000 original y
      values only about 3 in 10000 or about 105299 altogether
      potentially need to be checked to see if there is a
      corresponding (5x)^2 that will generate the chosen 'A'
      (or values near it) and factor it. If the entire range
      of y is traversed without finding another x value that
      gives us 'A' then 'A' is prime. For the given test
      number a valid x = 68132401 is found right away at
      y = 35884 yielding factors from the formula of 4045597
      and 28685655773.

      Clearly the number of possible y values that need to be considered could be greatly reduced simply by increasing the number of m values used to make exclusionary sieves, but this would also increase computational overhead, and may turn out to be too expensive. It is not clear if even an optimized version would have the potential to be tooled up to analyze really large integers.
    Your message has been successfully submitted and would be delivered to recipients shortly.