Results 1 to 3 of 3

Thread: Integers mod n is a field if and only if n is prime

  1. #1
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157

    Integers mod n is a field if and only if n is prime

    Define $\displaystyle \mathbb{Z}_n$ as the set of integers mod n: $\displaystyle \{0,1,...,n-1\}$ which is endowed with the operations $\displaystyle a+b = (a+b) \mod n$ and $\displaystyle a \cdot b = ab \mod n$. It appears that this ring with identity is a field if and only if $\displaystyle n$ is prime. The key is whether or not elements of $\displaystyle \mathbb{Z}_n$ have inverses (they don't when $\displaystyle n$ is composite).

    So I managed to prove that: if $\displaystyle n$ is not prime, then $\displaystyle a \in \mathbb{Z}_n$ has no inverse mod n. Now I am having trouble going the opposite way: how do I show that if $\displaystyle n$ is prime, i.e. - $\displaystyle gcd(a,n)=1$, then for all $\displaystyle a \in \mathbb{Z}_n$, $\displaystyle a$ has an inverse mod n? Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by Last_Singularity View Post
    Define $\displaystyle \mathbb{Z}_n$ as the set of integers mod n: $\displaystyle \{0,1,...,n-1\}$ which is endowed with the operations $\displaystyle a+b = (a+b) \mod n$ and $\displaystyle a \cdot b = ab \mod n$. It appears that this ring with identity is a field if and only if $\displaystyle n$ is prime. The key is whether or not elements of $\displaystyle \mathbb{Z}_n$ have inverses (they don't when $\displaystyle n$ is composite).

    So I managed to prove that: if $\displaystyle n$ is not prime, then $\displaystyle a \in \mathbb{Z}_n$ has no inverse mod n. Now I am having trouble going the opposite way: how do I show that if $\displaystyle n$ is prime, i.e. - $\displaystyle gcd(a,n)=1$, then for all $\displaystyle a \in \mathbb{Z}_n$, $\displaystyle a$ has an inverse mod n? Thanks!
    This is because in number theory, if $\displaystyle \gcd (a,n)=1$, then there exists $\displaystyle x,ax\mod n=1$.
    if not, we suppose $\displaystyle d=\min\{ax-kn|ax-kn>0\},d>1$.now we will show that $\displaystyle d|n$,which is impossible.
    suppose $\displaystyle ax-kn=d$
    Suppose $\displaystyle n=dq+r,0<r<d$
    then $\displaystyle n=(ax-kn)q+r\Leftrightarrow -axq+(kq+1)n=r\Leftrightarrow -axq\mod n=r$,but $\displaystyle r<d$,which will make contradiction.
    The only possible case is $\displaystyle r=0$,so $\displaystyle d|n$
    So $\displaystyle d=1$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,410
    Thanks
    1
    $\displaystyle \gcd (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1$ for some $\displaystyle x, y \in \mathbb{Z}$

    which by definition means: $\displaystyle ax \equiv 1 \ (\text{mod } n)$

    The least residue of $\displaystyle x$ is then a solution and is therefore the inverse.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relatively Prime Set of Integers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 15th 2010, 12:32 AM
  2. Relatively prime integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 26th 2010, 08:49 AM
  3. Replies: 3
    Last Post: Oct 21st 2009, 07:58 PM
  4. relatively prime integers....
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 16th 2008, 01:00 PM
  5. field of Integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2008, 01:43 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum