Could you please let me know any known method for ascertaining a given
number p could be expressed in the form x+y+24*x*y for some arbitrary
integers x,y.

---

Request for Question Clarification by mathtalk-ga on 23 Sep 2004 21:01 PDT

Hi, padmapani-ga:

If x,y are integers, then x + y + 24*x*y must also be an integer.

There is always a trivial way to express an integer in this form:

  p = x + y + 24*x*y

by taking x = p and y = 0 (or vice versa).

Are you interested in an algorithm to determine if there exists a
nontrivial solution, ie. both x,y nonzero integers?  There is such an
algorithm which can be quickly outlined for this particular "quadratic
form".  I can also post a link which explains the range of techniques
for solving more general questions of this type.

regards, mathtalk-ga

---

Clarification of Question by padmapani-ga on 24 Sep 2004 04:19 PDT

"Are you interested in an algorithm to determine if there exists a
nontrivial solution, ie. both x,y nonzero integers?"

Yes.Could you please point me out to the algorithm.I think that should
be something on the lines of "Pell Equation".

Thanks,
Padmapani

Hi, Padmapani:

Here is a nice explanation of the techniques for solving this and
various more difficult problems in Diophantine equations related to
quadratic forms:

[Solving the equation ax^2 + bxy + cy^2 + dx + ey + f = 0]
http://hometown.aol.com/jpr2718/ax2p.pdf

As discussed there, many of the more general cases of quadratic forms
will have solutions requiring the consideration of a "Pell equation
X^2 - D*Y^2 = N.

The particular quadratic form you ask about has a,c = 0 (and b
nonzero), so it falls into the category of the discriminant b^2 - 4ac
being a perfect square (see the appropriate section of the document
linked above).  Here's a quick discussion of how to solve this case,
which doesn't require consideration of a Pell equation.

Suppose that we are to determine if a integer solutions exist to:

24xy + x + y = p

Multiply both sides by 24 and add 1, so that it factors:

(24x + 1)(24y + 1) = 24p + 1

For every possible integer factorization of 24p + 1 (which is
necessarily nonzero given integer p, so only finitely many to check):

rs = 24p + 1

solve the simultaneous equations for x,y:

24x + 1 = r

24y + 1 = s

If there are any integer solutions for x,y, then they will appear among these.

Example: p = 1

Then 24k + 1 = 25, which can be factor 1*25, 5*5, -1*-25, and -5*-5.

Of these only the first gives rise to an integer solution (although
the roles of x,y are interchangeable):

24x + 1 = 1 ==> x = 0

24y + 1 = 25 ==> y = 1

This trivial solution is easily verified in the original equation (as
would be x = 1, y = 0).  As you can see, neither:

24x + 1 = 5  OR  24x + 1 = -5

has an integer solution.  So the trivial solutions are the only ones for p = 1.

regards, mathtalk-ga

---

Request for Answer Clarification by padmapani-ga on 24 Sep 2004 06:29 PDT

The crux of the solution as I see is in the statement : 

"For every possible integer factorization of 24p + 1 (which is
necessarily nonzero given integer p, so only finitely many to check):"


If I am not pushing my luck could I ask if there is a way to know the
number of possible factorisations.The reason I ask is the answer
wouldnt be practical if I choose a large number and I wish to make
some decision regarding the number of solutions.

Thank you for your continued patience with me.

---

Clarification of Answer by mathtalk-ga on 24 Sep 2004 06:50 PDT

Hi, Padmapani:

Sometimes a very large number of the form 24p + 1 will be a prime (and
thus have "few" factorizations) and sometimes it will not be prime
(composite).  To determine whether a large number is prime or not is
fairly easy, but _factoring_ a large composite number (into prime
factors) is required to determine how many different factorizations
there are.

Are you asking how to count the factorizations once you have a prime
factorization (which is essentially unique, apart from signs)?  Or are
you asking for a "magic" way of determining the exact number of
factorizations without knowing the prime factorization?

If it's the latter, I'm sure nothing of this kind is known.  One can
estimate the average number of factors, average size of the largest
prime factor, etc. based on the size of a number, but these are
"average" figures.  The estimates tell us nothing about a particular
number.

As already mentioned, a large number 24p + 1 may have only itself as a
prime factor.

A trivial upper bound on the number of prime factors can be obtained
by taking the log base 2 of a number, since each prime factor must be
at least 2.  For the particular numbers 24p + 1, we can eliminate 2
and 3 as possible prime factors apriori.  Thus a sharper estimate for
these numbers is that there are at most:

  floor( log_5(24p + 1) )

using log base 5, as that's the smallest possible prime factor.

regards, mathtalk-ga

---

Request for Answer Clarification by padmapani-ga on 24 Sep 2004 07:37 PDT

Excellent Answer! I am impressed with Google Answers.

One last clarification before I close this issue just for the sake of
background and to let you know how you have helped me.

As you know prime factorisation/primality check are important in
number theory.I have a pet project done at my grad school which
essentially is what you have stated in the last answer.

Every prime other than 2 or 3 is of the form sqrt(1+24*n) for some
arbitrary 'n'.The converse is not true obviously.Not extremely useful
either.

One way of looking at the "primality" of a number is to see if it
could be expressed in the form of sqrt(1+24*n) and if it is NOT we
could reject it.

Next if I know that a prime is composed EXACTLY of two factors (as in
the case of RSA).I know that it is of the form (1+24*x) * (1+24*y)=
1+24*z where only "z" is known and hence my question in this forum.

You have been extremely helpful.The author of the link
"http://hometown.aol.com/jpr2718/ax2p.pdf" himself contacted me a
couple of years earlier on the same subject but the clincher of this
was in you coming up with the average number of factors.

Before I rate this answer, considering the above mentioned information
would like to throw some light on my approach.

Thank you
Paddy

---

Clarification of Answer by mathtalk-ga on 24 Sep 2004 08:36 PDT

Hi, Paddy:

Thanks for posting the interesting Question.  You obviously have a
keen interest in computational number theory, as do I, and current
developments are very exciting (e.g. the proof that primality can be
determined in polynomial time by Agrawal, Kayal, and Saxena).

Unfortunately I'm at work (a "real" job) right now and cannot take
time to express my additional thoughts until this evening.  However I
can post them below as Comments whether or not the rating is given.

regards, mathtalk-ga

Thanks.

The condition that integer m = SQRT(1 + 24*n) for some integer is
equivalent to the condition that m is not divisible by 2 or 3.  So
this "primality" test is a limited form of trial division.

I think your claim about an integer with exactly two (large) prime
factors must be  referring to unequal (and nontrivial) factorizations
of its square.  For if we multiply two large primes, the result need
not be of the form 1 + 24*z (although the square of the product of two
large primes must be).

Finally, since finding solutions to xy = m is essentially the problem
of factorization, I see little hope for finding all solutions to x + y
+ 24*x*y = m that is "factorization free".  There are a number of
interesting probabilistic algorithms for factoring large numbers, once
trial division, Pollard's rho, and elliptic curves have been given
their shot.  In some cases it can be advantageous to "throw in" a
known small factor like 5 to vary the search, because the
probabilistic methods are at least as likely to find a large factor as
a small one.

regards, mathtalk-ga

>The condition that integer m = SQRT(1 + 24*n) for some integer is
>equivalent to the condition that m is not divisible by 2 or 3.  So
>this "primality" test is a limited form of trial division.

Yes. You are exactly right


>For if we multiply two large primes, the result need
>not be of the form 1 + 24*z (although the square of the product of two
>large primes must be).

I am not sure I follow you here because here is the logic of my assumption.

Sinc every prime has to be of the form sqrt(1+24n) I trying to think
that a product of two primes would be of the form

sqrt ( (1+24x) * (1+24y)) = sqrt(1+24(x+y+24xy)) = sqrt(1+24z) where z=x+y+24xy

Did I miss something there?


> see little hope for finding all solutions to x + y+ 24*x*y = m that
>is "factorization free".

Well.I agree.I did not expect an answer otherwise but the process of
another head thinking of this idea might spur me onto other ideas
which is the very reason why I started this question and I am glad
that you co-operated with my stupidity and seriously entertained the
idea.

Thanks
Paddy

Hi, Paddy:

I was confused when you wrote:

  "Next if I know that a prime is composed EXACTLY
  of two factors (as in the case of RSA).  I know
  that it is of the form

    (1+24*x) * (1+24*y) = 1+24*z 

  where only "z" is known and hence my question in
  this forum."

As I tried to reconstruct the logic of your claim, I came to the
conclusion, which was confirmed by your last Comment, that SQRT must
be applied to both sides of the equation to make it valid.

regards, mathtalk-ga