mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   why continued fractions gives one factor for N=(4m+3)(4n+3) (https://www.mersenneforum.org/showthread.php?t=18508)

 wsc811 2013-08-25 07:56

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}
[COLOR=blue]{16,23,23,2} Q=23 is one factor[/COLOR]
{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}
[COLOR=blue]{17,43,43,2} Q=43 is one factor[/COLOR]
{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?

 wsc811 2013-08-28 01:27

my mathematica code

[LEFT]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?[/LEFT]

 wsc811 2013-08-28 01:33

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++];

 LaurV 2013-08-28 02:25

[QUOTE=wsc811;351065][LEFT]i cant use code style ,have proper method?[/LEFT]
[/QUOTE]
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.

 wsc811 2013-08-29 10:36

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)

 wsc813 2013-11-29 08:53

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

 R.D. Silverman 2013-11-29 21:43

[QUOTE=wsc813;360599]{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[/QUOTE]

Would someone move this to misc.math?

 All times are UTC. The time now is 19:21.