Prove that 17 divides 1111111111111111 (16 1's) and doesn't divide 11111111
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$?
$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}$
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$$