Find all numbers of form $10^k+1$ divisible by $49$

Question

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.

Answer 1

You have to solve $$10^k\equiv-1\pmod{49}\ .$$ Calculating powers, $$\eqalign{ 10^2&=100\equiv2\cr 10^3&\equiv20\cr 10^4&\equiv(10^2)^2\equiv4\cr}$$ and so on. You will eventually find $10^{21}\equiv-1$ as the first solution (I actually did this by asking Maple). So the order of $10$ modulo $49$ is $42$, and the complete solution is $$k=21+42t\ ,\quad t\in\Bbb Z\ .$$

Short cut. If $10^k\equiv-1\pmod{49}$, then $10^k\equiv-1\pmod{7}$ and a much smaller amount of trial and error shows that $k=3+6t$. So if you go back to mod $49$, you now only need to calculate $$\eqalign{ 10^2&\equiv2\cr 10^3&\equiv20\cr 10^6&\equiv(10^2)^3\equiv8\cr 10^9&=10^310^6\equiv160\equiv13\cr 10^{15}&=10^910^6\equiv104\equiv6\cr 10^{21}&=10^{15}10^6\equiv48\equiv-1\ .\cr}$$

Answer 2

Since $3$ is a primitive element of $\mathbb{F}_7^*$,

$$7\mid (10^k+1)\Longleftrightarrow 3^k\equiv -1\pmod{7}\Longleftrightarrow k\equiv 3\pmod{6}$$ so $k=3(2m+1)$ is equivalent to $7\mid (10^k+1)$. The sequence given by: $$ a_n = 10^n+1\pmod{49} $$ is regulated by the recurrence relation: $$ a_{n+1} = 10a_n-9 $$ and it is eventually periodic since the residue classes $\pmod{49}$ are just $49$. If a zero occurs, it occurs for some $n$ that is an odd multiple of $3$ by the previous argument, so let: $$ b_n = a_{3n} = 20^n+1\pmod{49},$$ $$ c_n = b_{2n+1} = 20\cdot 8^n+1\pmod{49},$$ $$ d_n = \frac{20\cdot 8^n+1}{7}\pmod{7}.$$ Now we have just to understand for which $n$s we have $d_n=0$.

Since it is not difficult to check, by induction, that: $$ d_n\equiv 3-n\pmod{7}, $$ we have: $$ 49\mid (10^k+1)\Longleftrightarrow k=3(2(7h+3)+1)\Longleftrightarrow k\equiv 21\pmod{42}.$$