 My Math Forum Solve x^120 + x^3 + 2x^2 + x +3 ≡ 0 (mod 7)
 User Name Remember Me? Password

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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: 313 Thanks: 112 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 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*} Thanks from topsquark Last edited by cjem; February 3rd, 2019 at 05:25 AM. July 6th, 2019, 02:53 AM #3 Newbie   Joined: Jun 2016 From: Hong Kong Posts: 25 Thanks: 2 just use Fermat's little theorem We have $x^6\equiv 1\pmod{7}$ for $(x,7)=1$ Tags 2x2, ≡, mod, solve, x120 ### cochy rayman math

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post gen_shao Algebra 12 November 2nd, 2014 06:11 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      