Results 1 to 2 of 2

Math Help - Modulo Classes Problems

  1. #1
    Member
    Joined
    Mar 2008
    From
    Acolman, Mexico
    Posts
    118

    Modulo Classes Problems

    Hello, I need help with the following problem


    Let n \in \mathbb{N} and a \in \mathbb{Z}, so [a] \in \mathbb{Z}_n. Prove that there exists an integer b such that [a][b]=[1] if and only if gcd(a,n)=1.
    Last edited by akolman; February 8th 2009 at 11:19 PM. Reason: Solved one!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    That can be done using the fact that if n and m are two integers, gcd(n,m)=1 \Leftrightarrow \exists u,v\in\mathbb{Z}\ \text{such that}\ un+vm=1. (Bezout's identity)

    gcd(a,n)=1\Rightarrow \exists u,v\in \mathbb{Z}\ \text{s.t.}\ ua+vn=1 so b=u is a solution.

    \exists b\in\mathbb{Z}\ \text{s.t.}\ [a][b]=1\Rightarrow \exists k\in\mathbb{Z}\ ab-1=kn\Rightarrow \exists u,v\in\mathbb{Z}\ \text{s.t.}\ ua+vn=1 (with u=b and v=-k) therefore gcd(a,n)=1.
    Last edited by clic-clac; February 9th 2009 at 06:52 AM. Reason: classes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence modulo and equivalence classes
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 9th 2010, 05:28 AM
  2. Conjugacy classes - two problems.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 17th 2010, 11:53 PM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. classes
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 8th 2009, 04:28 PM
  5. modulo and congruence classes
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 3rd 2008, 02:37 PM

Search Tags


/mathhelpforum @mathhelpforum