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.

  1. 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.
  2. Prove that this implies ax=bx implies a=b or x=0
  3. Therefore, the function x->ax is one-to-one, on a finite set.
  4. Therefore, it is onto.
  5. Therefore, 1 is in the image. Or, there exists an a, ax=1.
  6. QED
Advertisements

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

  1. Rani says:

    In (2): s/bc/bx/

  2. Rani says:

    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.

    • moshez says:

      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.]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: