Find $\,n\bmod 42\,$ given $\,7\mid 3^n+4n+1$ I have been working on a problem relating to remainders: "The number $3^n+4n+1$ is divisible by $7$. Find the remainder of n when it is divided by $42$." I have been unable to find a strategic way to solve this problem and so far, I have only found the remainders, $4$, $8$, $13$, $21$, $23$, and $24$. Can anyone confirm whether this is correct?
Key Idea $ $ We eliminate nasty exponential dependence on $\,n\,$ in $\,3^{\large n}\,$ by noting - by Fermat - that it's periodic $\!\bmod 7\!:\ 3^{\large 6}\equiv 1\,\Rightarrow\, 3^{\large n}\! =3^{\Large i\large +6k}\equiv \color{90f}{3^{\Large i}}\,$ by mod exponent reduction. Thus we get a simpler linear congruence by replacing the function $\ g(n) = \color{#90f}{3^{\large n}}\,$ by constants $\,\color{90f}{3^{\Large i}},\ i = 0,1,\ldots,5$. 

Doing so $\ n = \color{}i\!+\!6\,\color{#c00}k\,\Rightarrow$ $\! \bmod\color{#c00} 7\!:\,\ \overbrace{0\equiv f(i\!+\!6k)\equiv \color{90f}{3^{\Large\color{}i}}\!+\! 4(i\!+\!6k)\!+\!1}^{\Large{\ \ \ \ 7\ \, \mid\, \  f(n)\ \ =\ \  \color{#90f}{3^{\LARGE n}}\ \ +\ \  4\,n\ \ +\ \ 1}} \equiv f(i)\!+\!3k\!$ $\iff\!$
 $ 3k\equiv -f(i)\!\equiv\!6f(i)\!\!\iff\!\!$ $\color{#c00}{k \equiv 2f(i)}^{\phantom{|^I}}\!\!\!,\, $ so $\, n^{\phantom{|^I}}\!\!\! = i\!+\!6\color{#c00}k = i\!+\! 6(\color{#c00}{2f(i)\!+\!7}j)\equiv \bbox[5px,border:1px solid #0a0]{i\!+\!12f(i)}^{\phantom |}\!\pmod{\!42},\, $ e.g. 
 $\,i\!=\!0^{\phantom{|^{|^|}}}\!\!\!\Rightarrow n\equiv 0\!+\!12f(0)\equiv\bbox[5px,border:1px solid #0a0]{24},\,$ 
$\ i\!=\!1\Rightarrow n^{\phantom{|^I}}\!\!\!\!\equiv 1\!+\!12f(1)\equiv\bbox[5px,border:1px solid #0a0]{13},\,$ $\, i\!=\! 2,3,4,5\Rightarrow \bbox[5px,border:1px solid #0a0]{n\equiv \ldots\phantom{i}\!\!\!}$ 

Remark $ $ The same idea works generally. If $\,g(n)\,$ has period $\,\ell,\,$  so $\ g(i+ \ell k) = g(i),\,$ then we can solve $\,f(n,g(n)) \equiv a\pmod{\!m}\,$ by using this periodicity to eliminate the function $\,g(n)\,$ as above.

Doing so $\ n = i+\ell\, k\,\Rightarrow\bmod m\!:\ a\equiv f(n,g(n))\equiv f(n,g(i))\iff \ldots\, n\equiv r_i$

Combining $\,\ \begin{align}  &amp;n\equiv\, i\pmod{\!\ell}\\ &amp;n\equiv r_i\!\!\!\pmod{\!m}\\\end{align}\!\! \overset{\large \rm CRT\!\!}\iff n\equiv s_i \pmod{\!\ell m},\ $ with $\,s_i\,$ computable by CRT,

assuming $\,\ell,\,m\,$ are coprime. In our solution above we did the CRT step in parallel by substituting $\,n = i + \ell k\,$ not only into $\,g(n)\,$ but everywhere for $\,n\,$ in $\,f,\,$ then solve that for $\,k \equiv k_i\pmod{\!m},\,$ so $\, n = i +\ell (k_i + mj)\equiv i + \ell k_i \pmod{\!\ell m}$.
Let's say that $n=42a+b$, with $a \in Z$ and $b \in \{0,1,2,3,...,41\}$, since $n\in Z$. 

Substituing we get $ 3^n+4n+1=0 (mod 7) \Rightarrow 3^{42a+b}+4(42a+b)+1=0 (mod 7)$

$ \Rightarrow 3^b.(3^{42})^a+7.(24a)+4b+1=0 (mod 7) \Rightarrow 3^b.(3^{42})^a+4b+1=0 (mod 7)$

Note that $3^{42}=({3^2})^{21}=9^{21}=(7+2)^{21}=2^{21}=64=1 (mod 7)$. 

So $3^b.(1)^a+4b+1=0 (mod 7) \Rightarrow 3^b+(7-3)b+1=0 (mod 7) \Rightarrow 3^b-3b+1=0 (mod 7)$

Now we only have to test all values of $b \in \{0,1,2,3,...,41\}$ which $ 3^b-3b+1$ is multiple of 7, remaining 4, 8, 13, 21, 23 and 24.