
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
February 3rd, 2019, 04:04 AM  #1 
Newbie Joined: Feb 2019 From: Uppsala Posts: 1 Thanks: 0  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? 
February 3rd, 2019, 05:19 AM  #2 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 311 Thanks: 109 Math Focus: Number Theory, Algebraic Geometry 
You can just try each number from 0 to 6 to see which are solutions. The only obstacle in doing this is computing the 120th 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*}$ Last edited by cjem; February 3rd, 2019 at 05:25 AM. 