Solving equation in finite field

In summary, the conversation discusses a problem in finding numbers x in the field Z_{21} that satisfy the equation x^2 = x. It also addresses representing numbers outside the set \{0, 1, ... , n-1\} in finite fields, with -7 being easy to represent and \frac{2}{5} requiring the use of the extended Euclidean algorithm. The conversation also mentions the possibility of solving the problem by trying all 21 possible solutions and a playful mention of the equation x^2 - x = (x - 15)(x - 7).
  • #1
368
0
Hi all,

I encountered a problem I don't know how to solve: In [itex]\mathbb{Z}_{21}[/itex], I want to find numbers x such that [itex]x^2 = x[/itex].

I don't know what to do with that, I just wrote that (since 21 divides [itex]x^2 - x[/itex])

[tex]
21y = x^2 - x
[/tex]

for some integer y, but it didn't seem to help me much.

Could you give me please some advice?


And I have one more (probably trivial, but I can't find it nowhere) question regarding [itex]Z_{n}[/itex]: These fields consist of elements [itex]\{0, 1, ... , n - 1\}[/itex]. But what if I am given something like -7 or [itex]\frac{2}{5}[/itex], how should I represent it in this field?

Thank you.
 
Physics news on Phys.org
  • #2
Z_21 isn't a finite field. If it was, solving this problem would be trivial. (You'd do exactly the same thing you did in your precalculus classes)

But you can factor Z_21 into the product of two finite fields...


But what if I am given something like -7 or , how should I represent it in this field?
-7 should be easy. (Remember that Z_n is just working modulo n)

As for 2/5, that would simply require solving the equation 5x = 2. The extended Euclidean algorithm will be useful here. (run it on (5, n))
 
Last edited:
  • #3
solve it as usual, i.e. x(x-1) = 0, so either x = 0, or x-1 = 0, or x(x-1) is a multiple of 3(7). e.g. x=7 works.

but as i noticed on my midterm in college when i had not studied this topic, it aint too hard to find all solutions of a problem when there are only 21 possible solutions. i.e. try them all.
 
  • #4
Hey, wait a minute! I thought x² - x = (x - 15)(x - 7)!

(Yes, I know both are true. I just thought it would be fun to say it that way. :wink:)
 

What is a finite field?

A finite field is a mathematical structure that consists of a finite set of elements and two operations, addition and multiplication. It is often denoted as GF(q), where q is a prime number representing the number of elements in the field.

How is solving equations in finite fields different from solving equations in real numbers?

In finite fields, the operations of addition and multiplication follow specific rules and have unique properties, unlike in real numbers where they are continuous. Additionally, in finite fields, there are a finite number of solutions to an equation, unlike in real numbers where there can be an infinite number of solutions.

What is the purpose of solving equations in finite fields?

Solving equations in finite fields is important in various fields such as cryptography, coding theory, and error-correcting codes. It allows for efficient and secure data transmission and storage by providing a way to encode and decode messages and detect and correct errors.

What are the methods for solving equations in finite fields?

The most common method for solving equations in finite fields is the Gaussian elimination method, which involves transforming the equation into an equivalent form and then using elimination to find the solution. Other methods include the substitution method and the extended Euclidean algorithm.

Can equations be solved in all types of finite fields?

Not all types of finite fields have the same properties and operations, so equations may not be solvable in all of them. However, equations can be solved in any finite field that follows the rules and properties of a field, such as prime fields, binary fields, and extension fields.

Similar threads

Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
737
  • Linear and Abstract Algebra
Replies
14
Views
2K
Replies
2
Views
901
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
696
  • Linear and Abstract Algebra
Replies
4
Views
682
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
2
Replies
52
Views
2K
Replies
1
Views
1K
Back
Top