Can Bezout's Theorem Prove Coprime Relationship in Modular Arithmetic?

  • Context: Undergrad 
  • Thread starter Thread starter twodice
  • Start date Start date
  • Tags Tags
    Theorem
Click For Summary
SUMMARY

This discussion centers on using Bézout's Theorem to demonstrate the coprimality of integers x and y in the context of modular arithmetic. The theorem states that for integers a and b, if d = gcd(a, b), then there exist integers x and y such that ax + by = d. The key question posed is whether x and y can be proven to be coprime, specifically if (x, y) = 1, under the condition that d = gcd(a, b). The conversation suggests analyzing the implications of writing a and b in terms of their gcd to explore the coprimality relationship.

PREREQUISITES
  • Bézout's Theorem
  • Understanding of gcd (greatest common divisor)
  • Modular arithmetic concepts
  • Basic number theory principles
NEXT STEPS
  • Study the implications of Bézout's Theorem in number theory
  • Explore the properties of gcd and its relationship with coprimality
  • Investigate modular arithmetic applications in proofs
  • Learn about integer linear combinations and their significance
USEFUL FOR

Mathematicians, students of number theory, and anyone interested in the applications of Bézout's Theorem in proving relationships in modular arithmetic.

twodice
Messages
2
Reaction score
0
what is it?
 
Physics news on Phys.org
what I am trying to prove is that given the d=gdf(a,b) and ax+by=d prove that x and y are coprime or i guess (x,y)=1

i don't know whether or not to use modular arithmetic.
 
twodice said:
what I am trying to prove is that given the d=gdf(a,b) and ax+by=d prove that x and y are coprime or i guess (x,y)=1

i don't know whether or not to use modular arithmetic.


Hint write a and b as two parts each with one part being "gdf(a,b)" What happens to the "gdf" if (x,y) > 1
 

Similar threads

Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Spectral theorem for Hermitian matrices-- special cases
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Characterizing linear independence in terms of span
  • · Replies 3 ·
Replies
3
Views
2K
Graduate How Can We Prove the Extension of Bezout's Identity?
  • · Replies 13 ·
Replies
13
Views
7K
Undergrad Fundamental Theorem of Arithmetic - Bhattacharya et al
  • · Replies 5 ·
Replies
5
Views
4K
Graduate Modular forms, dimension and basis confusion, weight mod 1
  • · Replies 12 ·
Replies
12
Views
2K
Undergrad How is uniqueness about the determinant proved by this theorem?
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Congruence vs equality in mod arithmetic
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Which Mathematician's Theorem Linked Prime Numbers to Cryptography?
  • · Replies 4 ·
Replies
4
Views
6K
MHB How Do You Prove That sa + tb Divides gcd(a, b) in Bezout's Lemma?
  • · Replies 3 ·
Replies
3
Views
4K