mersenneforum.org > Math n=a²+b²
 Register FAQ Search Today's Posts Mark Forums Read

 2022-05-04, 23:38 #1 bhelmes     Mar 2016 40410 Posts n=a²+b² A peaceful and pleasant night for you, if n odd and not a square and n, a, b element N how do I find (fast) the composition n=a²+b² ? Thanks in advance if you spent me some lines or a link.
2022-05-05, 00:55   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

990110 Posts

Quote:
 Originally Posted by bhelmes
Just type "sum of two squares". -> https://en.wikipedia.org/wiki/Sum_of...quares_theorem
Would you rather like to have a link to "let me google that for you"?

 2022-05-06, 11:25 #3 Gelly     May 2020 47 Posts Perhaps I am horribly dull, but I found researching based on the "just google these four words" criteria became horribly unclear, as people on the internet are more concerned with whether you can represent a number as the sum of two squares, or how to factorize when you know two ways of writing a number as the sum of squares. I want to save the trouble for anyone else interested in finding a sum of squares decomposition given only the fact that the number is 1 mod 4 and nothing else - no factorization, nothing. I eventually stumbled upon Brillhart's 1972 paper "Note on representing a prime as a sum of two squares.", which not only gives a lot of methods to decompose a number into a sum of two squares, but also the most efficient way to do so. Here is the jstor link. https://www.jstor.org/stable/2005889 I would much rather math research on something so basic not be buried in references and muddled Wikipedia jargon, because this should be a lot easier to find - mostly, so people can find out for themselves why it's so hard to get two sum of two squares decompositions given an unfactorized number.
 2022-05-06, 16:01 #4 Dobri   "Καλός" May 2018 2·32·19 Posts The Wolfram code below represents the prime exponent p of each known Mersenne prime 2p-1 as a unique sum of two squares p = a2 + b2 with the exception of the prime exponents p = 4k + 3 for which there is no such sum. Code: MPData = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933}; Np = 51; ic = 1; While[ic <= Np, p = MPData[[ic]]; Ms = FindInstance[(p == ac^2 + bc^2) && (ac <= bc), {ac, bc}, PositiveIntegers, 2]; Print[p, " ", Mod[p, 4], " ", Ms]; ic++;]; Code: 2 2 {{ac->1,bc->1}} 3 3 {} 5 1 {{ac->1,bc->2}} 7 3 {} 13 1 {{ac->2,bc->3}} 17 1 {{ac->1,bc->4}} 19 3 {} 31 3 {} 61 1 {{ac->5,bc->6}} 89 1 {{ac->5,bc->8}} 107 3 {} 127 3 {} 521 1 {{ac->11,bc->20}} 607 3 {} 1279 3 {} 2203 3 {} 2281 1 {{ac->16,bc->45}} 3217 1 {{ac->9,bc->56}} 4253 1 {{ac->38,bc->53}} 4423 3 {} 9689 1 {{ac->35,bc->92}} 9941 1 {{ac->70,bc->71}} 11213 1 {{ac->67,bc->82}} 19937 1 {{ac->76,bc->119}} 21701 1 {{ac->26,bc->145}} 23209 1 {{ac->40,bc->147}} 44497 1 {{ac->64,bc->201}} 86243 3 {} 110503 3 {} 132049 1 {{ac->120,bc->343}} 216091 3 {} 756839 3 {} 859433 1 {{ac->187,bc->908}} 1257787 3 {} 1398269 1 {{ac->610,bc->1013}} 2976221 1 {{ac->1189,bc->1250}} 3021377 1 {{ac->244,bc->1721}} 6972593 1 {{ac->352,bc->2617}} 13466917 1 {{ac->2241,bc->2906}} 20996011 3 {} 24036583 3 {} 25964951 3 {} 30402457 1 {{ac->3291,bc->4424}} 32582657 1 {{ac->3536,bc->4481}} 37156667 3 {} 42643801 1 {{ac->285,bc->6524}} 43112609 1 {{ac->3880,bc->5297}} 57885161 1 {{ac->2444,bc->7205}} 74207281 1 {{ac->2716,bc->8175}} 77232917 1 {{ac->2329,bc->8474}} 82589933 1 {{ac->5122,bc->7507}}
2022-05-06, 18:19   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

990110 Posts

Quote:
 Originally Posted by Gelly I want to save the trouble for anyone else interested in finding a sum of squares decomposition given only the fact that the number is 1 mod 4 and nothing else - no factorization, nothing. Here is the jstor link. https://www.jstor.org/stable/2005889
Please explain why would you want to factor a prime number?
What you quoted is for "number is 1 mod 4 and nothing else prime".

2022-05-06, 19:58   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

262378 Posts

Quote:
 Originally Posted by Batalov Please explain why would you want to factor a prime number? What you quoted is for "number is 1 mod 4 and nothing else prime".
Factoring into complex primes?

One of the prized books in my library is a table of complex primes. Cost me all of 10p about 40 years ago.

Handbook for First Complex Numbers, Part One 1 List of First 332,395 Complex Prime Numbers by Kogbetliantz and Krikorian

to be precise.

2022-05-06, 22:33   #7
Gelly

May 2020

47 Posts

Quote:
 Originally Posted by Batalov Please explain why would you want to factor a prime number? What you quoted is for "number is 1 mod 4 and nothing else prime".
My mistake! I am interested in composites, personally, so evidently I'm having a hard time finding the resources for this even with the hour of research I put in!

Can you just tell us the magic words to find the sum of two squares decomposition for composites? Or do you also not know and assumed it would be easy to find on google? I really truly want to know how it works, considering I remember a while ago that PARI/GP had some function for it with an esoteric name.

 2022-05-06, 23:35 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,901 Posts Step 1. You factor n. ("there is no royal road to geometry, your excellency" (c) Euclid) Step 2. If there is a prime factor ≡ 3{mod 4} repeated odd number of times? - then Stop. No solution. Step 3. There are established algorithms. Wiki has a short explanation (see post #2 (!!) ); then just one jump via Wiki to OEIS; then use OEIS links. . . . . . . Ok, here is at least one way: solve each prime factor for sum of squares. then combine them using https://en.wikipedia.org/wiki/Brahma...nacci_identity Either way. The OP asked for "fast" way. The answer to that is elegant and easy - there is no fast way.
2022-05-07, 00:26   #9
bhelmes

Mar 2016

22×101 Posts

Quote:
 Originally Posted by Batalov Either way. The OP asked for "fast" way. The answer to that is elegant and easy - there is no fast way.
I only needed one composition and the algorithm is described under
https://en.wikipedia.org/wiki/Fermat...of_two_squares

The english version of wikipedia is much better than the german, where no algorithm is indicated.

Corona time was not funny, the war in Ukraine ugly and perhaps my question was a try to cheer you up.

2022-05-07, 12:05   #10
Dr Sardonicus

Feb 2017
Nowhere

170916 Posts

Quote:
 Originally Posted by Gelly My mistake! I am interested in composites, personally, so evidently I'm having a hard time finding the resources for this even with the hour of research I put in!
If you want to know the decomposition(s) of a composite number into a sum of two squares, in general you need to factor the number. You certainly need the factorization if you want to be sure of having all the decompositions.

There are situations where you have one decomposition "by formula," e.g. Fermat numbers.

Pari-GP's qfbsolve(Q, n) function now works for composite n (it used to work only for prime n).

Another function that works for composite n (assuming Pari-GP can find the factorization) is bnfisintnorm(). You first have to define the number field k = Q(i) where i^2 + 1 = 0. This function in effect gives each representation twice.

Code:
? Q=Qfb(1,0,1);v=qfbsolve(Q,1009)
%1 = [28, 15]

? k=bnfinit(t^2+1);bnfisintnorm(k,1009)
%2 = [15*t - 28, 15*t + 28]

? bnfisintnorm(k,1105)
%3 = [-33*t + 4, 31*t + 12, 32*t + 9, -24*t - 23, 23*t + 24, -9*t - 32, -12*t - 31, -4*t + 33]
?

 2022-05-07, 20:04 #11 Gelly     May 2020 47 Posts Oh shoot my mistake! I'm sure I come off super foolish now that I remember what the particular context was. It seems like to get the sum of squares representation of any composite requires factorization, and I thought that was wrong because we know the sum of squares representation of C1133, the large composite factor of F12. But that method requires it to be a factor of a Fermat number, and to know the cofactors! Super sorry to be so pushy about it! Thank you all for the help for the true answer.

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

Sat Aug 13 19:23:30 UTC 2022 up 37 days, 14:10, 2 users, load averages: 0.66, 0.98, 1.05