20130825, 07:56  #1 
Aug 2013
2^{2} 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? 
20130828, 01:27  #2 
Aug 2013
2^{2} 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? 
20130828, 01:33  #3 
Aug 2013
100_{2} 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++]; 
20130828, 02:25  #4 
Romulan Interpreter
Jun 2011
Thailand
3×3,253 Posts 

20130829, 10:36  #5 
Aug 2013
2^{2} 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) 
20131129, 08:53  #6 
Nov 2013
1_{8} Posts 
d=114I
{n,Q,P,a}
{0,1,0,3I} {1,3+2 I,3I,1I} {2,12 I,2,1+2 I} {3,2,3,3} {4,12 I,3,2+2 I} {5,2+4 I,32 I,1I} {6,1,3,6+I} {7,32 I,3I,1+I} {8,1+2 I,2,12 I} {9,2,3,3} {10,1+2 I,3,22 I} {11,24 I,32 I,1+I} {12,1,3,6I} via continued fraction, we can get (28  196 I)^2  (11  4 I)*(18  55 I)^2 
20131129, 21:43  #7  
Nov 2003
2^{2}·5·373 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
a joke about fractions  MattcAnderson  Lounge  1  20170101 14:34 
Continued Fraction Algorithm  Raman  Math  7  20090227 18:01 
Prime fractions  robert44444uk  Math  14  20080902 17:10 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 
Continued Fraction of Primes  Cyclamen Persicum  Miscellaneous Math  9  20030413 14:56 