Prove that if and [j] are equivalence classes modulo

So, if i= j+ kn for some integer k, then gcd(i,n)= gcd(j+ kn, n)= gcd(j,n). But since [i]=[j], i and j are equivalent mod n, so i- j is a multiple of n, meaning gcd(i,n)=gcd(j,n).
  • #1
leilei
8
0
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.

please help
 
Physics news on Phys.org
  • #2
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
For (1) use the fact that, if i and j are equivalent mod n, then i- j is a multiple of n.
 

1. What does it mean for two elements to be in the same equivalence class modulo?

Two elements are in the same equivalence class modulo if they produce the same remainder when divided by a given number.

2. How do you prove that two elements are in the same equivalence class modulo?

To prove that two elements are in the same equivalence class modulo, you must show that they produce the same remainder when divided by a given number, also known as the modulus.

3. Can two elements be in multiple equivalence classes modulo?

No, an element can only be in one equivalence class modulo. This is because the elements in an equivalence class are all considered equivalent and produce the same remainder when divided by the modulus.

4. What is the significance of equivalence classes modulo in mathematics?

Equivalence classes modulo are used to group elements that are considered equivalent based on a specific property. This allows for easier analysis and comparison of elements in a mathematical system.

5. How are equivalence classes modulo used in real-life applications?

Equivalence classes modulo are commonly used in computer science and coding, particularly in cryptography and error correction. They are also used in number theory and algebra to study patterns and relationships between numbers.

Similar threads

I Understanding the Results of gcd(x,n)
    • Linear and Abstract Algebra
Replies
8
Views
891
Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?
    • Precalculus Mathematics Homework Help
Replies
14
Views
948
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
    • Linear and Abstract Algebra
Replies
3
Views
1K
Solve ## 25x\equiv 15\pmod {29} ##.
    • Precalculus Mathematics Homework Help
Replies
1
Views
791
MHB GCD of a and b: Proving $gcd(a',b')=1$
    • Linear and Abstract Algebra
Replies
4
Views
1K
I Algebra Homomorphisms as Subsets of the Cartesian Product
    • Linear and Abstract Algebra
Replies
2
Views
831
A Equivalence Relation to define the tensor product of Hilbert spaces
    • Linear and Abstract Algebra
Replies
1
Views
1K
I Proof about a positive definite matrix
    • Linear and Abstract Algebra
Replies
12
Views
1K
I Fourier Transformation on a Ring
    • Linear and Abstract Algebra
Replies
11
Views
1K
A How do we prove that a nonzero nilpotent Lie algebra has a nontrivial center?
    • Linear and Abstract Algebra
Replies
9
Views
1K

Hot Threads

Recent Insights

Back
Top