Find n where $(2n+1)2^{4n+5} = 3 \pmod{7}$ For $n$ normal number, the book solved it like this:
If $n$ can be divided by $3$ (which is $n = 3k$) then $n = 21L + 9$.
If $n$ can't be divided by 3(Which is either $n = 3k +1$ or $n = 3k + 2$) then $n = 21L + 1$ or $n = 21L + 2$ .
But I didn't solve it like this.
My logic is that since 3 is a prime number then $(2n+1)2^{4n+5} = 3 \pmod{7}$ means either $2^{4n+5} = 3\pmod{7}$ and $ 2n + 1 = 1\pmod{7} $ or the other way around.
But since there is no $n$ value that can make $2^{4n+5} = 3\pmod{7}$ then it means:
$ 2n + 1 = 3 \pmod{7}$ and by calculating we find in the end $n = 7k' + 1$
And $ 2^{4n+5} = 1\pmod{7}$ and by calculating we find that $n = 3k''$
So it means that $n = 7k' + 1$ AND $n = 3k''$
So, I know that my solution is faulty but can anyone explains to me the right solution or point out where I went wrong?
 A: Here is one way to solve it:

*

*$(2n+1)\pmod 7\equiv 1,3,5,0,2,4,6,\cdots\ $ and cycling.

*$2^{4n+5}\pmod 7\equiv 4,1,2,\cdots\ $ and cycling.

Both can be proved by induction on $n$.

*

*$1\times 3\equiv 2\times 5\equiv 4\times 6\equiv 3\pmod 7\ $ verify there are no others.

Finally can you find $n$ for which the conditions are reunited ? (hint, Chinese theorem).
A: Update:
I found that this solution provides a neat way in general to solve this kind of problems. I will apply the method here:
$$(2n+1)2^{4n+5} \equiv 3 \pmod 7 \\ \iff g(n)=(2n+1)2^n\equiv (2n+1) 2^{4n+6} \equiv 3\cdot 2 \equiv -1 \pmod 7$$
Suppose $n=3k+i, i=0,1,2$, then
$$-1 \equiv g(3k+i) = (6k+2i+1)2^{3k+i} \equiv (-k+2i+1)2^i=g(i)-k\cdot 2^i \pmod 7\\
\iff k\equiv 2^{3-i}(g(i)+1)\equiv (2i+1) 2^3 + 2^{3-i} \equiv 2^{3-i}+2i+1 \pmod 7 \\
(\text{ now write } k = 2^{3-i}+2i+1 + 7j)\\
\iff n=3k+i = 3(2^{3-i}+2i+1+7j)+i \equiv 3\cdot 2^{3-i}+7i+3 \pmod {21}\\
\iff n \equiv \begin{cases}3 \cdot 8 + 0 + 3 \equiv 6  \\ 3 \cdot 4 + 7 +3\equiv 1  \\ 3 \cdot 2 + 14+3\equiv 2 \\ \end{cases} \pmod{21}$$

Just some comments:
$f(n)=(2n+1)2^{4n+5}$, then $f(n+21)\equiv f(n) \pmod 7$ (notice that $2^3\equiv 1 \pmod 7$). So the most direct way is to plug in $n=1, 2, \ldots, 21$ into $f(n)$ and see which ones yield $3 \pmod 7$. No fancy theorems needed.
To save time, do as zwim showed by reusing partial results (you can make a $3 \times 7$ table).
A: This is somewhere between a comment and an answer.
The simplest way to solve this is that the value of $(2n+1)2^{4n+5}$ is precisely a function of $n \mod 42 = 6 \times 7$. More precisely, $2n+1 \mod 7$ is precisely a function of $n \mod 7$ while $2^{4n+5} \mod 7$ is precisely a function of $n \mod 6$. For each $i \in \{0,1,2,3,4,5\}$, you can check directly what $n \mod 7$ must be--in particular, what $(2n+1) \mod 7$ must be, given $n \mod 6$--in particular, what is $2^{4n+5} \mod 7$, which is a function of $n \mod 6$.
For example, for the case where $n = 0 \mod 6$ , we see that $2^{4n+5}= 1 \times 2^5 = 32 = 4 \mod 7$. So $2^{4n+5}$ is $4 \mod 7$ for this case where $n = 0 \mod 6$. So for the case where $n = 0 \mod 6$, the integer $n$ must satisfy the equation $(2n+1) \times 4 = 3 \mod 7$, which gives $n = 6 \mod 7$. So for the case where $n = 0 \mod 6$, the integer $n$ must also be $6 \mod 7$ which gives $n = 6 \mod 42$. What about the case where $n = 1 \mod 6$. What about each of the cases where $n \mod 6 = i=2,3,4,5$.
This in fact would work if $2n+1, 4n+5$ were each replaced by any two polynomials in $n$. Can you see why this is.
A: Problem: Find $n$ where $(2n+1)2^{4n+5} \equiv 3 \bmod{7}$

My approach:
Starting at $n=0,1,2...$, all $\bmod 7$, knowing that $2^3\equiv 1$, we can see that  $2^{4n+5}\equiv 2^{n+2}$ cycles through $\{4, 1, 2\}$. Since $4^{-1}\equiv 2$, the implied $3$-cycle of $required$ values for $(2n+1)$ to satisfy is thus $\{2\cdot 3, 1\cdot 3, 4\cdot 3\} = \{\color{red}6,\color{green}3,\color{blue}5\}$, each of which can be found at one point in the $7$-cycle of its values $\{1, \color{green}3, \color{blue}5, 0, 2, 4, \color{red}6\}$.
So we need one of $n \underset{(3,7)}{\equiv} (0,6),(1,1),(2,2)$ which can be worked through the Chinese Remainder Theorem to give $n \equiv \{6,1,2\} \bmod 21$.

Your approach fails because of your assumption that only $1\times 3 = 3\times1 \equiv 3 \bmod 7$, whereas also $2\times 5 \equiv 4\times 6 \equiv 3 \bmod 7$; a prime modulus implies all coprime numbers have a multiplicative inverse.

The book's approach is incomprehensible, and $n \equiv \{\color{red}9,1,2\} \bmod 21$ is wrong.
