20130131, 02:34  #1 
Mar 2010
192_{10} Posts 
Remarks on Cornacchia's Theorem
Recently I wrote a new page http://www.literka.addr.com/mathcoun...cornacchia.htm I hope it gives a new approach for Cornacchia's algorithm. Proofs of Cornacchia's I saw before were unreadable and complicated. Proof I presented is, in my opinion, straightforward. My approach avoids computing square roots, as it is in original Cornacchia's algorithm.

20130131, 08:19  #2 
Mar 2009
2·19 Posts 

20130131, 08:44  #3 
Mar 2010
2^{6}×3 Posts 

20130131, 08:58  #4 
Romulan Interpreter
Jun 2011
Thailand
2·5·7·131 Posts 
Also, how do you "easy generalize" for d>1? If d>1 your theorem does not hold. Example: x^2+6*y^2=159, there is no r for which r^2=1 (mod 159), because 159=3 (mod 4) and 1 is quadratic residue only when m=1 (mod 4). Therfore, according with your demonstration, there should be no solution for the given equation. OTOH, it is easy to see that 3^2+6*5^2=159.

20130131, 09:44  #5  
Mar 2010
2^{6}·3 Posts 
Quote:
This corresponds also to a second part of your post. Your counterexample 3^2+6*5^2=159 evidently is for the case d=6. The part of Theorem about nonexistence of solution is taking live from Cornacchia's theorem. I don't prove it on my page, since it was proved a century ago. I proved only a part, which looked new (at least for me). I had ready some remarks concerning nonexistence. But I did not write it, since it was 4 in the night and I wanted this page to be off my head. For sure, I will update this page. 

20130307, 09:27  #6  
Mar 2010
2^{6}·3 Posts 
Quote:
Moreover, it is Cornacchia's theorem, which was not denied (except of you) for more than century. I made only some remarks. Moreover, you wrote about theorem, but you say "according to your demonstration" not "according to your theorem". Moreover, 3^2+6*5^2=159 is a solution for something, but does not correspond to what I wrote. I considered only equations of the form a^2+b^2=m (mod n). Moreover, my remarks can be easily generalized for d>1, But I leave it to readers to do this. Generalized theorem does not have to look exactly the same as original. Have you ever taken math courses? 

20130307, 15:09  #7 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
2351_{8} Posts 
For d > 1, you do start with r² = d (mod m), but do not start with r² = 1 (mod m).
Then, x = Real Part of GCD(m, r+√d) Then, y = Imaginary Part of GCD(m, r+√d) if a solution does exist to x²+dy² = m. The Cornacchia's algorithm works out actually for the prime values of m only. For the composite values of m, you must combine the prime factors together by using the underlying representable quadratic form polynomials of the same discriminant value of 4d, by making for using the following identity / other equations, etc. (x_{1}²+dy_{1}²)(x_{2}²+dy_{2}²) = x_{1}x_{2}+dy_{1}y_{2}²+dx_{1}y_{2}y_{1}x_{2}² = x_{1}x_{2}dy_{1}y_{2}²+dx_{1}y_{2}+y_{1}x_{2}² (2x_{1}²+dy_{1}²)(2x_{2}²+dy_{2}²) = 2x_{1}x_{2}+dy_{1}y_{2}²+2dx_{1}y_{2}y_{1}x_{2}² = 2x_{1}x_{2}dy_{1}y_{2}²+2dx_{1}y_{2}+y_{1}x_{2}² 159 = 3 × 53 3 = 2x_{1}² + 3y_{1}², with x_{1} = 0, y_{1} = 1 53 = 2x_{2}² + 3y_{2}², with x_{2} = 5, y_{2}² = 1 (2x_{1}²+dy_{1}²)(2x_{2}²+dy_{2}²) = 2x_{1}x_{2}+dy_{1}y_{2}²+2dx_{1}y_{2}y_{1}x_{2}² = 2x_{1}x_{2}dy_{1}y_{2}²+2dx_{1}y_{2}+y_{1}x_{2}² 159 = 3² + 6 × 5² Or if d is being a quadratic nonresidue mod m, or if p²  m, then if m/p² = a²+db² then certainly that m = (pa)²+d(pb)²; m = x² + dy² form with x = pa, y = pb. @ literka : You may wish to experiment your own algorithm / implementation with the following twentysix values AZ, Cases of prime numbers that are being congruent to {1, 9, 15, 23, 25, 39} mod 56, if in case whether they are being of following form x²+14y², or 2x²+7y². as since 14 is not being an ideonal / or aka convenient number, from among within it, into them, its their own place, position respectively Last fiddled with by Raman on 20130307 at 15:17 
20130307, 15:45  #8 
Romulan Interpreter
Jun 2011
Thailand
2·5·7·131 Posts 

20130309, 12:21  #9  
Mar 2010
2^{6}·3 Posts 
Quote:
Cornacchia's algorithm works not only for m prime only. I quote from Wikipedia: "In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation , where and d and m are coprime." However I understand your position that finding solutions for prime factors gives a solution for m. What surprises me that in Cornacchia's algorithm there appear square roots. Square roots are hard to compute (I mean they take lot of time to compute). My remarks show that it can be avoided. BTW. I read few last your posts. There are few things things which surprise me. But I am in the middle of something different (and it is not Cornacchia's theorem). May be I will write soon, but in your thread. Last fiddled with by literka on 20130309 at 12:22 

20130309, 16:48  #10  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Quote:
But, that for finding out the square roots modulo composite numbers... there is being no straightforward method... you have to find out for the individual prime factors by using TonelliShanks algorithm... and then combine them product put altogether, by using Chinese Remainder Theorem... If in case whether there does exist N solutions to x²+dy² = m, then there must be 2*N square roots of d modulo m, between 1 & m1. Try solving out following equation x² + 24y² = 385. Each & every square root r of 24 mod 385, along with its own twin complement 385  r, yields out a single different solution into following above mentioned equation... ^{[SUP][SUP][SUP][SUP][SUP][COLOR=White]by using it that this some same way... it into them... they of r for the...[/COLOR]}[/SUP][/SUP][/SUP][/SUP][/SUP] By finding out square roots for composite numbers, by using them, before taking out GCD of m with r+√d into field Z[√d] is being quite directly equivalent to the step stage alone of combining individually prime factor products by using them as that this way (s²+dt²)(u²+dv2²) = su+dtv²+dsvtu² = sudtv²+dsv+tu² (2s²+dt²)(2u²+dv²) = 2su+dtv²+2dsvtu² = 2sudtv²+2dsv+tu² right afterwards after taking out GCD of m with r+√d into field Z[√d] by using them, finding out taking out square roots for composite numbers and then , applying , over thereby , by using them , CornacchiaSmith algorithm , step stage alone^{[SUP][SUP][SUP][SUP][SUP] [COLOR=White]it that this it into them... they of r for the... being from among within into for the of r the it into them, within , into into be being that own way , this own process , it into them , within , into into[/COLOR] }[/SUP][/SUP][/SUP][/SUP][/SUP] ^{[SUP][SUP][SUP][SUP][SUP] [COLOR=White]so, thus? thus, why so, thus?[/COLOR] }[/SUP][/SUP][/SUP][/SUP][/SUP] r² = d (mod m) ^{[SUP][SUP][SUP][SUP][SUP] [COLOR=White]for the of r the[/COLOR] }[/SUP][/SUP][/SUP][/SUP][/SUP]GCD(m, r+√d) Last fiddled with by Raman on 20130309 at 16:50 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pocklington's Theorem  bgbeuning  Computer Science & Computational Number Theory  7  20151013 13:55 
Modified CornacchiaSmith Algorithm  henryzz  Math  2  20120506 13:01 
Koebe's 1/4 Theorem  wpolly  Math  3  20081112 12:31 
Number Theorem  herege  Math  25  20061118 09:54 
Størmer's theorem  grandpascorpion  Factoring  0  20060910 04:59 