Proving Congruence Classes: [a][b]=1 iff gcd(a,n)=1

  • Thread starter Juanriq
  • Start date
  • Tags
    Classes
In summary, the conversation is about proving that for an integer n and an element [a] in Zn, there exists another element [b] in Zn such that [a][b] = 1 if and only if the greatest common divisor of a and n is 1. The conversation also discusses the attempt at a solution for the first implication and further clarification on the meaning of [ab] = [1] in Z.
  • #1
Juanriq
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!
 
Physics news on Phys.org
  • #2
You have [ab] = [1] in Zn. What does that mean in Z?
 
  • #3
In Z, it would mean that b is the multiplicative inverse of a, right? In Z we would just have ab = 1
 
  • #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.
 

1. What is the definition of congruence classes?

Congruence classes are sets of integers that have the same remainder when divided by a given integer. They are denoted by [a] and are used to group integers that are equivalent under a certain modulus.

2. How do you prove that [a][b]=1 if gcd(a,n)=1?

To prove that [a][b]=1 if gcd(a,n)=1, we must show that [a][b] is equivalent to 1 under the given modulus n. This can be done by using the definition of congruence classes and the properties of the greatest common divisor.

3. What is the significance of gcd(a,n) in proving congruence classes?

The greatest common divisor, gcd(a,n), plays a crucial role in proving congruence classes. It helps us determine if two integers are relatively prime, which is necessary for showing that their congruence class pair is equivalent to 1.

4. Can congruence classes be used with any modulus?

Yes, congruence classes can be used with any modulus. However, it is important to note that the properties of congruence classes may vary depending on the modulus used.

5. How are congruence classes related to modular arithmetic?

Congruence classes are a fundamental concept in modular arithmetic. They allow us to group integers that are equivalent under a certain modulus, which is the key concept in modular arithmetic. Additionally, congruence classes help us manipulate and solve equations in modular arithmetic.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
624
  • Calculus and Beyond Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
743
  • Calculus and Beyond Homework Help
Replies
3
Views
451
  • Calculus and Beyond Homework Help
Replies
1
Views
399
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
439
Back
Top