Can the sum of two squares be used to determine if a number is square free?
$begingroup$
Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."
Below we provide a simple method to check if a number is square free and provide the square part if it is not.
We start with two simple examples to show how the square part can be determined. We consider $N=3^2*13=117$ and find its sum of two square representation (2sq rep) $N=a^2 + b^2$. $N=3^2*13=117=6^2 + 9^2$. We immediately notice that the square part $3^2$ is common to both $a$ and $b$.
To check that this result is general, we calculate the 2sq rep of $N=3^2*17=153$. We find $N=153=3^2 + 12^2$. And here too we see that $3^2$ is common to both $a$ and $b$.
To check that the previous result is not specific to the $N=117$, we do the same with $N=5*7^2=245=7^2 + 14^2$. Here too, we see that the square part $7^2$ is common to both $a$ and $b$.
The three previous examples have only one 2sq rep. So we need to show that the method works for integers $N$ with more than one 2sq rep. We calculate the 2sq rep for $N=13^2*17=2873=8^2 + 53^2=13^2 + 52^2=32^2 + 43^2$. It is clear that the second 2sq rep $13^2+52^2$ is the one conveying the information on the square part $q^2$. With large integers, one can use the GCD(a^2,b^2) to find the 2sq rep that conveys the information.
We provide now an example of a number $N$ with $3$ factors, only one of which is a square. $N=3^2*5*13=585=12^2 + 21^2= 3^2 + 24^2$. Again, it's clear from this simple example that both representations have the common factor $3^2$.
We now provide an example of a number $N$ with 3 factors but two of which are squares. $N=3^2*5^2*13=2925=3^2 + 54^2=18^2 + 51^2 = 30^2 + 45^2$. It's clear that both $3^2$ and $5^2$ appear in at least one 2sq representation.
For completeness and to answer a question by Somos, we show that it is possible to find if a number $N=3*q^2$ is square free or square full. It is obvious that $N=3*q^2$ does not admit a 2sq rep.
However, if we square the number $N$ to get $N^2=M=9*q^4$, we will be able to show that $N$ was square full. We give the following example: $N=3*5^2$. We take the square to get $N^2=3^2*5^4=21^2 + 72^2=45^2 + 60^2$. It is easy to show that $21^2+72^2=3^2*7^2 + 3^2*24^2=3^2*(7^2+24^2)=3^2*25^2$. Now by taking the square root we get the original number $N=3*25=3*5^2$. We can do the same with the other 2sq rep.
This is of course not a proof that the 2sq rep of an integer will show either that N is square-free or has one square factor (or more). But the numerical evidence suggests that the 2sq rep does in fact provide the information on the square-free and square-full status of an integer. There was no need to factor the integer to find if it is square-free or square-full. Large numbers were not considered because all calculations were done by hand (I can't code). No theorem was proved because I simply don't know enough to provide a solid mathematical foundation to the method.
Any help with the proof and any help with more numerical evidence will be much appreciated.
When calculating the 2sq rep's, it is important to find all of them to make sure that the important one with the information is not missed.
I can't make any statement on how efficient the method is compared to others or on how it relates to other areas of mathematics.
number-theory elementary-number-theory prime-numbers prime-factorization sums-of-squares
asked Jan 6 at 16:25
user25406user25406
3841413
$endgroup$
|
show 5 more comments
$begingroup$
Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."
Below we provide a simple method to check if a number is square free and provide the square part if it is not.
We start with two simple examples to show how the square part can be determined. We consider $N=3^2*13=117$ and find its sum of two square representation (2sq rep) $N=a^2 + b^2$. $N=3^2*13=117=6^2 + 9^2$. We immediately notice that the square part $3^2$ is common to both $a$ and $b$.
To check that this result is general, we calculate the 2sq rep of $N=3^2*17=153$. We find $N=153=3^2 + 12^2$. And here too we see that $3^2$ is common to both $a$ and $b$.
To check that the previous result is not specific to the $N=117$, we do the same with $N=5*7^2=245=7^2 + 14^2$. Here too, we see that the square part $7^2$ is common to both $a$ and $b$.
The three previous examples have only one 2sq rep. So we need to show that the method works for integers $N$ with more than one 2sq rep. We calculate the 2sq rep for $N=13^2*17=2873=8^2 + 53^2=13^2 + 52^2=32^2 + 43^2$. It is clear that the second 2sq rep $13^2+52^2$ is the one conveying the information on the square part $q^2$. With large integers, one can use the GCD(a^2,b^2) to find the 2sq rep that conveys the information.
We provide now an example of a number $N$ with $3$ factors, only one of which is a square. $N=3^2*5*13=585=12^2 + 21^2= 3^2 + 24^2$. Again, it's clear from this simple example that both representations have the common factor $3^2$.
We now provide an example of a number $N$ with 3 factors but two of which are squares. $N=3^2*5^2*13=2925=3^2 + 54^2=18^2 + 51^2 = 30^2 + 45^2$. It's clear that both $3^2$ and $5^2$ appear in at least one 2sq representation.
For completeness and to answer a question by Somos, we show that it is possible to find if a number $N=3*q^2$ is square free or square full. It is obvious that $N=3*q^2$ does not admit a 2sq rep.
However, if we square the number $N$ to get $N^2=M=9*q^4$, we will be able to show that $N$ was square full. We give the following example: $N=3*5^2$. We take the square to get $N^2=3^2*5^4=21^2 + 72^2=45^2 + 60^2$. It is easy to show that $21^2+72^2=3^2*7^2 + 3^2*24^2=3^2*(7^2+24^2)=3^2*25^2$. Now by taking the square root we get the original number $N=3*25=3*5^2$. We can do the same with the other 2sq rep.
This is of course not a proof that the 2sq rep of an integer will show either that N is square-free or has one square factor (or more). But the numerical evidence suggests that the 2sq rep does in fact provide the information on the square-free and square-full status of an integer. There was no need to factor the integer to find if it is square-free or square-full. Large numbers were not considered because all calculations were done by hand (I can't code). No theorem was proved because I simply don't know enough to provide a solid mathematical foundation to the method.
Any help with the proof and any help with more numerical evidence will be much appreciated.
When calculating the 2sq rep's, it is important to find all of them to make sure that the important one with the information is not missed.
I can't make any statement on how efficient the method is compared to others or on how it relates to other areas of mathematics.
number-theory elementary-number-theory prime-numbers prime-factorization sums-of-squares
asked Jan 6 at 16:25
user25406user25406
3841413
$endgroup$
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
2
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45
|
show 5 more comments
$begingroup$
Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."
Below we provide a simple method to check if a number is square free and provide the square part if it is not.
We start with two simple examples to show how the square part can be determined. We consider $N=3^2*13=117$ and find its sum of two square representation (2sq rep) $N=a^2 + b^2$. $N=3^2*13=117=6^2 + 9^2$. We immediately notice that the square part $3^2$ is common to both $a$ and $b$.
To check that this result is general, we calculate the 2sq rep of $N=3^2*17=153$. We find $N=153=3^2 + 12^2$. And here too we see that $3^2$ is common to both $a$ and $b$.
To check that the previous result is not specific to the $N=117$, we do the same with $N=5*7^2=245=7^2 + 14^2$. Here too, we see that the square part $7^2$ is common to both $a$ and $b$.
The three previous examples have only one 2sq rep. So we need to show that the method works for integers $N$ with more than one 2sq rep. We calculate the 2sq rep for $N=13^2*17=2873=8^2 + 53^2=13^2 + 52^2=32^2 + 43^2$. It is clear that the second 2sq rep $13^2+52^2$ is the one conveying the information on the square part $q^2$. With large integers, one can use the GCD(a^2,b^2) to find the 2sq rep that conveys the information.
We provide now an example of a number $N$ with $3$ factors, only one of which is a square. $N=3^2*5*13=585=12^2 + 21^2= 3^2 + 24^2$. Again, it's clear from this simple example that both representations have the common factor $3^2$.
We now provide an example of a number $N$ with 3 factors but two of which are squares. $N=3^2*5^2*13=2925=3^2 + 54^2=18^2 + 51^2 = 30^2 + 45^2$. It's clear that both $3^2$ and $5^2$ appear in at least one 2sq representation.
For completeness and to answer a question by Somos, we show that it is possible to find if a number $N=3*q^2$ is square free or square full. It is obvious that $N=3*q^2$ does not admit a 2sq rep.
However, if we square the number $N$ to get $N^2=M=9*q^4$, we will be able to show that $N$ was square full. We give the following example: $N=3*5^2$. We take the square to get $N^2=3^2*5^4=21^2 + 72^2=45^2 + 60^2$. It is easy to show that $21^2+72^2=3^2*7^2 + 3^2*24^2=3^2*(7^2+24^2)=3^2*25^2$. Now by taking the square root we get the original number $N=3*25=3*5^2$. We can do the same with the other 2sq rep.
This is of course not a proof that the 2sq rep of an integer will show either that N is square-free or has one square factor (or more). But the numerical evidence suggests that the 2sq rep does in fact provide the information on the square-free and square-full status of an integer. There was no need to factor the integer to find if it is square-free or square-full. Large numbers were not considered because all calculations were done by hand (I can't code). No theorem was proved because I simply don't know enough to provide a solid mathematical foundation to the method.
Any help with the proof and any help with more numerical evidence will be much appreciated.
When calculating the 2sq rep's, it is important to find all of them to make sure that the important one with the information is not missed.
I can't make any statement on how efficient the method is compared to others or on how it relates to other areas of mathematics.
number-theory elementary-number-theory prime-numbers prime-factorization sums-of-squares
asked Jan 6 at 16:25
user25406user25406
3841413
$endgroup$
Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."
Below we provide a simple method to check if a number is square free and provide the square part if it is not.
We start with two simple examples to show how the square part can be determined. We consider $N=3^2*13=117$ and find its sum of two square representation (2sq rep) $N=a^2 + b^2$. $N=3^2*13=117=6^2 + 9^2$. We immediately notice that the square part $3^2$ is common to both $a$ and $b$.
To check that this result is general, we calculate the 2sq rep of $N=3^2*17=153$. We find $N=153=3^2 + 12^2$. And here too we see that $3^2$ is common to both $a$ and $b$.
To check that the previous result is not specific to the $N=117$, we do the same with $N=5*7^2=245=7^2 + 14^2$. Here too, we see that the square part $7^2$ is common to both $a$ and $b$.
The three previous examples have only one 2sq rep. So we need to show that the method works for integers $N$ with more than one 2sq rep. We calculate the 2sq rep for $N=13^2*17=2873=8^2 + 53^2=13^2 + 52^2=32^2 + 43^2$. It is clear that the second 2sq rep $13^2+52^2$ is the one conveying the information on the square part $q^2$. With large integers, one can use the GCD(a^2,b^2) to find the 2sq rep that conveys the information.
We provide now an example of a number $N$ with $3$ factors, only one of which is a square. $N=3^2*5*13=585=12^2 + 21^2= 3^2 + 24^2$. Again, it's clear from this simple example that both representations have the common factor $3^2$.
We now provide an example of a number $N$ with 3 factors but two of which are squares. $N=3^2*5^2*13=2925=3^2 + 54^2=18^2 + 51^2 = 30^2 + 45^2$. It's clear that both $3^2$ and $5^2$ appear in at least one 2sq representation.
For completeness and to answer a question by Somos, we show that it is possible to find if a number $N=3*q^2$ is square free or square full. It is obvious that $N=3*q^2$ does not admit a 2sq rep.
However, if we square the number $N$ to get $N^2=M=9*q^4$, we will be able to show that $N$ was square full. We give the following example: $N=3*5^2$. We take the square to get $N^2=3^2*5^4=21^2 + 72^2=45^2 + 60^2$. It is easy to show that $21^2+72^2=3^2*7^2 + 3^2*24^2=3^2*(7^2+24^2)=3^2*25^2$. Now by taking the square root we get the original number $N=3*25=3*5^2$. We can do the same with the other 2sq rep.
This is of course not a proof that the 2sq rep of an integer will show either that N is square-free or has one square factor (or more). But the numerical evidence suggests that the 2sq rep does in fact provide the information on the square-free and square-full status of an integer. There was no need to factor the integer to find if it is square-free or square-full. Large numbers were not considered because all calculations were done by hand (I can't code). No theorem was proved because I simply don't know enough to provide a solid mathematical foundation to the method.
Any help with the proof and any help with more numerical evidence will be much appreciated.
When calculating the 2sq rep's, it is important to find all of them to make sure that the important one with the information is not missed.
I can't make any statement on how efficient the method is compared to others or on how it relates to other areas of mathematics.
number-theory elementary-number-theory prime-numbers prime-factorization sums-of-squares
number-theory elementary-number-theory prime-numbers prime-factorization sums-of-squares
asked Jan 6 at 16:25
user25406user25406
3841413
asked Jan 6 at 16:25
user25406user25406
3841413
edited Jan 11 at 13:46
user25406
asked Jan 6 at 16:25
user25406user25406
3841413
asked Jan 6 at 16:25
user25406user25406
3841413
asked Jan 6 at 16:25
user25406user25406
3841413
3841413
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
2
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45
|
show 5 more comments
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
2
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
2
2
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45
|
show 5 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064068%2fcan-the-sum-of-two-squares-be-used-to-determine-if-a-number-is-square-free%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064068%2fcan-the-sum-of-two-squares-be-used-to-determine-if-a-number-is-square-free%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What about $N=3q^2$?
$endgroup$
– Somos
Jan 6 at 16:55
$begingroup$
in this case, you won't be able to find a 2sq rep. To get around that, one can square $N=(3q^2)^2=3^2q^4$ and get the information on $q^2$ from the 2sq rep.
$endgroup$
– user25406
Jan 6 at 17:01
$begingroup$
So, in worst case you have to find $N^2=a^2+b^2$ which is an $O(N)$ operation. You may as well find prime factorization of $N$ by trial division up to $sqrt{N}$.
$endgroup$
– Somos
Jan 6 at 17:06
$begingroup$
Just to make sure, you want to base the result on the list of ALL different ways of writing $N$ as a sum of two squares?? A single such representation need not show anything, $25=4^2+3^2$ being the smallest example of that
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:35
2
$begingroup$
That result implies that if $p^2mid N$ for some prime $p$, and $N$ has a presentation as a sum of two squares, then so does $m=N/p^2$. So $m=a^2+b^2$ for some integers $a,b$. But this implies that $$N=p^2m=(pa)^2+(pb)^2, $$ which is exactly the kind of presentation you seem to be looking for, proving that $p^2mid N$.
$endgroup$
– Jyrki Lahtonen
Jan 7 at 14:45