# 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?

• Exhibit A: $2 \times 5 = 3 \pmod 7$. – player3236 Jan 13 at 18:39
• @player3236 So I'm in the wrong here, I got it but I don't understand the book's solution. – TechnoKnight Jan 13 at 18:45
• Do you know Fermat's Little Theorem? – fleablood Jan 13 at 18:46
• @fleablood Never heard of it. – TechnoKnight Jan 13 at 18:46
• @TechnoKnight FYI, you can use the command \pmod{7} instead of (mod 7) to correctly display $\pmod{7}$ instead of $(mod 7)$. – DMcMor Jan 13 at 18:52

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

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}$$

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

• Thanks for the alternative solution but can you explain to me what the book has done? – TechnoKnight Jan 13 at 19:09
• @TechnoKnight For example, $n=3k$ then $(6k+1)2^{12k+5} \equiv (-k+1) 2^5 \equiv 3 \pmod 7$ which gives you $k\equiv 2 \pmod 7$, so $n=3(7j+2)=21j+6$. Others can be done similarly – Neat Math Jan 13 at 19:13
• I understood that but I didn't get why they thought of doing "If n can be divided by 3 or not" I mean, what the equation above has anything to do with n ability to be divided by 3? – TechnoKnight Jan 13 at 19:18
• @TechnoKnight Because $2^3\equiv 1 \pmod 7$. As others point out if you are familiar with FLT then you'd know $2^6\equiv 1 \pmod 7$. Even if you don't, since the modulus is so small, it helps to find the order of $2 \pmod 7$ to simplify calculation. – Neat Math Jan 13 at 19:21
• From where $2^{3} = 1 (mod 7)$ came from? – TechnoKnight Jan 13 at 19:28

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.

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

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

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

• Must have made an error somewhere but the idea is the same consider the cases where $n = 3j; 3j+1$ and $3j+2$ and you get equations involving solving for $j$ which you can solve by considering the remainders of $j$ via $7$. – fleablood Jan 13 at 19:29
• Thank you but I still don't understand what the book has done. – TechnoKnight Jan 13 at 19:33
• The book did what I did (and got a different answer) but did it all in a single line. I'll rewrite this so it is easier to follow. – fleablood Jan 13 at 19:42
• But I still don't understand why the book tested for "If n is divisible by 3 or not" What n being divisible by 3 has anything to do with the equation? – TechnoKnight Jan 13 at 19:44
• Because $2^3 \equiv 1 \pmod 7$. So if $n = 3k + 0,1,2$ then $2^n\equiv 2^{3k + 0,1,2}\equiv 2^{3k}\times 2^{0,1,2}\equiv 2^{0,1,2}$. So $2^{4n+5}\equiv 2^{12n + 5,9,13}\equiv 2^2,2^0,2^1$. So we only have three things to solve. $n=3k$ and $(6k+1)4\equiv 3$ or $n=3k+1$ and $(6k+3)\equiv 3$ or $n=3k+2$ and $(6k + 5)2\equiv 3$. – fleablood Jan 13 at 20:05

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.

• i.e. eliminate the nasty exponential by splitting into case-analyses of the values in its period, as explained here. – Bill Dubuque Jan 13 at 22:33