Functions with modular arithmetic

Algebra Level 3

Two functions f , g : Z / 5 Z Z / 5 Z f, g: \mathbb{Z}/5\mathbb{Z} \to \mathbb{Z}/5\mathbb{Z} are defined by f ( x ) = 2 x x 3 g ( x ) = 4 x 7 + 3 1 x 5 \begin{aligned} f(x) &= 2 \cdot x - x^3 \\ g(x) &= 4 \cdot x^7 + 3^{-1} \cdot x^5 \end{aligned} Are these functions different?

Details and assumptions: The prime field Z / 5 Z \mathbb{Z}/5\mathbb{Z} contains only the numbers 0 , 1 , 2 , 3 0, 1, 2, 3 and 4 4 . All computational operations on Z / 5 Z \mathbb{Z} / 5 \mathbb{Z} obey the modular arithmetic with the modulus 5, so that all additions and multiplications in the functions f f and g g are always calculated modulo 5. However, the exponents are natural numbers, so that x n = x x x n times and x 1 x = 1 x Z / 5 Z , n N x^n = \underbrace{x \cdot x \cdot \dots \cdot x}_{n \text{ times}} \quad \text{and} \quad x^{-1} \cdot x = 1 \quad \forall \, x \in \mathbb{Z}/5\mathbb{Z}, n \in \mathbb{N}

no yes

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Markus Michelmann
Jun 16, 2018

For all primes p p and integers x x the little theorem of Fermat applies: x p = x ( mod p ) x^{p} = x \quad (\text{mod } p) In our case, the modulus p = 5 p = 5 is also a prime, so we can apply the theorem of Fermat to our prime field. Therefore, in Z / 5 Z \mathbb{Z} / 5 \mathbb{Z} applies for x 0 x \not= 0 x 5 = x x 3 x = 1 x 1 = x 3 \begin{aligned} & & x^{5} &= x \\ \Rightarrow & & x^3 \cdot x &= 1 \\ \Rightarrow & & x^{-1} &= x^{3} \end{aligned} In particular, 3 1 = 3 3 = 3 ( 9 mod 5 ) = 3 4 = ( 12 mod 5 ) = 2 1 = ( 1 + 5 ) = 4 \begin{aligned} 3^{-1} &= 3^3 = 3 \cdot (9 \text{ mod } 5) = 3 \cdot 4 = (12 \text{ mod } 5) = 2 \\ -1 &= (-1 + 5 ) = 4 \end{aligned} Therefore, we can rewrite the function g ( x ) g(x) g ( x ) = 4 x 5 x 2 + 3 1 x 5 = ( 1 ) x 3 + 2 x = f ( x ) \begin{aligned} g(x) &= 4 \cdot x^{5} \cdot x^{2}+ 3^{-1} \cdot x^5 \\ &= (-1) \cdot x^3 + 2 \cdot x \\ &= f(x) \end{aligned} Thus, both functions are identical.

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...