mersenneforum.org why continued fractions gives one factor for N=(4m+3)(4n+3)
 Register FAQ Search Today's Posts Mark Forums Read

 2013-08-25, 07:56 #1 wsc811   Aug 2013 48 Posts why continued fractions gives one factor for N=(4m+3)(4n+3) for example N=989=23*43 ,Sqrt[N]={a0;a1,a2,...,2a0} {n,Q,P,a} {0,1,0,31} {1,28,31,2} {2,13,25,4} {3,20,27,2} {4,41,13,1} {5,5,28,11} {6,52,27,1} {7,7,25,8} {8,4,31,15} {9,37,29,1} {10,25,8,1} {11,28,17,1} {12,31,11,1} {13,19,20,2} {14,35,18,1} {15,20,17,2} {16,23,23,2} Q=23 is one factor {17,20,23,2} {18,35,17,1} {19,19,18,2} {20,31,20,1} {21,28,11,1} {22,25,17,1} {23,37,8,1} {24,4,29,15} {25,7,31,8} {26,52,25,1} {27,5,27,11} {28,41,28,1} {29,20,13,2} {30,13,27,4} {31,28,25,2} {32,1,31,62} N=43*103=4429 {0,1,0,66} {1,73,66,1} {2,60,7,1} {3,27,53,4} {4,52,55,2} {5,39,49,2} {6,92,29,1} {7,5,63,25} {8,117,62,1} {9,12,55,10} {10,17,65,7} {11,89,54,1} {12,36,35,2} {13,85,37,1} {14,25,48,4} {15,69,52,1} {16,60,17,1} {17,43,43,2} Q=43 is one factor {18,60,43,1} {19,69,17,1} {20,25,52,4} {21,85,48,1} {22,36,37,2} {23,89,35,1} {24,17,54,7} {25,12,65,10} {26,117,55,1} {27,5,62,25} {28,92,63,1} {29,39,29,2} {30,52,49,2} {31,27,55,4} {32,60,53,1} {33,73,7,1} {34,1,66,132} in many cases, it's so .and this can be used for decomposition?
 2013-08-28, 01:27 #2 wsc811   Aug 2013 22 Posts my mathematica code d = 23*43; pell = -1; P[0] = 0; Q[0] = 1; x[0] = (P[0] + Sqrt[d])/Q[0]; a[0] = IntegerPart[x[0]]; i = 0; While[(x[i] != 1/(x[0] - a[0]) && P[i] != pell) || i == 1, P[i + 1] = Q[i] a[i] - P[i]; Q[i + 1] = (d - P[i + 1]^2)/Q[i]; x[i + 1] = (P[i + 1] + Sqrt[d])/Q[i + 1]; a[i + 1] = IntegerPart[x[i + 1]]; Print[{i, Q[i], P[i], a[i]}]; i++]; i cant use code style ,have proper method?
 2013-08-28, 01:33 #3 wsc811   Aug 2013 22 Posts Or you can use complex number d = 11 - 4 I; pell = -1; P[0] = 0; Q[0] = 1; x[0] = (P[0] + Sqrt[d])/Q[0]; a[0] = Round[x[0]]; i = 0; While[(x[i] != 1/(x[0] - a[0]) && P[i] != pell) || i == 1, P[i + 1] = Q[i] a[i] - P[i]; Q[i + 1] = (d - P[i + 1]^2)/Q[i]; x[i + 1] = (P[i + 1] + Sqrt[d])/Q[i + 1]; a[i + 1] = Round[x[i + 1]]; Print[{i, Q[i], P[i], a[i]}]; i++];
2013-08-28, 02:25   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

222318 Posts

Quote:
 Originally Posted by wsc811 i cant use code style ,have proper method?
On the editor' window (the one which appears when you click "reply" or "new post") bar, click the sign that appears like a sharp sign ("#"), or put your text between [code] tags.

 2013-08-29, 10:36 #5 wsc811   Aug 2013 410 Posts you can observe the following list N=4181 as complex {0,1,0,65} {1,-44,65,-3} {2,7,67,19} {3,-25,66,-5} {4,-28,59,-4} {5,-49,53,-2} {6,-44,45,-2} {7,-53,43,-2} {8,-4,63,-32} {9,11,65,12} {10,-28,67,-5} {11,41,73,3} {12,41,50,3} {13,-28,73,-5} {14,11,67,12} {15,-4,65,-32} {16,-53,63,-2} {17,-44,43,-2} {18,-49,45,-2} {19,-28,53,-4} {20,-25,59,-5} {21,7,66,19} {22,-44,67,-3} {23,1,65,130} N=4181 as real {0,1,0,64} {1,85,64,1} {2,44,21,1} {3,83,23,1} {4,7,60,17} {5,100,59,1} {6,25,41,4} {7,28,59,4} {8,49,53,2} {9,44,45,2} {10,53,43,2} {11,4,63,31} {12,115,61,1} {13,11,54,10} {14,95,56,1} {15,28,39,3} {16,77,45,1} {17,41,32,2} {18,41,50,2} {19,77,32,1} {20,28,45,3} {21,95,39,1} {22,11,56,10} {23,115,54,1} {24,4,61,31} {25,53,63,2} {26,44,43,2} {27,49,45,2} {28,28,53,4} {29,25,59,4} {30,100,41,1} {31,7,59,17} {32,83,60,1} {33,44,23,1} {34,85,21,1} {35,1,64,128} for Q in two list ,what do you find ? tip(+/- symbol)
 2013-11-29, 08:53 #6 wsc813   Nov 2013 1 Posts d=11-4I {n,Q,P,a} {0,1,0,3-I} {1,3+2 I,3-I,1-I} {2,1-2 I,2,1+2 I} {3,2,3,3} {4,1-2 I,3,2+2 I} {5,-2+4 I,3-2 I,-1-I} {6,-1,3,-6+I} {7,-3-2 I,3-I,-1+I} {8,-1+2 I,2,-1-2 I} {9,-2,3,-3} {10,-1+2 I,3,-2-2 I} {11,2-4 I,3-2 I,1+I} {12,1,3,6-I} via continued fraction, we can get (28 - 196 I)^2 - (11 - 4 I)*(18 - 55 I)^2
2013-11-29, 21:43   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wsc813 {n,Q,P,a} {0,1,0,3-I} {1,3+2 I,3-I,1-I} {2,1-2 I,2,1+2 I} {3,2,3,3} {4,1-2 I,3,2+2 I} {5,-2+4 I,3-2 I,-1-I} {6,-1,3,-6+I} {7,-3-2 I,3-I,-1+I} {8,-1+2 I,2,-1-2 I} {9,-2,3,-3} {10,-1+2 I,3,-2-2 I} {11,2-4 I,3-2 I,1+I} {12,1,3,6-I} via continued fraction, we can get (28 - 196 I)^2 - (11 - 4 I)*(18 - 55 I)^2
Would someone move this to misc.math?

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Lounge 1 2017-01-01 14:34 Raman Math 7 2009-02-27 18:01 robert44444uk Math 14 2008-09-02 17:10 dsouza123 Software 12 2003-08-21 18:38 Cyclamen Persicum Miscellaneous Math 9 2003-04-13 14:56

All times are UTC. The time now is 05:32.

Sat Apr 17 05:32:28 UTC 2021 up 9 days, 13 mins, 0 users, load averages: 1.34, 1.62, 1.67