Prove that 17 divides 1111111111111111 (16 1's) and doesn't divide 11111111

Question

I need to prove that $17$ divides $\underbrace{1111111111111111}_{\text{16 1's}}$ and doesn't divide $\underbrace{11111111}_{\text{8 1's}}$ by using congruence.

I know that $\underbrace{1111111111111111}_{\text{16 1's}}= \frac{10^{16}-1}{9}$ and that $10^{15}\equiv{1}\pmod {17}$. But how do I use these two facts to figure out if $17$ divides $1111111111111111$?

Answer 1

$1111111111111111=10^{15} + ... + 1 = \large{(10^{16} -1)\over9}$

$10^2 \equiv -2\pmod {17}$

$10^{16} - 1 = (-2)^8 - 1 = 256 -1 \equiv 1 -1 = 0\pmod {17}$

$11111111= \large{(10^8 -1 )\over9} $

$10^2 \equiv -2\pmod {17}$

$10^8 - 1 \equiv (-2)^4 - 1 = 15 \pmod {17}$

Answer 2

Do you know that $a^{p-1}-1$ is always divisible by $p$ when $p$ is prime and $a$ is not divisible by $p$? It's a famous result. Take $a=10$ and $p=17$ to get $9999999999999999$. And dividing out $9$ won't change divisibility by $17$.

$11111111$ is just too easy to outright factor. It's clearly divisible by $11$, which is prime ($11\cdot01010101$). And also by $101$ which is prime ($101\cdot00110011$). After dividing these two prime factors, you have $$11111111=11\cdot101\cdot10001$$ For the remaining factor of $10001$, note that it is $100^2+1$. That's not helpful for factoring. But move on to calculate it is $101^2-200$. Still not helpful. $102^2-403$. $103^2-608$. $104^2-815$. $105^2-1024$. Aha. So it's $105^2-32^2=(105-32)(105+32)=73\cdot137$. So you have $$11111111=11\cdot73\cdot101\cdot137$$

Answer 3

$$ 1111111111111111 = \sum_0^{15} 10^ i $$

Since 17 is prime, the 16 values $10^0$, $10^1$, ..., $10^{15}$ are distinct and non-zero mod 17. (Otherwise we have $10^m = 17k$ for some integers $k$, $0\leq m < 17$ in which 17 is a factor of the RHS but not of the LHS.)

Thus

$$ 1111111111111111 = \sum_0^{15} 10^i $$

$$ = 1 + 2 + 3 + ... + 16 \mod 17 $$

$$ = (1 + 16) + (2 + 15) + ... + (8 + 9) \mod 17 $$

$$ = 8 \times 17 \mod 17 $$

$$ = 0 \mod 17 $$

Answer 4

Let $1111111111111111 \equiv k \pmod {17}$.

Then $9999999999999999 \equiv 9k\pmod {17}$

And $10000000000000000 =10^{16} \equiv 9k + 1\pmod {17}$.

ANd but Fermat's little theorem:

$9k + 1 \equiv 10^{16} \equiv 1 \pmod{17}$

so $9k \equiv 0 \pmod 17$.

Not $2\cdot 9 = 18 \equiv 1 \pmod {19}$ so $9^{-1} \equiv 2 \pmod {17}$ and we may do:

So $2\cdot 9k \equiv 2\cdot 0 \pmod {17}$

$k \equiv 0 \pmod 7$.

So $1111111111111111 \equiv 0 \pmod {17}$ and we are done. $17$ divides $1111111111111111$

Meanwhile if $11111111\equiv m \pmod{17}$ then

$99999999 \equiv 9m\pmod {17}$

$10^8 \equiv 9m + 1 \pmod {17}$.

And be successive squaring $10^2 \equiv 100=6*17-2\equiv -2 \pmod {17}$. $10^4\equiv (-2)^2\equiv 4\pmod{17}$ and $10^8 \equiv 4^2 =16\equiv -1 \pmod {17}$.

SO $9m + 1 \equiv -1\pmod{17}$

$9m \equiv -2 \pmod {17}$

$m\equiv 2\cdot 9m \equiv -2\cdot 2 \equiv -4 \equiv 13 \pmod {17}$.

And we are done $17$ does not divide $11111111$ and, indeed, we will have a remainder of $13$ if we attempt to.

$11111098= 653594\times 17$ and $11111111=653594\times 17 + 13$.