find remainder $\frac{ 11111\ldots1111 \text{ (105 ones )}} {107}$

Question

Find the remainder of

$\dfrac{1111\ldots111 \mspace{10mu}}{107}$ (105 ones) into 107 .

So I assumed that $1111\ldots \text{ (105 ones)}$ is going to be exactly divided by $11111 \text{ (5 ones)}$ $ 21 \text{ times}$ $(105/5 = 21)$

$11111\cdot10000100001\ldots=11111\ldots11 \text{ (105 times)}$.

Answer 1

Note that $$n:=\underbrace{11\ldots 1}_{105} =\frac{10^{105}-1}9.$$ $107$ is a prime so that by Little Fermat, $a^{106}\equiv 1\pmod{107}$ for all $a$ not a mutltiple of $107$. It follows that $10\cdot 10^{105}=10^{106}\equiv 1$, and hence $$10\cdot(9n+1)\equiv 1\pmod{107}.$$ You can use this to find $n\bmod{107}$ once you verify that $10\cdot 75$ and $9\cdot 12$ are $\equiv 1\pmod{107}$, so $$ n\equiv (75-1)\cdot 12\equiv 32\pmod{107}.$$

Answer 2

$$\underbrace{11111\cdots 111}_{105 \text{ times}}={10^{105}-1\over 9}$$Based on little Fermat's theorem,$$10^{106}\equiv 1\mod 107\\10^{106}\equiv 1\mod 9$$hence$$10^{106}=9\times 107k+1$$by defining $x=10^{105}$ we obtain $$10x=9\times 107k+1$$since there exist some $q,r\in \Bbb Z$ such that $x=9\times 107q+r$ we must have $$10x\equiv 10r\equiv 1\mod 9\times 107$$For example with $10r-1=9\times 107\times 3=2889$ we have $r=289$, and since $\gcd(9,107)=1$, this $r$ is unique, therefore$$10^{105}=9\times 107k+289$$ $$10^{105}-1=9\times 107k+288$$ $${10^{105}-1\over 9}=107k+32$$

Answer 3

$\underbrace{1111\cdots1}_{105-times} = \frac {10^{105}-1}{9} $

$10^{106}\equiv 1\pmod {107}$ by Fermats little theorem

$10^{105}\equiv 10^{-1}\pmod {107}$

by the Euclidean algorithm, we find $10^{-1} \equiv 75 \pmod{107}$ and $9^{-1}\equiv 12\pmod {107}$

$9\cdot 74 \equiv 32 \pmod {107}$

Answer 4

$\!\!\bmod 107\!:\ \dfrac{\overbrace{10^{105}}^{\large\color{#c00}{1/10}}-1}{9}\equiv \dfrac{-1}{10}\equiv \dfrac{-11}{110}\equiv\dfrac{96}3\equiv \bbox[5px,border:1px solid #c00]{32}\ $ by $\rm\color{#c00}{Fermat}$ and Gauss's algorithm.

---

Alternatively, equivalently, eliminating all fractions

$\begin{align}\!\!\bmod 107\!:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9x&\equiv 10^{\large 105}-1\\ \overset{\large \times\ 10}\iff\ \ 90x &\equiv 10^{\large106}-10\equiv -9\ \ \ {\rm by\ little\ Fermat}\\ \overset{\large\div\ 9}\iff\ \ 10x&\equiv -1\\ \overset{\large\times\ 11}\iff 110x&\equiv -11,\ \ \text{by scaling as in Gauss's algorithm}\\ \overset{\large \equiv}\iff\ \ \ \ 3x&\equiv 96\ \ \ \ \ \ \ {\rm by}\ \ 110\equiv 3,\, -11\equiv 96\\ \overset{\large \div\ 3}\iff\ \ \ \ \ \ x&\equiv 32 \end{align}$

where we used that congruences are preserved (remain equivalent) when scaled by units (invertibles), i.e. multiplying or dividing a congruence by an integer coprime to the modulus yields an equivalent congruence, since if $\, \color{#0a0}{(n,c)=1}\,$ then $\bmod n\!:\ ca\equiv cb\iff a\equiv b,\ $ because, by Euclid's lemma, $\,\color{#0a0}{n\mid c}\,(a-b)\iff n\mid a-b$.