My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree1Thanks
  • 1 Post By cjem
Reply
 
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?
Sisco is offline  
 
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 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.
cjem is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
2x2, mod, solve, x120



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Please Solve this 4 EPIC Problems.... i couldn't solve it myself gen_shao Algebra 12 November 2nd, 2014 06:11 AM





Copyright © 2019 My Math Forum. All rights reserved.