<s>[INST] 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?
 [/INST] 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.
</s>