$begingroup$
What I am trying to achieve, is related to cryptography/blockchain/bitcoin . So, the largest number here is huge, in other words: I want to find the largest multiple of 7, which is lower than this number:
$115792089237316195423570985008687907852837564279074904382605163141518161494336 $
I can just go to Wolfram Alpha, and type "multiples of 7", and I get a list of the multiples relatively fast. But, it will take some time until I keep hitting "more", to get to a number lower than this above.
elementary-number-theory modular-arithmetic arithmetic
edited 48 mins ago
Glorfindel
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 2 more comments
$begingroup$
What I am trying to achieve, is related to cryptography/blockchain/bitcoin . So, the largest number here is huge, in other words: I want to find the largest multiple of 7, which is lower than this number:
$115792089237316195423570985008687907852837564279074904382605163141518161494336 $
I can just go to Wolfram Alpha, and type "multiples of 7", and I get a list of the multiples relatively fast. But, it will take some time until I keep hitting "more", to get to a number lower than this above.
elementary-number-theory modular-arithmetic arithmetic
edited 48 mins ago
Glorfindel
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago
|
show 2 more comments
$begingroup$
What I am trying to achieve, is related to cryptography/blockchain/bitcoin . So, the largest number here is huge, in other words: I want to find the largest multiple of 7, which is lower than this number:
$115792089237316195423570985008687907852837564279074904382605163141518161494336 $
I can just go to Wolfram Alpha, and type "multiples of 7", and I get a list of the multiples relatively fast. But, it will take some time until I keep hitting "more", to get to a number lower than this above.
elementary-number-theory modular-arithmetic arithmetic
edited 48 mins ago
Glorfindel
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
What I am trying to achieve, is related to cryptography/blockchain/bitcoin . So, the largest number here is huge, in other words: I want to find the largest multiple of 7, which is lower than this number:
$115792089237316195423570985008687907852837564279074904382605163141518161494336 $
I can just go to Wolfram Alpha, and type "multiples of 7", and I get a list of the multiples relatively fast. But, it will take some time until I keep hitting "more", to get to a number lower than this above.
elementary-number-theory modular-arithmetic arithmetic
elementary-number-theory modular-arithmetic arithmetic
edited 48 mins ago
Glorfindel
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 48 mins ago
Glorfindel
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 48 mins ago
Glorfindel
3,42781830
edited 48 mins ago
Glorfindel
3,42781830
edited 48 mins ago
Glorfindel
3,42781830
3,42781830
asked 5 hours ago
kpopguykpopguy
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
kpopguykpopguy
304
asked 5 hours ago
kpopguykpopguy
304
304
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
kpopguy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago
|
show 2 more comments
$begingroup$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago
$begingroup$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
1
1
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
1
1
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
One can compute this number $a$ modulo $7$. The result is $2bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
$endgroup$
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
add a comment |
$begingroup$
$$begin{array}{cccccc}115792&089237&316195&423570&985008&687907\852837&564279&074904&382605&163141&518161\494336end{array}$$
Sum up the places of these numbers, by place value carrying when needed, then apply $10^kequiv 3^k bmod 7$ you'll then have a much smaller number to find the remainder of that's equivalent.
5667972, which goes to :$$6(3^5)+6(3^4)+2(3^2)equiv 1458+486+18equiv 2+3+4equiv 2 bmod 7$$ so the largest multiple of 7, is 2 less than the number. Yes, this is a slightly tedious way to go, but it's inspired via extension of Fermat's little theorem, and polynomial remainder theorem.
The reason I broke it into 6 digits at a time, is because Fermat's extension, is that exponents that have the same remainder mod p-1, will give back the same remainder with the same base. That means you can simply turn one into the other, adding like terms. you then go and do the addition the first column on the right sums to 62, carry the 6, that means you sum the next column plus 6, giving 57 carry the 5, next column is then 59, carry the 5, next column 67, carry the 6, next column, 76 carry the 7, next column, 56 there's no column to carry the 5 onto, and in the next step, it will be merged with the 2 (6 digits before), and then tossed because 7 creates a term that is 0 mod 7. Doing the same to other 7's and the nine gives 660200 we then replace x=10 with 3, via polynomial remainder theorem, and evaluate the sum shown above.
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
$endgroup$
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
add a comment |
$begingroup$
Just divide the number by 7, if the mod is 0, you subtract 1 from the quotient and multiply it by 7, else, the quotient times 7 is your desired number.
Ex:
70 / 7 = 10, with mod 0. 10-1 = 9 => 9 * 7 = 63 >Biggest multiple under 70.
71 / 7 = 10, with mod 1. 10 * 7 = 70 => Biggest multiple under 71
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
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
});
}
});
kpopguy is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3152587%2fhow-to-find-the-largest-multiple-of-7-which-is-lower-than-another-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
One can compute this number $a$ modulo $7$. The result is $2bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
$endgroup$
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
add a comment |
$begingroup$
One can compute this number $a$ modulo $7$. The result is $2bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
$endgroup$
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
add a comment |
$begingroup$
One can compute this number $a$ modulo $7$. The result is $2bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
$endgroup$
One can compute this number $a$ modulo $7$. The result is $2bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
answered 5 hours ago
Dietrich BurdeDietrich Burde
80.9k647105
80.9k647105
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
add a comment |
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
thanks, this should work
$endgroup$
– kpopguy
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
@PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here.
$endgroup$
– Dietrich Burde
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
$begingroup$
Dietrich.Thanks.Any advantage to using the modulo calculator, why not just divide (calculator) and find remainder ?You have to enter this lengthy number anyway? Hope this question is not too trivial.Thanks.
$endgroup$
– Peter Szilas
4 hours ago
1
1
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
@Peter When you are using such big numbers (and given the context), you would usually not be typing in the number, but writing a program (in Python or Go, etc). This is a more efficient method than, say dividing the number by 7 and the successively smaller numbers till the remainder is 0.
$endgroup$
– Devashish Kaushik
4 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
$begingroup$
Davashish.Thank you. My questions came up when I read 2 mod 7, where from ?As you can see not a number cruncher:)Thank you for your comment.
$endgroup$
– Peter Szilas
3 hours ago
add a comment |
$begingroup$
$$begin{array}{cccccc}115792&089237&316195&423570&985008&687907\852837&564279&074904&382605&163141&518161\494336end{array}$$
Sum up the places of these numbers, by place value carrying when needed, then apply $10^kequiv 3^k bmod 7$ you'll then have a much smaller number to find the remainder of that's equivalent.
5667972, which goes to :$$6(3^5)+6(3^4)+2(3^2)equiv 1458+486+18equiv 2+3+4equiv 2 bmod 7$$ so the largest multiple of 7, is 2 less than the number. Yes, this is a slightly tedious way to go, but it's inspired via extension of Fermat's little theorem, and polynomial remainder theorem.
The reason I broke it into 6 digits at a time, is because Fermat's extension, is that exponents that have the same remainder mod p-1, will give back the same remainder with the same base. That means you can simply turn one into the other, adding like terms. you then go and do the addition the first column on the right sums to 62, carry the 6, that means you sum the next column plus 6, giving 57 carry the 5, next column is then 59, carry the 5, next column 67, carry the 6, next column, 76 carry the 7, next column, 56 there's no column to carry the 5 onto, and in the next step, it will be merged with the 2 (6 digits before), and then tossed because 7 creates a term that is 0 mod 7. Doing the same to other 7's and the nine gives 660200 we then replace x=10 with 3, via polynomial remainder theorem, and evaluate the sum shown above.
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
$endgroup$
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
add a comment |
$begingroup$
$$begin{array}{cccccc}115792&089237&316195&423570&985008&687907\852837&564279&074904&382605&163141&518161\494336end{array}$$
Sum up the places of these numbers, by place value carrying when needed, then apply $10^kequiv 3^k bmod 7$ you'll then have a much smaller number to find the remainder of that's equivalent.
5667972, which goes to :$$6(3^5)+6(3^4)+2(3^2)equiv 1458+486+18equiv 2+3+4equiv 2 bmod 7$$ so the largest multiple of 7, is 2 less than the number. Yes, this is a slightly tedious way to go, but it's inspired via extension of Fermat's little theorem, and polynomial remainder theorem.
The reason I broke it into 6 digits at a time, is because Fermat's extension, is that exponents that have the same remainder mod p-1, will give back the same remainder with the same base. That means you can simply turn one into the other, adding like terms. you then go and do the addition the first column on the right sums to 62, carry the 6, that means you sum the next column plus 6, giving 57 carry the 5, next column is then 59, carry the 5, next column 67, carry the 6, next column, 76 carry the 7, next column, 56 there's no column to carry the 5 onto, and in the next step, it will be merged with the 2 (6 digits before), and then tossed because 7 creates a term that is 0 mod 7. Doing the same to other 7's and the nine gives 660200 we then replace x=10 with 3, via polynomial remainder theorem, and evaluate the sum shown above.
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
$endgroup$
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
add a comment |
$begingroup$
$$begin{array}{cccccc}115792&089237&316195&423570&985008&687907\852837&564279&074904&382605&163141&518161\494336end{array}$$
Sum up the places of these numbers, by place value carrying when needed, then apply $10^kequiv 3^k bmod 7$ you'll then have a much smaller number to find the remainder of that's equivalent.
5667972, which goes to :$$6(3^5)+6(3^4)+2(3^2)equiv 1458+486+18equiv 2+3+4equiv 2 bmod 7$$ so the largest multiple of 7, is 2 less than the number. Yes, this is a slightly tedious way to go, but it's inspired via extension of Fermat's little theorem, and polynomial remainder theorem.
The reason I broke it into 6 digits at a time, is because Fermat's extension, is that exponents that have the same remainder mod p-1, will give back the same remainder with the same base. That means you can simply turn one into the other, adding like terms. you then go and do the addition the first column on the right sums to 62, carry the 6, that means you sum the next column plus 6, giving 57 carry the 5, next column is then 59, carry the 5, next column 67, carry the 6, next column, 76 carry the 7, next column, 56 there's no column to carry the 5 onto, and in the next step, it will be merged with the 2 (6 digits before), and then tossed because 7 creates a term that is 0 mod 7. Doing the same to other 7's and the nine gives 660200 we then replace x=10 with 3, via polynomial remainder theorem, and evaluate the sum shown above.
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
$endgroup$
$$begin{array}{cccccc}115792&089237&316195&423570&985008&687907\852837&564279&074904&382605&163141&518161\494336end{array}$$
Sum up the places of these numbers, by place value carrying when needed, then apply $10^kequiv 3^k bmod 7$ you'll then have a much smaller number to find the remainder of that's equivalent.
5667972, which goes to :$$6(3^5)+6(3^4)+2(3^2)equiv 1458+486+18equiv 2+3+4equiv 2 bmod 7$$ so the largest multiple of 7, is 2 less than the number. Yes, this is a slightly tedious way to go, but it's inspired via extension of Fermat's little theorem, and polynomial remainder theorem.
The reason I broke it into 6 digits at a time, is because Fermat's extension, is that exponents that have the same remainder mod p-1, will give back the same remainder with the same base. That means you can simply turn one into the other, adding like terms. you then go and do the addition the first column on the right sums to 62, carry the 6, that means you sum the next column plus 6, giving 57 carry the 5, next column is then 59, carry the 5, next column 67, carry the 6, next column, 76 carry the 7, next column, 56 there's no column to carry the 5 onto, and in the next step, it will be merged with the 2 (6 digits before), and then tossed because 7 creates a term that is 0 mod 7. Doing the same to other 7's and the nine gives 660200 we then replace x=10 with 3, via polynomial remainder theorem, and evaluate the sum shown above.
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
edited 15 mins ago
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
answered 3 hours ago
Roddy MacPheeRoddy MacPhee
396116
396116
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
add a comment |
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
and had I not made an stupid error, with this small modulus, no calculator required.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
I think this requires a bit more step-by-step explanation...
$endgroup$
– jcaron
48 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
$begingroup$
All the steps are literally in there. but I guess I can show the summation instead of talking about it.
$endgroup$
– Roddy MacPhee
45 mins ago
add a comment |
$begingroup$
Just divide the number by 7, if the mod is 0, you subtract 1 from the quotient and multiply it by 7, else, the quotient times 7 is your desired number.
Ex:
70 / 7 = 10, with mod 0. 10-1 = 9 => 9 * 7 = 63 >Biggest multiple under 70.
71 / 7 = 10, with mod 1. 10 * 7 = 70 => Biggest multiple under 71
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
add a comment |
$begingroup$
Just divide the number by 7, if the mod is 0, you subtract 1 from the quotient and multiply it by 7, else, the quotient times 7 is your desired number.
Ex:
70 / 7 = 10, with mod 0. 10-1 = 9 => 9 * 7 = 63 >Biggest multiple under 70.
71 / 7 = 10, with mod 1. 10 * 7 = 70 => Biggest multiple under 71
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
add a comment |
$begingroup$
Just divide the number by 7, if the mod is 0, you subtract 1 from the quotient and multiply it by 7, else, the quotient times 7 is your desired number.
Ex:
70 / 7 = 10, with mod 0. 10-1 = 9 => 9 * 7 = 63 >Biggest multiple under 70.
71 / 7 = 10, with mod 1. 10 * 7 = 70 => Biggest multiple under 71
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Just divide the number by 7, if the mod is 0, you subtract 1 from the quotient and multiply it by 7, else, the quotient times 7 is your desired number.
Ex:
70 / 7 = 10, with mod 0. 10-1 = 9 => 9 * 7 = 63 >Biggest multiple under 70.
71 / 7 = 10, with mod 1. 10 * 7 = 70 => Biggest multiple under 71
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 11 mins ago
answered 17 mins ago
FabioFabio
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 17 mins ago
FabioFabio
11
answered 17 mins ago
FabioFabio
11
11
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Fabio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
add a comment |
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
$begingroup$
That's only fast to a point, and only if you know your multiples.
$endgroup$
– Roddy MacPhee
13 mins ago
add a comment |
kpopguy is a new contributor. Be nice, and check out our Code of Conduct.
kpopguy is a new contributor. Be nice, and check out our Code of Conduct.
kpopguy is a new contributor. Be nice, and check out our Code of Conduct.
kpopguy is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3152587%2fhow-to-find-the-largest-multiple-of-7-which-is-lower-than-another-number%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$
m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7.
$endgroup$
– Roddy MacPhee
2 hours ago
$begingroup$
78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
I would very much like (aka 'prefer') to see a solution which does not require use of extended-precision or large-integer software packages. (Compare with, e.g., the simple "sum the digits" approach for multiples of 3). Is Roddy's answer the only such?
$endgroup$
– Carl Witthoft
2 hours ago
$begingroup$
no answer requires it. it's simply more convenient for numbers of this size ( I speak from experience, thought I messed up because it didn't match the other answer, turns out I was doing the mod 7 steps too early.found that out by calculator) you can literally do mod as you would long division, just forget to write out the quotient.
$endgroup$
– Roddy MacPhee
2 hours ago
1
$begingroup$
+1 for "it will take some time"!
$endgroup$
– TonyK
21 mins ago