If $2^x \equiv 2^4 + 2^4 \pmod 7$, then what is the value of $\mathbf x$?

Question

It's easy to figure out the answer which is 2. But I am trying to solve it in a different approach. My approach:

$2^x \equiv 2^4 + 2^4 \pmod 7 \Rightarrow x\log_2(2) \equiv 4\log_2(2) + 4\log_2(2) \pmod 7 \Rightarrow x \equiv 4 + 4 \mod 7 \Rightarrow x \equiv 8 \pmod 7 \Rightarrow x \equiv 1 \pmod 7 $

Here, the answer is 1(false) but it supposed to be 2. It works if I do the modular operation by 6.

PS: I read somewhere that it is related to Fermat's little theorem, but can't figure it out. Can someone give a detail explanation on this?

Answer 1

Fermat's little theorem says $2^6\equiv1\pmod7$. In fact, $2^3=8\equiv1\pmod7$.

$2^4+2^4=2\times2^4=2^5 $, so, because $2^3\equiv1\pmod7$, $2^{3n+5}\equiv2^4+2^4\pmod 7$ for all $n\in \mathbb Z$

$(n>-2$ to avoid negative exponents).

So if $2^x\equiv2^4+2^4\pmod7$, then $x$ could be $3m+2$

(integer $m>-1$ to avoid negative exponents).

On the other hand, $2^{3m}\equiv2^0\equiv1$ and $2^{3m+1}\equiv2^1\equiv2,$

so these are not congruent to $4=2^2\equiv2^5=2^4+2^4\pmod7$.

Answer 2

$\!\bmod 7\!:\,\ 2\,$ has order $\,\color{#c00}3,\,$ so the correct modulus for $\,\ell := \log_2$ is $\,\color{#c00}3\ $ (not $7),\,$ i.e.

$\bmod 7\!:\,\ \overbrace{2^{\Large x}\equiv 2^{\large y}}^{\Large a\,\ \equiv\,\ b} \iff 2^{\large x-y}\equiv 1\iff \color{#c00}3\mid x-y\iff\!\!\!\!\! \overbrace{x\,\equiv\, y}^{\Large \ell(a)\ \equiv\ \ell(b)}\!\!\!\!\pmod{\!\color{#c00}3}$

Hence if you redo the calculation using modulus $\,\color{#c00}3\,$ instead of $\,7,\,$ and use $\,2^{\large 4}\!+2^{\large 4} = 2(2^{\large 4}) = 2^{\large 5},\,$ then you will obtain $\,2^{\large x}\equiv 2^{\large 5}\pmod{\!7}\iff x\equiv 5\equiv 2\pmod{\!\color{#c00}3}$

Remark $ $ Regarding you question about the relationship to little Fermat, since $\, a^{p-1}\equiv 1\pmod{p}\,$ if $\,p\nmid a,\,$ this implies that the order of $\,a\,$ divides $\,p-1.\,$ For algorithms to compute the order and solve the discrete log problem see here.

Answer 3

By Fermat’s little theorem, $2^6\equiv1\pmod7$, so if $x\equiv y\pmod6 $ then $2^x\equiv2^y\pmod7$. So to solve $2^x\equiv2^4+2^4=32\equiv4\pmod7$, you only have to check if the following are congruent to $4\pmod7: 1,2,4,8,16,32.$ That’s easy, no?