Here is a nice explanation of the techniques for solving this and
various more difficult problems in Diophantine equations related to
[Solving the equation ax^2 + bxy + cy^2 + dx + ey + f = 0]
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.
Clarification of Answer by
24 Sep 2004 06:50 PDT
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
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
As already mentioned, a large number 24p + 1 may have only itself as a
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.
Clarification of Answer by
24 Sep 2004 08:36 PDT
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.