Thread: proof on inverse modulo

Hi,
I need help with this problem.

Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m.
[hint: assume that there are 2 solutions b and c of the congruence ax==1(mod m). No need to prove that b==c (mod m) ]

I can fin the solution by starting with the fact that gcd(a,m)=1
--> S*a+ T*m=1 --> S*a+ T*m=1 (mod m) and so on....
But this way of showing this..I don't get it.

I tried something like:

a*b==1(mod m) and c*a==1(mod m)-->a*b==c*a(mod m)
-->b==c (mod m)
then I dont know how to continue..
Can I have some help please?
B

Originally Posted by braddy

Hi,
I need help with this problem.

Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m.
[hint: assume that there are 2 solutions b and c of the congruence ax==1(mod m). No need to prove that b==c (mod m) ]

I can fin the solution by starting with the fact that gcd(a,m)=1
--> S*a+ T*m=1 --> S*a+ T*m=1 (mod m) and so on....
But this way of showing this..I don't get it.

I tried something like:

a*b==1(mod m) and c*a==1(mod m)-->a*b==c*a(mod m)
-->b==c (mod m)
then I dont know how to continue..
Can I have some help please?
B

For n>1 consider the set,
G_n={gcd(x,n)=1|1<=x<=n}
It can be shown from group theory this is a group under multiplication mudolo n.

Proof:

Closure: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.

AssociativityTrivial. Since G_n is a proper algebraic binary structuce of Z_n.

IdentityTrivial, 1 is in G_n.

Existence of inverse.
Let,
a_1,a_2,...,a_k
Be all the elements in G_n
Let a be in G_n
Form the numbers,
aa_1,aa_2,...,aa_k
Note if,
aa_i=aa_j (mod n)
Then since gcd(a,n)=1 we have,
a_i=a_j
But that is not possible for 1<=a_i,a_j<=n
Thus, all,
aa_1,aa_2,...,aa_k
Are distinct.
By Dirichlet's Pigeonhole Principle
It consits of,
a_1,a_2,...a_k
In which one is 1 (identity)
Q.E.D.

Now the equation,
ax=1(mod n)
For gcd(a,n)=1
Is asking to solve this linear equation in the group G_n
Which we know always have a unique solution.

Originally Posted by ThePerfectHacker

For n>1 consider the set,
G_n={gcd(x,n)=1|1<=x<=n}
It can be shown from group theory this is a group under multiplication mudolo n.

Proof:

Closure: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.

AssociativityTrivial. Since G_n is a proper algebraic binary structuce of Z_n.

IdentityTrivial, 1 is in G_n.

Existence of inverse.
Let,
a_1,a_2,...,a_k
Be all the elements in G_n
Let a be in G_n
Form the numbers,
aa_1,aa_2,...,aa_k
Note if,
aa_i=aa_j (mod n)
Then since gcd(a,n)=1 we have,
a_i=a_j
But that is not possible for 1<=a_i,a_j<=n
Thus, all,
aa_1,aa_2,...,aa_k
Are distinct.
By Dirichlet's Pigeonhole Principle
It consits of,
a_1,a_2,...a_k
In which one is 1 (identity)
Q.E.D.

Now the equation,
ax=1(mod n)
For gcd(a,n)=1
Is asking to solve this linear equation in the group G_n
Which we know always have a unique solution.

OK!! thanks ThePerfectHacker