My Math Forum (http://mymathforum.com/math-forums.php)
-   Algebra (http://mymathforum.com/algebra/)
-   -   Solve x^120 + x^3 + 2x^2 + x +3 0 (mod 7) (http://mymathforum.com/algebra/345708-solve-x-120-x-3-2x-2-x-3-0-mod-7-a.html)

 Sisco February 3rd, 2019 04:04 AM

Solve x^120 + x^3 + 2x^2 + x +3 0 (mod 7)

Hi,

I'm having trouble with this one:

x^120 + x^3 + 2x^2 + x +3 ≡ 0 (mod 7)

What is x?

 cjem February 3rd, 2019 05:19 AM

You can just try each number from 0 to 6 to see which are solutions. The only obstacle in doing this is computing the 120-th powers mod 7. I'll explain a common trick for computing large powers modulo a relatively small number, and use it to compute $3^{120} \bmod 7$.

Say you have natural numbers $a, n$ and $m$ and you want to compute $a^n \bmod m$. Write $n$ in its binary form: $n = n_0 + n_1 2 + n_2 2^2 + \dots + n_k 2^k$, with each $n_i$ here being either $0$ or $1$. We now compute $a^{2^i} \bmod m$ for $i = 0, 1 \dots, k$. But this is particularly easy if $m$ is small: once we know $a^{2^i} \bmod m$ for some $i$, we just need to square this value and reduce mod $m$ to get $a^{2^{i+1}} \bmod 7$. (Do you see why this is the case?) Then we're pretty much done in light of the equation $a^n = a^{n_0} a^{n_1 2} a^{n_2 2^2} \dots a^{n_k 2^k}$.

Let's see this in practice with $a = 3, n = 120, m = 7$. We have $120 = 2^6 + 2^5 + 2^4 + 2^3$. Now:

\begin{align*} 3 &\equiv 3 \bmod 7 \\ 3^2 &= 9 \equiv 2 \bmod 7 \\ 3^{2^2} &\equiv 2^2 = 4 \bmod 7 \\ 3^{2^3} &\equiv 4^2 = 16 \equiv 2 \bmod 7 \\ 3^{2^4} &\equiv 2^2 = 4 \bmod 7 \\ 3^{2^5} &\equiv 4^2 \equiv 2 \bmod 7 \\ 3^{2^6} &\equiv 2^2 = 4 \bmod 7 \end{align*}

(Aside: as soon as we hit a value we've seen before in the list, we'll enter a cycling pattern. More precisely, let $x_i$ denote $a^{2^i} \bmod m$. If $x_{r + s} = x_s$ for some naturals $r$ and $s$, we will have $x_{dr + s + i} = x_{s+i}$ for all natural numbers $d$ and $i$. And we're guaranteed to have such $r, s$ with $s \leq m+1$ by the pigeonhole principle.)

Now we just compute

\begin{align*} 3^{120} &= 3^{2^3} 3^{2^4} 3^{2^5} 3^{2^6} \\ &\equiv 2 \times 4 \times 2 \times 4 \\ &= 8 \times 8 \equiv 1 \times 1 = 1 \bmod 7 \end{align*}

 All times are GMT -8. The time now is 08:29 AM.