Congruence Classes


by Juanriq
Tags: classes, congruence
Juanriq
Juanriq is offline
#1
Oct17-10, 10:08 PM
P: 42
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 [latex] [a] \in \thinspace \mathbb{Z}_n [/latex]. Prove that there exists and element [latex][b] \in \thinspace \mathbb{Z}_n[/latex] such that [latex][a][b] = 1[/latex] if and only if [latex]\gcd (a,n) = 1[/latex].


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



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

Thanks in advance!
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Tedjn
Tedjn is offline
#2
Oct18-10, 02:17 AM
P: 740
You have [ab] = [1] in Zn. What does that mean in Z?
Juanriq
Juanriq is offline
#3
Oct18-10, 08:31 AM
P: 42
In Z, it would mean that b is the multiplicative inverse of a, right? In Z we would just have ab = 1

Tedjn
Tedjn is offline
#4
Oct18-10, 07:41 PM
P: 740

Congruence Classes


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.


Register to reply

Related Discussions
Basic general ed classes before classes for 4 yr Bachelor's degree? Academic Guidance 5
solutions to na=0 (mod m) Linear & Abstract Algebra 4
Congruence Classes in Quadratic Integers Calculus & Beyond Homework 4
congruence classes General Math 1
congruence help Linear & Abstract Algebra 5