# Prove that if and [j] are equivalence classes modulo

1. Apr 15, 2008

### leilei

Prove that if and [j] are equivalence classes modulo

1. Prove that if and [j] are equivalence classes modulo n such that =[j], then gcd(i,n)=gcd(j,n)

2. Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.

plz help

2. Apr 23, 2008

### mhill

the second part is the easiest if c divides b then b=kc for k an integer

since gcd(a,b)=1 and gcd(a,c)=gcd(a,kb) then gcd(a,c)=1

3. Apr 23, 2008

### HallsofIvy

Staff Emeritus
For (1) use the fact that, if i and j are equivalent mod n, then i- j is a multiple of n.