View Question
Q: Partitioning a Number in a given diophantine form ( Answered ,   3 Comments )
 Question
 Subject: Partitioning a Number in a given diophantine form Category: Science > Math Asked by: padmapani-ga List Price: \$2.50 Posted: 23 Sep 2004 19:55 PDT Expires: 23 Oct 2004 19:55 PDT Question ID: 405564
 ```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```
 Subject: Re: Partitioning a Number in a given diophantine form Answered By: mathtalk-ga on 24 Sep 2004 05:42 PDT Rated:
 ```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```
 padmapani-ga rated this answer: and gave an additional tip of: \$2.00 `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```