5
$\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.

$\endgroup$
  • $\begingroup$ m.wolframalpha.com/input/… works a lot easier it lists as 2 mod 7. $\endgroup$ – Roddy MacPhee Mar 18 at 11:47
  • $\begingroup$ 78 digits is semi small cryptographically compared to 617 digit (2048 bit) crypto keys. $\endgroup$ – Roddy MacPhee Mar 18 at 11:58
  • 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 Mar 18 at 12:07
  • $\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 Mar 18 at 12:11
  • 1
    $\begingroup$ +1 for "it will take some time"! $\endgroup$ – TonyK Mar 18 at 14:18
14
$\begingroup$

One can compute this number $a$ modulo $7$. The result is $2\bmod 7$. So take $a-2$. It is the largest multiple of $7$ less than $a$.

$\endgroup$
  • $\begingroup$ thanks, this should work $\endgroup$ – kpopguy Mar 18 at 9:40
  • $\begingroup$ @PeterSzilas See How to compute modulo, or similar links. With wolframalpha, compute it here. $\endgroup$ – Dietrich Burde Mar 18 at 9:45
  • $\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 Mar 18 at 10:06
  • 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$ – The Long Night Mar 18 at 10:14
  • $\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 Mar 18 at 11:18
5
$\begingroup$

$$\begin{array}{cccccc}115792&089237&316195&423570&985008&687907\\852837&564279&074904&382605&163141&518161\\494336\end{array}$$ Sum up the places of these numbers, by place value carrying when needed, then apply $10^k\equiv 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+18\equiv 2+3+4\equiv 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.Formula used $$\sum_{n=0}^Ld_na^n\equiv\sum_{n=0}^L(d_n\bmod p)(a_n\bmod p)^{(n \bmod (p-1))} \pmod p$$ we did the exponent part first, the base part second, and the coefficient (digit) part third, we then used the simple reduction mod p last. For those wondering, That means in theory the first number that has a 12+ digit intermediate sum is ... 6 million and 6 digits if I did the math correct.

$\endgroup$
  • $\begingroup$ and had I not made an stupid error, with this small modulus, no calculator required. $\endgroup$ – Roddy MacPhee Mar 18 at 12:24
  • 1
    $\begingroup$ en.m.wikipedia.org/wiki/Addition#/media/… $\endgroup$ – Roddy MacPhee Mar 18 at 20:14
  • 1
    $\begingroup$ okay in the second one there k should be y. But, it's literally that simple. first might multiply by the same coefficient (digit in the case of numbers) on each side. $\endgroup$ – Roddy MacPhee Mar 18 at 20:44
  • 1
    $\begingroup$ That is what I did in fact. $\endgroup$ – Roddy MacPhee Mar 19 at 14:17
  • 1
    $\begingroup$ BTW, thats sufficiently better than typing something having not thought of it prior ... $\endgroup$ – Roddy MacPhee Mar 19 at 15:26
0
$\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

$\endgroup$
  • $\begingroup$ That's only fast to a point, and only if you know your multiples. $\endgroup$ – Roddy MacPhee Mar 18 at 14:26
  • $\begingroup$ Try doing this without gmp or equivalent. You will be sad. $\endgroup$ – Carl Witthoft Mar 19 at 13:21
  • $\begingroup$ I could, but it doesn't scale well if you can't think of sufficiently high multiples to do long division quickly. $\endgroup$ – Roddy MacPhee Mar 19 at 17:36
  • $\begingroup$ just caring about remainder I got to the end in 4:48.3 at 78 digits. $\endgroup$ – Roddy MacPhee Mar 21 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.