Find the smallest value of $n$ such that $19 \,|\, 10^n+1$ A riddle I'm working on reduces to this question. I don't have a number theory background and don't really know how to approach this kind of problem.
In fact I'm not sure such an $n$ exists. I feel like it does, but my computer has been chugging on an R script for almost 20 minutes to find one.
Any suggestions for resources/additional reading about evaluating divisibility appreciated!
 A: $$19\,|\,10^n+1$$
$\iff$
$$10^n+1\equiv 0 \pmod {19}$$
$\iff$
$$10^n\equiv -1 \pmod {19}$$
Listing powers of $10\pmod{19}$:
$$1,10,100\equiv5,50\equiv12,120\equiv6, 60\equiv3, 30\equiv11, 110\equiv-4,-40\equiv-2,-20\equiv-1$$
Hence $10^9\equiv-1\pmod{19}$.
A: We want to solve $$10^n\equiv -1\mod 19$$
This congruence implies $$10^{2n}\equiv 1\mod 19$$
The order of $10$ modulo $19$ (the smallest exponent $u>0$ with $10^u\equiv 1\mod 19$) is $18$, so $2n$ must be a multiple of $18$. $n=9$ is the smallest example and we are lucky because we actually have $$10^9\equiv -1\mod 19$$ hence we can choose $n=9$. A smaller value is impossible because $n$ must be at least $9$.
A: By fermat's little theorem,  $10^{18}\equiv 1  \ mod19$.  Thus $10^{18}-1\equiv 0 \ mod19$. Thus  $(10^9-1)(10^9+1)\equiv 0 \ mod19$.  So either $10^9 \equiv 1 \ mod19$ or $10^9 \equiv -1 \mod19$. So if we can rule out  $10^9 \equiv 1 \mod 19$ we're done. My calculator tells me we're done. .. 
A: The pattern
$\begin{array}{l}
10^3 + 1 = 1001 = 999+2 \\
10^4 + 1 = 10001 = 9999+2\\
10^5 + 1 = 100001 = 99999+2\\
\dots \\
10^9 + 1 = 999999999+2
\end{array}$
Multiples of $19$:
\begin{array}{r|ccccccccc}
     n &  1 &  2 &  3 &  4 &  5 &   6 &   7 &   8 &   9 \\
   19n & 19 & 38 & 57 & 76 & 95 & 114 & 133 & 152 & 171 \\
\end{array}
$$\begin{array}{cccccccccc}
&  &   & 5 & 2 & 6 & 3 & 1 & 5 & 7 & 9\\  
&  & - & - & - & - & - & - & - & - & -\\
19 & ) & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\
& & 9 & 5 & &  \\  
& & - & -\\
& & & 4 & 9\\
& & &  3 & 8 \\
& & & - & -\\
& & & 1 & 1 & 9 \\
& & & 1 & 1 & 4 \\
& & & - & - & -\\
& & & &   & 5 & 9 \\
& & & &   & 5 & 7 \\
& & & & & & - & - \\
& & & & &   & 2 & 9\\
& & & & &   & 1 & 9\\
& & & & & & - & - \\
& & & & &   & 1 & 0 & 9\\
& & & & &   &   & 9 & 5\\
& & & & & & & - & - & -\\
& & & &   & &   & 1 & 4 & 9\\
& & & & &   &   & 1 & 3 & 3\\
& & & & &   &   & - & - & -\\
& & & & &   &   &   & 1 & 6 & 9\\
& & & & &   &   &   & 1 & 7 & 1\\
& & & & &   &   &   & - & - & -\\
& & & & &   &   &   &   &   & -2\\
\end{array}
$$
Hence 
$999999999 = 19 \times 52631579 - 2$
$10^9 + 1 = 19 \times 52631579$
$19 \mid 10^9+1$
A: Since we need $10^n = 19m-1$, we are looking for $n$ such that $10^n\equiv -1 \bmod 19$
Fermat's Little Theorem guarantees that $10^{18}\equiv 1 \bmod 19$, since $19$ is prime. Since $-1^2\equiv 1 \bmod 19$, if there is some $10^{n}\equiv -1 \bmod 19$ then $10^{2n}\equiv 1 \bmod 19$ and $2n$ must divide $18$. The only even numbers that divide $18$ are $\{2,6,18\}$ giving $n=\{1,3,9\}$ as possible options.
$\bmod 19$:
$10^1\equiv 10\quad(\not \equiv -1)$
$10^2\equiv 100\equiv 5$
$10^3\equiv 50 \equiv 12 \quad(\not \equiv -1)$
$10^6\equiv 144\equiv 11$
$10^9\equiv 132 \equiv 18 \quad(\equiv -1)$  
Then every $n$ an odd multiple of $9$ will be a solution to $19 \mid 10^n{+}1$.
