2
$\begingroup$

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?

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Thanks for the alternative solution but can you explain to me what the book has done? $\endgroup$ – TechnoKnight Jan 13 at 19:09
  • $\begingroup$ @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 $\endgroup$ – Neat Math Jan 13 at 19:13
  • $\begingroup$ 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? $\endgroup$ – TechnoKnight Jan 13 at 19:18
  • $\begingroup$ @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. $\endgroup$ – Neat Math Jan 13 at 19:21
  • $\begingroup$ From where $2^{3} = 1 (mod 7)$ came from? $\endgroup$ – TechnoKnight Jan 13 at 19:28
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$ – fleablood Jan 13 at 19:29
  • $\begingroup$ Thank you but I still don't understand what the book has done. $\endgroup$ – TechnoKnight Jan 13 at 19:33
  • $\begingroup$ 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. $\endgroup$ – fleablood Jan 13 at 19:42
  • $\begingroup$ 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? $\endgroup$ – TechnoKnight Jan 13 at 19:44
  • $\begingroup$ 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$. $\endgroup$ – fleablood Jan 13 at 20:05
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.