Congruence Classes

  • Thread starter Juanriq
  • Start date
  • #1
42
0
Salutations! I believe I have one implications correct and I am looking for a push in the right direction for the other.

Homework Statement


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!
 

Answers and Replies

  • #2
737
0
You have [ab] = [1] in Zn. What does that mean in Z?
 
  • #3
42
0
In Z, it would mean that b is the multiplicative inverse of a, right? In Z we would just have ab = 1
 
  • #4
737
0
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.
 

Related Threads on Congruence Classes

  • Last Post
Replies
0
Views
3K
Replies
4
Views
4K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
936
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
0
Views
819
  • Last Post
Replies
4
Views
5K
Top