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$?
 A: $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}$
A: 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$$
A: $$
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
$$
