Salutations! I believe I have one implications correct and I am looking for a push in the right direction for the other.(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums - The Fusion of Science and Community**

# Congruence Classes

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Congruence Classes

Loading...

**Physics Forums - The Fusion of Science and Community**