Prove that if and [j] are equivalence classes modulo

  • Context: Graduate 
  • Thread starter Thread starter leilei
  • Start date Start date
  • Tags Tags
    Classes Equivalence
Click For Summary
SUMMARY

This discussion focuses on proving properties of equivalence classes modulo n, specifically that if [i] and [j] are equivalence classes such that [i] = [j], then gcd(i, n) = gcd(j, n). Additionally, it establishes that if gcd(a, b) = 1 and c divides b, then gcd(a, c) = 1. The proofs utilize the definitions of equivalence classes and properties of the greatest common divisor (gcd).

PREREQUISITES
  • Understanding of equivalence classes in modular arithmetic
  • Knowledge of the greatest common divisor (gcd) and its properties
  • Familiarity with basic number theory concepts
  • Ability to manipulate algebraic expressions involving integers
NEXT STEPS
  • Study the properties of equivalence relations in modular arithmetic
  • Learn advanced gcd properties and their applications in number theory
  • Explore the implications of divisibility in integer arithmetic
  • Investigate the relationship between gcd and linear combinations of integers
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in modular arithmetic and its applications in proofs and problem-solving.

leilei
Messages
8
Reaction score
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
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
 
For (1) use the fact that, if i and j are equivalent mod n, then i- j is a multiple of n.
 

Similar threads

Undergrad Clarifications needed for an exercise in Hungerford's abstract algebra
  • · Replies 23 ·
Replies
23
Views
2K
Undergrad Equivalent definitons for primitive polynomials
  • · Replies 24 ·
Replies
24
Views
2K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?
  • · Replies 14 ·
Replies
14
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
MHB GCD of a and b: Proving $gcd(a',b')=1$
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Definition of minimal ideal using symbolic logic notation
  • · Replies 3 ·
Replies
3
Views
2K
MHB Properties of gcd's and relatively prime integers
  • · Replies 2 ·
Replies
2
Views
2K
Solve ## 25x\equiv 15\pmod {29} ##.
  • · Replies 1 ·
Replies
1
Views
2K