mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2013-08-25, 07:56   #1
wsc811
 
Aug 2013

22 Posts
Wink 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?
wsc811 is offline   Reply With Quote
Old 2013-08-28, 01:27   #2
wsc811
 
Aug 2013

416 Posts
Cool 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?
wsc811 is offline   Reply With Quote
Old 2013-08-28, 01:33   #3
wsc811
 
Aug 2013

22 Posts
Default 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++];
wsc811 is offline   Reply With Quote
Old 2013-08-28, 02:25   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

7·1,279 Posts
Default

Quote:
Originally Posted by wsc811 View Post
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.
LaurV is offline   Reply With Quote
Old 2013-08-29, 10:36   #5
wsc811
 
Aug 2013

410 Posts
Exclamation 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)
wsc811 is offline   Reply With Quote
Old 2013-11-29, 08:53   #6
wsc813
 
Nov 2013

1 Posts
Default 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
wsc813 is offline   Reply With Quote
Old 2013-11-29, 21:43   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by wsc813 View Post
{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?
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
a joke about fractions MattcAnderson Lounge 1 2017-01-01 14:34
Continued Fraction Algorithm Raman Math 7 2009-02-27 18:01
Prime fractions robert44444uk Math 14 2008-09-02 17:10
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38
Continued Fraction of Primes Cyclamen Persicum Miscellaneous Math 9 2003-04-13 14:56

All times are UTC. The time now is 17:10.

Tue Dec 1 17:10:35 UTC 2020 up 82 days, 14:21, 2 users, load averages: 1.87, 2.03, 2.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.