- #1

- 42

- 0

## 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].**

For the [itex](\Longleftarrow) [/itex]case, we know that the [itex]\gcd( a, n ) = 1[/itex] and we are trying to show [a]**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][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!Thanks in advance!