1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence Classes

  1. Oct 17, 2010 #1
    Salutations! I believe I have one implications correct and I am looking for a push in the right direction for the other.

    1. The problem statement, all variables and given/known data
    Let n be an integer and let [itex] [a] \in \thinspace \mathbb{Z}_n [/itex]. Prove that there exists and element [itex] \in \thinspace \mathbb{Z}_n[/itex] such that [itex][a] = 1[/itex] if and only if [itex]\gcd (a,n) = 1[/itex].

    2. The attempt at a solution
    For the [itex](\Longleftarrow) [/itex]case, we know that the [itex]\gcd( a, n ) = 1[/itex] and we are trying to show [a] = [1] in [itex]\mathbb{Z}_n[/itex] We know that [itex] \exists x,y \in \mathbb{Z}[/itex] such that
    [itex] ax + ny = 1 \Longrightarrow ax - 1 = -ny [/itex] but this implies that [itex] a b - 1 = vy[/itex] , where [itex] x = b[/itex] and [itex] v = -n[/itex] and also [itex] v| ab - 1[/itex].

    Now, for the other implications... uh little lost. [a] = [1] implies [ab] = [1]. Can I say that [0] = [n], so [1] = [n+1] = [n] + [1], therefore [ab] - [n] = [1]?

    Thanks in advance!
  2. jcsd
  3. Oct 18, 2010 #2
    You have [ab] = [1] in Zn. What does that mean in Z?
  4. Oct 18, 2010 #3
    In Z, it would mean that b is the multiplicative inverse of a, right? In Z we would just have ab = 1
  5. Oct 18, 2010 #4
    Yes, if ab = 1 in Z, that's right. What I actually wanted was for you to translate this statement as is into Z; that is, tell me what this equivalence class equality means. You've already done this to prove the backwards implication, so you know how. But it's the right place to start.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?