Largest multiple of $7$ lower than some $78$-digit number?

Question

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.

Answer 1

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

Answer 2

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

EDIT

Due to looking at previous questions, and a recent ultimate divisibility posting someone made, I've found a rule I forgot that makes it even less effort. But first a review of Columnar addition:

$$\begin{alignat}{}&115792\\&089237\\&316195\\&423570\\&985008\\&687907\\&852837\\&564279\\&074904\\&382605\\&163141\\&518161\\+\!\!\!&494336\\ &\overline{\phantom{123456}}\end{alignat}$$

These form the digit columns I refer to above. Now for the rule I forgot, which was: $$x\equiv y\implies x^c\equiv y^c$$ It's part of the Fermat extension used, but on its own, it's even more powerful!

All we did above, was a base $10^{\text{ord}(10,7)}$ digit sum, followed by a switch of base to base $(10\pmod 7)$ and a final modular reduction.

We can use the new rule without finding the order, and group digits into powers of previous group lengths allowing us to cut the additions used down ( using any exponent value):

$$\begin{alignat}{}115792089237316195423570985008&687907\\852837564279074904&382605\\163141&518161\\+\!\!\!&494336\\ &\overline{\phantom{123456}}\end{alignat}$$

this converges using a sum of the ceiling of log base $c$ of number of digits base $10^z$; where $z$ being the digit groupings (clumped a bit above). You'll note above I used $c=2,z=6$ this means I'll roughly half the number of digits at each addition chain . This does better than straight addition of the values if you have more than 10 digit groups, plus it's parallelizable.

Answer 3

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

Answer 4

Yet another way would be to calculate the iterated scalar product described in this question:

As far as I know we can generate this vector $\bf v$ to take scalar product with by taking the sequence $${\bf v}_{k+1} = (10^k) \mod 7$$

Furthermore, to calculate $10^k \mod 7$, we can do this on the fly as well by the following algorithm:

1. Start exponent $k=0$, $a_0 = 1 = 10^0\mod (7)$
2. Calculate $a = 10\cdot a$. This number will for reasons explained later be in range $\{10,11,\cdots,60\}$.
3. Now find $x: a = x \mod 7$, this can for example be done fast by a lookup table.
4. Increment $k: k = k+1$,
5. Set $a_k = x$
6. Loop back to $2$ for as long as we still have digits.

---

This way to calculate will be $\mathcal O(n)$ complexity for $n$ decimal digits for each scalar product, because the first number we have will shrink down to $5\cdot \log_{10}(n)$. And we need to get down to 1 digit, this means we need to do inverse logtower function(n). An extreeemely fast decaying function. For a 1000 digit number $\approx 10^{1000}$, averaging 5 multiplied by on average 3 $\approx 5\times 3\cdot 1000 = 1.5\cdot 10^{4}$ which is $4$ decimal digit, then next one will be $2$ decimal digit and then we are done.

Answer 5

Well between

$115792089237316195423570985008687907852837564279074904382605163141518161494330$

$115792089237316195423570985008687907852837564279074904382605163141518161494336$

Exactly one of those is divisible by $7$.

And it is $115792089237316195423570985008687907852837564279074904382605163141518161494330 + a$ where $0 \le a < 7$ and $a\equiv 7-b$ and $b \equiv 115792089237316195423570985008687907852837564279074904382605163141518161494330 \pmod 7$.

So if you are lucky enough to have a calculator or computer program that can figure out $115792089237316195423570985008687907852837564279074904382605163141518161494330 \pmod 7$ you can get $115792089237316195423570985008687907852837564279074904382605163141518161494330\equiv 5\pmod 7$. (Assuming the calculator program that comes with Windows 8, doesn't have a rounding error.

So $115792089237316195423570985008687907852837564279074904382605163141518161494330 +2 =$

$115792089237316195423570985008687907852837564279074904382605163141518161494332$ is the largest number that is less than or equal to $115792089237316195423570985008687907852837564279074904382605163141518161494336$ that is divisible by $7$.

========

Now if you don't have a program that can do this....

So well, bear in mind if $10^6 \equiv 1 \pmod 7$ and $10^{6m+i} \equiv 10^i \equiv 1, 3,2,-1,-3, -2 \pmod 7$ if $i = 0,1,2,3,4,5$.

So $115792089237316195423570985008687907852837564279074904382605163141518161494330\equiv$

$1*0 +$

$3*3 +$

$2*3 + $

$(-1)*4 + $

$(-3)*9 + $

$(-2)*4 + $

$1*1 + $

......

$1*2 +$

$3*9 + $

$2*7 + $

$(-1)*5 + $

$(-3)*1 + $

$(-2)*1$

Or you can add the $1,7,13,.....,73$ digits together and take the remainder mod $7$. Then add the $2,8,...,74$ digits together, multiply by 3 and take the $7$ remainder and add. Add the $3,9, ...., 75$ digits together, multiply by 2, and take the $7$ remainder and add. Then add the $4,10,....,76$ and $7$ remainder and subtract. Add the $5,11,....,77$ digits together, multiply by 3, and take the $7$ remainder and subtract. And then take the $6,12,...,78$ digits together, multiply by $,$ and take the $7$ remainder and subtract. Then take the $7$ remainder of your result (it should be $5$); subtract from $7$ and add to: $115792089237316195423570985008687907852837564279074904382605163141518161494330$