We have 111...11 a hundred times.
We begin with 1 in our quotient. We have 93 ones remaining. We add six zeros according to the division algorithm to get 1000000 in our quotient. We add another one to get 10000001 in our quotient and we have 86 ones remaining. We see that we get the following answer by the same logic : 1000000100000010000001...1000001 (14 ones because 7*14 = 98 ones taken out so we have 11 left as a remainder)
My question is not on the remainder but on the way the quotient is presented : Why do we say : 1000000100000010000001...100000100 is the quotient and not 1000000100000010000001...10000010 with only one zero at the end ? According to the division algorithm shouldn't I need only one zero to make "11" go down before hitting the decimals ?
Thanks
$\endgroup$ 24 Answers
$\begingroup$We have that, letting $N$ be $111...1$ (100 ones), M be $1111111$, $Q$ be the quotient, and $R$ be the remainder,
$$N=M\cdot Q+R$$
However, if $M$ had only one zero at the end, $M\cdot Q$ would be $111...10$, while we need it to be $111...100$.
$\endgroup$ 6 $\begingroup$$111\dots 11$ ($100$ times) is very big.
Lets take $111,111,111,11$, divide it by $111$.
Now $11111111111=111\times 10^8+111\times 10^5+111\times 10^2+11$.
So remainder is $11$.
$\endgroup$ $\begingroup$Each of your blocks of $1000000$ has seven digits. You want the whole quotient to have $100-7=93$ digits. Thirteen blocks of $1000000$ account for $91$ digits so you need two more, which are $10$. I think you didn't count that first $1$ as a digit when you thought you needed two more zeros.
$\endgroup$ 2 $\begingroup$HINT:
We know $$\underbrace{11\cdots11}_{n \text{ digits}}=\dfrac{10^n-1}{10-1}$$
Now use : Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$
$\endgroup$
