Learn about finite fields and polynomial arithmetic by deciphering an alien number system! 🛸👽

---

You are an interstellar mathematician working on a distant planet 🌍🛸 where aliens use a strange number system.

1. Numbers wrap around (just like modular arithmetic).
2. The only allowed numbers are {0, 1, 2}.
3. Instead of regular addition and multiplication, they use mod 3 arithmetic.
4. The aliens have discovered a special type of polynomial math that forms a finite field.

Can you decode their system and use it to solve their polynomial puzzles? 🤔

---

The aliens use the set:

$$\mathbb{Z}_3 = \{0, 1, 2\}$$

where all arithmetic is done modulo 3:

$$\begin{array}{c|ccc} \underline{+} & \underline{0} & \underline{1} & \underline{2} \\\ 0 & 0 & 1 & 2 \\\ 1 & 1 & 2 & 0 \\\ 2 & 2 & 0 & 1 \end{array}$$ $$\begin{array}{c|ccc} \underline{\times} & \underline{0} & \underline{1} & \underline{2} \\\ 0 & 0 & 0 & 0 \\\ 1 & 0 & 1 & 2 \\\ 2 & 0 & 2 & 1 \end{array}$$

✅ This system satisfies field properties (closure, associativity, identity, inverses, and distributivity).

---

The aliens don’t just stop at numbers—they invent polynomials using their number system.

They define the set of polynomials:

$$\mathbb{Z}_3[x] = \{ a_n x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0 \mid a_i \in \mathbb{Z}_3 \}$$

These are polynomials where coefficients are from $( \mathbb{Z}_3 )$ .

• $( f(x) = x^2 + 2x + 1 )$
• $( g(x) = 2x^3 + x + 2 )$

The aliens perform polynomial arithmetic, where addition and multiplication follow normal polynomial rules, but the coefficients obey mod 3 rules.

---

$$(x^2 + 2x + 1) + (2x^2 + x + 2) \quad \text{mod 3}$$

Step by step:

$$(x^2 + 2x + 1) + (2x^2 + x + 2)$$

Combine like terms:

$$(1+2)x^2 + (2+1)x + (1+2)$$ $$0x^2 + 0x + 0 = 0$$

✅ The result is 0—these polynomials canceled out!

---

The aliens also multiply polynomials mod 3.

Multiply:

$$(x + 1) \cdot (x + 2) \quad \text{mod 3}$$

Using normal multiplication:

$$x^2 + 2x + x + 2$$

Combine like terms:

$$x^2 + 3x + 2$$

Since $( 3 \equiv 0 \mod{3} )$ , we simplify:

$$x^2 + 2$$

✅ The aliens say that:

$$(x + 1)(x + 2) \equiv x^2 + 2 \pmod{3}$$

---

In modular arithmetic, we take normal numbers and apply a "wrap-around" rule (modulus).

For example, in $( \mathbb{Z}_5 )$, numbers cycle:

$$ 0, 1, 2, 3, 4 $$

with addition and multiplication mod 5.

Now, we ask:

• What if we want to build a similar system for polynomials?
• Can we create a polynomial version of modular arithmetic?

👉 This is why we move from numbers to polynomials!
Just as modular arithmetic creates a structured number system, we can create polynomial rings to structure polynomial arithmetic.

---

In regular modular arithmetic, we say:

$$ a \equiv b \mod{n} $$

which means $( a )$ and $( b )$ differ by a multiple of $( n )$ .

For polynomials, we define modulus with polynomials in a similar way:

$$ f(x) \equiv g(x) \mod{p(x)} $$

which means $( f(x) )$ and $( g(x) )$ differ by a multiple of $( p(x) )$ .

• Numbers Modulo 5:
  • $( 8 \equiv 3 \mod{5} )$ (because $( 8 - 3 = 5 \times 1 ))$
• Polynomials Modulo $( x^2 + 1 )$ in $( \mathbb{Z}_3[x] )$ :
  • $( x^4 \equiv 1 \mod{x^2 + 1} )$
    (because $( x^4 - 1 )$ is divisible by $( x^2 + 1 )$ )

So polynomial modulus creates a structured way to control polynomial arithmetic, just like regular modulus does for numbers.

---

In modular arithmetic, we studied:

1. Numbers modulo a prime $( p )$ (e.g., $( \mathbb{Z}_5 )$ )
2. Fields like $( \mathbb{Z}_p )$ where every number has an inverse

But modular arithmetic has limits:

• What if we want more elements than just numbers?
• What if we need to work with functions instead of numbers?

• In $( \mathbb{Z}_p[x] )$ , we extend modular arithmetic to polynomials.
• This lets us define new types of number systems, such as finite fields.

✅ This is why we move from modular arithmetic to polynomial rings!

---

Imagine you are an alien scientist working in a lab that only allows certain numbers.

• The lab uses modular arithmetic to protect information.
• You discovered that the scientists are using polynomial modulus instead of numbers.

1. The lab uses $( x^2 + 1 )$ as a "modulus lock."
2. What happens to $( x^4 )$ under $mod ( x^2 + 1 )$ ?
3. Can you predict the system they built?

(Hint: It’s similar to numbers mod 5, but more powerful!)

💡 Solution

⚜️ Goal: Compute $x^4_{mod(x^2+1)}$

We want to see how powers of $x$ behave when they are restricted by $x^2+1$

📌 Step 1: Understanding Modulus with Polynomials

In modular arithmetic with numbers, we say:

• $8 ≡ 3_{ mod  5}$

which means 8 and 3 are the same in $ℤ_5$​ because they differ by a multiple of 5.

For polynomials, we do the same:

• $f(x)≡g(x)_{mod  p(x)}$ if $f(x)−g(x)$ is a multiple of $p(x)$.

In $ℤ_3[x]_{mod (x^2+1)}$ , we treat $x^2+1$ like $"0"$ , meaning:

• $x^2≡−1_{mod  (x^2+1)}$

We are working in $ℤ_3$ ​, which only has three numbers: {0,1,2}

• $−1≡2_{mod3}$
  • $x^2≡2_{[mod (x^2+1)] [mod 3]}$

---

1. Polynomials behave like numbers, but they give us more structure.
2. Polynomial modulus lets us build number systems beyond integers.
3. This leads to finite fields, which are essential in coding theory, cryptography, and algebraic structures.

---

Using $mod x^3+x+1$ , simplify the following:

(Hint: Replace $x3$ with $−x−1$ each time it appears!)

• 1️⃣ $x4$ mod $x^3+x+1$
  1. $(x^3)·x$
  2. $(-x-1)·x = -x^2 - x ≡ -x^2 - x +x^3+x+1 = +x^3 -x^2 +1$
  3. $x^3 -x^2 +1$
• 2️⃣ $x^5$ mod $x^3+x+1$
  1. $(x^3)·x^2$
  2. $(-x-1)·x^2$
  3. $-x^3 - x^2$
  4. $-(-x-1) - x^2$
  5. $-x^2 + x + 1$
• 3️⃣ $x^6$ mod $x^3+x+1$
  1. $(x^3)·(x^3)$
  2. $(-x-1)·(-x-1)$
  3. $x^2 + 2x +1$