Proving expressions mod 13
Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2equiv 0pmod {13}$
He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$.
I did a similar problem to prove that $13|2a+3biff 13|3a-2b$ using a special algebra trick.
I cannot find a trick here though to manipulate the expressions.
I can solve it by looking at all possible values of $a^2pmod {13}$ and then verifying that these work.
But I want to know if there is a more elegant solution using an algebra trick.
number-theory modular-arithmetic divisibility
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
asked Dec 26 at 0:59
user627514
323
add a comment |
Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2equiv 0pmod {13}$
He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$.
I did a similar problem to prove that $13|2a+3biff 13|3a-2b$ using a special algebra trick.
I cannot find a trick here though to manipulate the expressions.
I can solve it by looking at all possible values of $a^2pmod {13}$ and then verifying that these work.
But I want to know if there is a more elegant solution using an algebra trick.
number-theory modular-arithmetic divisibility
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
asked Dec 26 at 0:59
user627514
323
add a comment |
Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2equiv 0pmod {13}$
He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$.
I did a similar problem to prove that $13|2a+3biff 13|3a-2b$ using a special algebra trick.
I cannot find a trick here though to manipulate the expressions.
I can solve it by looking at all possible values of $a^2pmod {13}$ and then verifying that these work.
But I want to know if there is a more elegant solution using an algebra trick.
number-theory modular-arithmetic divisibility
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
asked Dec 26 at 0:59
user627514
323
Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2equiv 0pmod {13}$
He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$.
I did a similar problem to prove that $13|2a+3biff 13|3a-2b$ using a special algebra trick.
I cannot find a trick here though to manipulate the expressions.
I can solve it by looking at all possible values of $a^2pmod {13}$ and then verifying that these work.
But I want to know if there is a more elegant solution using an algebra trick.
number-theory modular-arithmetic divisibility
number-theory modular-arithmetic divisibility
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
asked Dec 26 at 0:59
user627514
323
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
asked Dec 26 at 0:59
user627514
323
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
edited Dec 26 at 1:00
Carl Schildkraut
11.1k11441
11.1k11441
asked Dec 26 at 0:59
user627514
323
asked Dec 26 at 0:59
user627514
323
asked Dec 26 at 0:59
user627514
323
323
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Hint: If $aequiv 0pmod{13}$ then $bequiv 0bmod 13$ as well. Now, assume this is not the case. Then
$$a^2+b^2equiv 0bmod 13 implies left(frac{a}{b}right)^2+1equiv 0bmod 13.$$
See that the square roots of $-1bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...
Can you finish from here?
edited Dec 26 at 1:16
steven gregory
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
add a comment |
From $13|2a+3biff 13|3a-2b$, we can write
begin{align*}
(3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) mod 13 = 0 mod 13
end{align*}
Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.
answered Dec 26 at 1:26
Muralidharan
47516
add a comment |
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%2f3052553%2fproving-expressions-mod-13%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Hint: If $aequiv 0pmod{13}$ then $bequiv 0bmod 13$ as well. Now, assume this is not the case. Then
$$a^2+b^2equiv 0bmod 13 implies left(frac{a}{b}right)^2+1equiv 0bmod 13.$$
See that the square roots of $-1bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...
Can you finish from here?
edited Dec 26 at 1:16
steven gregory
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
add a comment |
Hint: If $aequiv 0pmod{13}$ then $bequiv 0bmod 13$ as well. Now, assume this is not the case. Then
$$a^2+b^2equiv 0bmod 13 implies left(frac{a}{b}right)^2+1equiv 0bmod 13.$$
See that the square roots of $-1bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...
Can you finish from here?
edited Dec 26 at 1:16
steven gregory
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
add a comment |
Hint: If $aequiv 0pmod{13}$ then $bequiv 0bmod 13$ as well. Now, assume this is not the case. Then
$$a^2+b^2equiv 0bmod 13 implies left(frac{a}{b}right)^2+1equiv 0bmod 13.$$
See that the square roots of $-1bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...
Can you finish from here?
edited Dec 26 at 1:16
steven gregory
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
Hint: If $aequiv 0pmod{13}$ then $bequiv 0bmod 13$ as well. Now, assume this is not the case. Then
$$a^2+b^2equiv 0bmod 13 implies left(frac{a}{b}right)^2+1equiv 0bmod 13.$$
See that the square roots of $-1bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...
Can you finish from here?
edited Dec 26 at 1:16
steven gregory
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
edited Dec 26 at 1:16
steven gregory
17.7k32257
edited Dec 26 at 1:16
steven gregory
17.7k32257
edited Dec 26 at 1:16
steven gregory
17.7k32257
17.7k32257
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
answered Dec 26 at 1:03
Carl Schildkraut
11.1k11441
11.1k11441
add a comment |
add a comment |
From $13|2a+3biff 13|3a-2b$, we can write
begin{align*}
(3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) mod 13 = 0 mod 13
end{align*}
Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.
answered Dec 26 at 1:26
Muralidharan
47516
add a comment |
From $13|2a+3biff 13|3a-2b$, we can write
begin{align*}
(3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) mod 13 = 0 mod 13
end{align*}
Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.
answered Dec 26 at 1:26
Muralidharan
47516
add a comment |
From $13|2a+3biff 13|3a-2b$, we can write
begin{align*}
(3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) mod 13 = 0 mod 13
end{align*}
Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.
answered Dec 26 at 1:26
Muralidharan
47516
From $13|2a+3biff 13|3a-2b$, we can write
begin{align*}
(3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) mod 13 = 0 mod 13
end{align*}
Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.
answered Dec 26 at 1:26
Muralidharan
47516
answered Dec 26 at 1:26
Muralidharan
47516
answered Dec 26 at 1:26
Muralidharan
47516
answered Dec 26 at 1:26
Muralidharan
47516
47516
add a comment |
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3052553%2fproving-expressions-mod-13%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
