Prove that ⟨[a]⟩=⟨[b]⟩ in Z_n iff gcd(a,n)=gcd(b,n).

ucatzABI

ucatzABI

Answered question

2022-11-30

Prove that [ a ] = [ b ] in Z n iff gcd ( a , n ) = gcd ( b , n )

Answer & Explanation

tezeuszxcL

tezeuszxcL

Beginner2022-12-01Added 14 answers

One problem with your proof is that we cannot deduce [ a ] = [ b ] from [ a ] = [ b ] . For example, in ( Z 10 , + 10 ), we have that
[ 3 ] = ( { [ 3 ] , [ 6 ] , [ 9 ] , [ 2 ] , [ 5 ] , [ 8 ] , [ 1 ] , [ 4 ] , [ 7 ] } , + 10 ) = ( Z 10 , + 10 ) = ( { [ 7 ] , [ 4 ] , [ 1 ] , [ 8 ] , [ 5 ] , [ 2 ] , [ 9 ] , [ 6 ] , [ 3 ] } , + 10 ) = [ 7 ] ,
yet
[ 3 ] = { 3 + 10 k k Z } { 7 + 10 Z } ( because  3 7 + 10 0  for any  0 Z ) = [ 7 ] .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?