Find n where $(2n+1)2^{4n+5} = 3 \pmod{7}$

Question

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?

Answer 1

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).

Answer 2

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).

Answer 3

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.

Answer 4

Notice that $2^{4n+5}\equiv 2^{4n}2^5 \equiv 16^n\cdot 32 \equiv 2^n\cdot 4\equiv 2^{n+2}$.

And notice that if $k=3$ then $2^3 \equiv 8 \equiv 1 \pmod 7$. That implies if $n = 3j + r$ where $r$ is the remainder of $n$ then $2^{n}\equiv 2^{3j+r} \equiv 2^{3j}2^r\equiv (2^3)^j2^r \equiv 1^j2^r \equiv 2^r$. And as $r$ can be $0,1,2$ we have $2^n\equiv 2^0,2^1,2^2\equiv 1,2,4$ depending on what $n\pmod 3$ is equivalent to.

....

So our answer will depend on if $n = 3k$ or $n = 3k + 1$ or $n = 3k + 2$ for some $k$.

1. Suppose $n = 3k$ for some $k$..

Then $(2n+1)2^{4n + 5}\equiv 3\pmod 7$

$(6k+1)2^{12k}32\equiv 3\pmod 7$ now $6\equiv -1$ and $32\equiv 4$ and $2^{12k}\equiv(2^3)^{4k}\equiv 1$ so

$(-k+1)4 \equiv 3\pmod 7$

$-4k + 4\equiv 3\pmod 7$

$-4k \equiv -1 \pmod 7$

$4k \equiv 1 \pmod 7$

If we multiply both sides by $2$ we get

$8k\equiv 2\pmod 7$ so

$k \equiv 2 \pmod 7$ and $k = 7L + 2$ for some $L$ nad $n = 3k = 21L + 6$.

(Not the same answer as the book; could someone check if I made an arithmetic error.)

2. Suppose $n = 3k + 1$ for some $k$

$(2n+1)2^{4n+5}\equiv 3\pmod 7$

$(6k + 3)2^{12k + 9}\equiv 3\pmod 7$

$(-k+3)(2^3)^{4k+3}\equiv 3\pmod 7$

$-k + 3 \equiv 3 \pmod 7$

$k \equiv 0 \pmod 7$.

so $k = 7L$ for some $L$ and $n = 3(7L) + 1 = 21L + 1$

(Ditto errors)

3. Suppose $n=3k+2$ for som $k$

$(3n+1)2^{4n+5}\equiv 3\pmod 7$

$(6k + 5)2^{12k+13}\equiv 3\pmod 7$

$(-k-2)2^{12k+12}2\equiv 3\pmod 7$

$(-k-2)2 \equiv 3\pmod 7$

$2k + 4 \equiv -3\equiv 4 \pmod 7$

$2k \equiv 0\pmod 7$

$k \equiv 0\pmod 7$

So $k = 7L$ for so $L$ and $n=3(7L) + 2 = 21L + 2$.

(Ditto)

=== below is my old work =====

So if $n = 3j + r$ and $r=\begin{cases}0\\1\\2\end{cases}$ then

$(2n+1)2^{4n+5}\equiv (2(3j+r)+1)2^{r+2}\equiv$

$6j2^{r+2} + 2r2^{r+2} + 2^{r+2} \equiv -j2^{r+2} + r2^{r+3} + 2^{r+2}\equiv$

$-j2^{r+2} + r2^{r} + 2^{r+2}\equiv$

$-j2^{\begin{cases}2\\0\\1\end{cases}} + r2^{\begin{cases}0\\1\\2\end{cases}} + 2^{\begin{cases}2\\0\\1\end{cases}}\equiv $

$-j\begin{cases}4\\1\\2\end{cases}+ \begin{cases}0\\1\\2\end{cases}\begin{cases}1\\2\\4\end{cases}+\begin{cases}4\\1\\2\end{cases}\equiv$

$-j\begin{cases}4\\1\\2\end{cases}+ \begin{cases}0\\2\\1\end{cases}+\begin{cases}4\\1\\2\end{cases}\equiv$

$-j\begin{cases}4\\1\\2\end{cases}+ \begin{cases}4\\3\\3\end{cases}\equiv3 \pmod 7$

So

$-j\begin{cases}4\\1\\2\end{cases}+ \begin{cases}1\\0\\0\end{cases}\equiv0 \pmod 7$

There are three cases to solve

I) $r = 0$ and $-4j +1 \equiv 0 \pmod 7$

Let $3j+1 \equiv 0\pmod 7$

So if $j= 7k + s; s= 0,1,2,3,4,5,6$ we get

$3s + 1\equiv 0\pmod 7$ and the only one that fits is $s=2$.

so we can have $j = 7k + 2$ and $n = 3j= 3(7k+2)= 21k + 6$ for any $k$.

II) $r =1$ and $-j \equiv 3\pmod 7$

$j \equiv -3 \equiv 4 \pmod 7$.

so we can have $j = 7k + 4$ and $n = 3j + 1 = 3(7k + 4)+1 = 21k + 13$ for any $k$.

II) $r =2$ and $-2j \equiv 3\pmod 7$

$2j \equiv -3 \equiv 4 \pmod 7$.

If $j = 7k + s; s=0,1,2,3,4,5,6$ then $s=2$ is the only one that works

So $j = 7k + 2$ and $n = 3j + 2 = 21k + 8$ for any $k$.

Those are the solutions.

Answer 5

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.