Prove that if and [j] are equivalence classes modulo

  • Thread starter leilei
  • Start date
  • #1
8
0

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
188
1
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
HallsofIvy
Science Advisor
Homework Helper
41,833
956
For (1) use the fact that, if i and j are equivalent mod n, then i- j is a multiple of n.
 

Related Threads on Prove that if and [j] are equivalence classes modulo

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
4K
Replies
10
Views
3K
Replies
11
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
8K
Top