Results 1 to 3 of 3

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

    So I managed to prove that: if n is not prime, then 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 n is prime, i.e. - gcd(a,n)=1, then for all a \in \mathbb{Z}_n, 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 \mathbb{Z}_n as the set of integers mod n: \{0,1,...,n-1\} which is endowed with the operations a+b = (a+b) \mod n and a \cdot b = ab \mod n. It appears that this ring with identity is a field if and only if n is prime. The key is whether or not elements of \mathbb{Z}_n have inverses (they don't when n is composite).

    So I managed to prove that: if n is not prime, then 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 n is prime, i.e. - gcd(a,n)=1, then for all a \in \mathbb{Z}_n, a has an inverse mod n? Thanks!
    This is because in number theory, if \gcd (a,n)=1, then there exists x,ax\mod n=1.
    if not, we suppose d=\min\{ax-kn|ax-kn>0\},d>1.now we will show that d|n,which is impossible.
    suppose ax-kn=d
    Suppose n=dq+r,0<r<d
    then n=(ax-kn)q+r\Leftrightarrow -axq+(kq+1)n=r\Leftrightarrow -axq\mod n=r,but r<d,which will make contradiction.
    The only possible case is r=0,so d|n
    So 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,408
    \gcd (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1 for some x, y \in \mathbb{Z}

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

    The least residue of 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, 01:32 AM
  2. Relatively prime integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2010, 09:49 AM
  3. Replies: 3
    Last Post: October 21st 2009, 08:58 PM
  4. relatively prime integers....
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 16th 2008, 02:00 PM
  5. field of Integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2008, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum