Stop Using the Euclidean Algorithm to Prove Z/p is a Field

Context: Take the set of numbers module p, a prime number. Most of the field axioms (addition is a group, multiplication is a semi-group, the distributive law) are easily verifiable as an exercise (it’s a simple restatement of theorems about numbers). The big one is proving that for every number not 0, there is an inverse.

For some reason, most people will resort to the Euclidean algorithm. But there’s a simpler way.

Prove that there are no zero divisors. This is a different way of saying that if a prime number divides a product, it divides one of the terms.

Prove that this implies ax=bx implies a=b or x=0

Therefore, the function x->ax is one-to-one, on a finite set.

Therefore, it is onto.

Therefore, 1 is in the image. Or, there exists an a, ax=1.

This entry was posted on Wednesday, January 21st, 2009 at 1:07 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

3 Responses to Stop Using the Euclidean Algorithm to Prove Z/p is a Field

A bit simpler:
Consider 1, x, x**2, x**3, …, x**p .
These are 1+p elements in Z_p, hence two are equal by the pigeon-hole principle:
x**i = x**j for i>j.
Since x!=0, division by x**j yields x**(j-i) = 1.
Hence, the inverse of x is x**(-1) = x**(i-j-1).

Sidenote
It suffices to take p elements in Z_p \ {0} as x**i is nonzero for all i.

Your proof still depends on the fact that in Z_p, ax=bx implies x=0 or a=b [otherwise x**(j-i) * x**j = x**i wouldn’t imply x**(j-i)=1 ==> without mentioning that, it looks like the proof works for 2 in Z_6.]

In (2): s/bc/bx/

A bit simpler:

Consider 1, x, x**2, x**3, …, x**p .

These are 1+p elements in Z_p, hence two are equal by the pigeon-hole principle:

x**i = x**j for i>j.

Since x!=0, division by x**j yields x**(j-i) = 1.

Hence, the inverse of x is x**(-1) = x**(i-j-1).

Sidenote

It suffices to take p elements in Z_p \ {0} as x**i is nonzero for all i.

Your proof still depends on the fact that in Z_p, ax=bx implies x=0 or a=b [otherwise x**(j-i) * x**j = x**i wouldn’t imply x**(j-i)=1 ==> without mentioning that, it looks like the proof works for 2 in Z_6.]