Show that the sum or difference of $a_i$ and $a_j$ from a set of seven distinct integers is divisible by 10












1












$begingroup$


I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show?



Here's my intuition on how to prove this:
$a_i$ and $a_j$ can be decomposed as a sum of multiples of powers of $10$ since we're working in base $10$. When we add or subtract $a_i$ and $a_j$ from each other we want to show that their remainder is zero using the pigeonhole principle.



Is this a correct way of looking at it?



Thanks.






elementary-number-theory pigeonhole-principle







share|cite|improve this question









$endgroup$












  • $begingroup$
    Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
    $endgroup$
    – coffeemath
    Jan 13 at 23:50
















1












$begingroup$


I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show?



Here's my intuition on how to prove this:
$a_i$ and $a_j$ can be decomposed as a sum of multiples of powers of $10$ since we're working in base $10$. When we add or subtract $a_i$ and $a_j$ from each other we want to show that their remainder is zero using the pigeonhole principle.



Is this a correct way of looking at it?



Thanks.






elementary-number-theory pigeonhole-principle







share|cite|improve this question









$endgroup$












  • $begingroup$
    Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
    $endgroup$
    – coffeemath
    Jan 13 at 23:50














1












1








1


0



$begingroup$


I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show?



Here's my intuition on how to prove this:
$a_i$ and $a_j$ can be decomposed as a sum of multiples of powers of $10$ since we're working in base $10$. When we add or subtract $a_i$ and $a_j$ from each other we want to show that their remainder is zero using the pigeonhole principle.



Is this a correct way of looking at it?



Thanks.






elementary-number-theory pigeonhole-principle







share|cite|improve this question









$endgroup$




I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show?



Here's my intuition on how to prove this:
$a_i$ and $a_j$ can be decomposed as a sum of multiples of powers of $10$ since we're working in base $10$. When we add or subtract $a_i$ and $a_j$ from each other we want to show that their remainder is zero using the pigeonhole principle.



Is this a correct way of looking at it?



Thanks.






elementary-number-theory pigeonhole-principle




elementary-number-theory pigeonhole-principle






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 13 at 23:43









jd94jd94

31917




31917












  • $begingroup$
    Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
    $endgroup$
    – coffeemath
    Jan 13 at 23:50


















  • $begingroup$
    Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
    $endgroup$
    – coffeemath
    Jan 13 at 23:50
















$begingroup$
Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
$endgroup$
– coffeemath
Jan 13 at 23:50




$begingroup$
Note that if reduced mod 10 there can be repeats. [so the reduced numbers might not be distinct] Also does it mean there is a sum div by 10 and also a difference div by 10, or does it mean either a sum div by 10 or a difference div by 10?
$endgroup$
– coffeemath
Jan 13 at 23:50










1 Answer
1






active

oldest

votes


















3












$begingroup$

The idea behind that proof is that
$$0=a_i^2-a_j^2 =(a_i-a_j)(a_i+a_j) pmod{10}$$



Then at least one of $(a_i-a_j),(a_i+a_j)$ is divisible by $2$ and at least one is divisible by $5$. Now show that $(a_i-a_j)$ and $(a_i+a_j) $ have the same parity.



Your idea also works:



Split the seven numbers among the following $6$ boxes:



$${ 1,9 pmod{10} } ; { 2,8 pmod{10} } ; { 3,7 pmod{10} } \ { 4,6 pmod{10} } ; { 5 pmod{10} } ; { 0 pmod{10} }$$



Then at least one box contains two numbers. If the two numbers in the same box are congruent $pmod{10}$, then their difference is divisible by $10$. Otherwise, their sum is divisible by 10.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Why is the difference of squares congruent to 0 (mod 10)?
    $endgroup$
    – jd94
    Jan 13 at 23:56










  • $begingroup$
    @user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
    $endgroup$
    – N. S.
    Jan 14 at 0:01












Your Answer








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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072679%2fshow-that-the-sum-or-difference-of-a-i-and-a-j-from-a-set-of-seven-distinct%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









3












$begingroup$

The idea behind that proof is that
$$0=a_i^2-a_j^2 =(a_i-a_j)(a_i+a_j) pmod{10}$$



Then at least one of $(a_i-a_j),(a_i+a_j)$ is divisible by $2$ and at least one is divisible by $5$. Now show that $(a_i-a_j)$ and $(a_i+a_j) $ have the same parity.



Your idea also works:



Split the seven numbers among the following $6$ boxes:



$${ 1,9 pmod{10} } ; { 2,8 pmod{10} } ; { 3,7 pmod{10} } \ { 4,6 pmod{10} } ; { 5 pmod{10} } ; { 0 pmod{10} }$$



Then at least one box contains two numbers. If the two numbers in the same box are congruent $pmod{10}$, then their difference is divisible by $10$. Otherwise, their sum is divisible by 10.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Why is the difference of squares congruent to 0 (mod 10)?
    $endgroup$
    – jd94
    Jan 13 at 23:56










  • $begingroup$
    @user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
    $endgroup$
    – N. S.
    Jan 14 at 0:01
















3












$begingroup$

The idea behind that proof is that
$$0=a_i^2-a_j^2 =(a_i-a_j)(a_i+a_j) pmod{10}$$



Then at least one of $(a_i-a_j),(a_i+a_j)$ is divisible by $2$ and at least one is divisible by $5$. Now show that $(a_i-a_j)$ and $(a_i+a_j) $ have the same parity.



Your idea also works:



Split the seven numbers among the following $6$ boxes:



$${ 1,9 pmod{10} } ; { 2,8 pmod{10} } ; { 3,7 pmod{10} } \ { 4,6 pmod{10} } ; { 5 pmod{10} } ; { 0 pmod{10} }$$



Then at least one box contains two numbers. If the two numbers in the same box are congruent $pmod{10}$, then their difference is divisible by $10$. Otherwise, their sum is divisible by 10.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Why is the difference of squares congruent to 0 (mod 10)?
    $endgroup$
    – jd94
    Jan 13 at 23:56










  • $begingroup$
    @user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
    $endgroup$
    – N. S.
    Jan 14 at 0:01














3












3








3





$begingroup$

The idea behind that proof is that
$$0=a_i^2-a_j^2 =(a_i-a_j)(a_i+a_j) pmod{10}$$



Then at least one of $(a_i-a_j),(a_i+a_j)$ is divisible by $2$ and at least one is divisible by $5$. Now show that $(a_i-a_j)$ and $(a_i+a_j) $ have the same parity.



Your idea also works:



Split the seven numbers among the following $6$ boxes:



$${ 1,9 pmod{10} } ; { 2,8 pmod{10} } ; { 3,7 pmod{10} } \ { 4,6 pmod{10} } ; { 5 pmod{10} } ; { 0 pmod{10} }$$



Then at least one box contains two numbers. If the two numbers in the same box are congruent $pmod{10}$, then their difference is divisible by $10$. Otherwise, their sum is divisible by 10.






share|cite|improve this answer









$endgroup$



The idea behind that proof is that
$$0=a_i^2-a_j^2 =(a_i-a_j)(a_i+a_j) pmod{10}$$



Then at least one of $(a_i-a_j),(a_i+a_j)$ is divisible by $2$ and at least one is divisible by $5$. Now show that $(a_i-a_j)$ and $(a_i+a_j) $ have the same parity.



Your idea also works:



Split the seven numbers among the following $6$ boxes:



$${ 1,9 pmod{10} } ; { 2,8 pmod{10} } ; { 3,7 pmod{10} } \ { 4,6 pmod{10} } ; { 5 pmod{10} } ; { 0 pmod{10} }$$



Then at least one box contains two numbers. If the two numbers in the same box are congruent $pmod{10}$, then their difference is divisible by $10$. Otherwise, their sum is divisible by 10.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 13 at 23:50









N. S.N. S.

105k7116210




105k7116210












  • $begingroup$
    Why is the difference of squares congruent to 0 (mod 10)?
    $endgroup$
    – jd94
    Jan 13 at 23:56










  • $begingroup$
    @user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
    $endgroup$
    – N. S.
    Jan 14 at 0:01


















  • $begingroup$
    Why is the difference of squares congruent to 0 (mod 10)?
    $endgroup$
    – jd94
    Jan 13 at 23:56










  • $begingroup$
    @user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
    $endgroup$
    – N. S.
    Jan 14 at 0:01
















$begingroup$
Why is the difference of squares congruent to 0 (mod 10)?
$endgroup$
– jd94
Jan 13 at 23:56




$begingroup$
Why is the difference of squares congruent to 0 (mod 10)?
$endgroup$
– jd94
Jan 13 at 23:56












$begingroup$
@user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
$endgroup$
– N. S.
Jan 14 at 0:01




$begingroup$
@user2965071 That's exactly what the answer you posted shows: that there exists some $i,j$ such that $$a_i^2 equiv a_j^2 pmod{10}$$
$endgroup$
– N. S.
Jan 14 at 0:01


















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072679%2fshow-that-the-sum-or-difference-of-a-i-and-a-j-from-a-set-of-seven-distinct%23new-answer', 'question_page');
}
);

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







-

Popular posts from this blog

Bressuire

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more

Cabo Verde

Image
  Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
Read more

Gyllenstierna

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more