mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2022-05-04, 23:38   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

24×52 Posts
Default 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.

bhelmes is offline   Reply With Quote
Old 2022-05-05, 00:55   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100110100010002 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Using Google is too hard?
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"?
Batalov is offline   Reply With Quote
Old 2022-05-06, 11:25   #3
Gelly
 
Gelly's Avatar
 
May 2020

47 Posts
Default

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.
Gelly is offline   Reply With Quote
Old 2022-05-06, 16:01   #4
Dobri
 
"Καλός"
May 2018

17·19 Posts
Default

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}}
Dobri is offline   Reply With Quote
Old 2022-05-06, 18:19   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100110100010002 Posts
Default

Quote:
Originally Posted by Gelly View Post
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".
Batalov is offline   Reply With Quote
Old 2022-05-06, 19:58   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

1138710 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
xilman is online now   Reply With Quote
Old 2022-05-06, 22:33   #7
Gelly
 
Gelly's Avatar
 
May 2020

1011112 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
Gelly is offline   Reply With Quote
Old 2022-05-06, 23:35   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×32×137 Posts
Lightbulb

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.
Batalov is offline   Reply With Quote
Old 2022-05-07, 00:26   #9
bhelmes
 
bhelmes's Avatar
 
Mar 2016

24×52 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.

bhelmes is offline   Reply With Quote
Old 2022-05-07, 12:05   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·1,459 Posts
Default

Quote:
Originally Posted by Gelly View Post
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!
<snip>
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]
?
Dr Sardonicus is offline   Reply With Quote
Old 2022-05-07, 20:04   #11
Gelly
 
Gelly's Avatar
 
May 2020

47 Posts
Default

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.
Gelly is offline   Reply With Quote
Reply

Thread Tools


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


Wed Jul 6 12:32:04 UTC 2022 up 83 days, 10:33, 0 users, load averages: 1.54, 1.23, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔