Diophantine and coprime solutions x,y

  • Thread starter thomas430
  • Start date
In summary, for the linear diophantine equation d=ax+by, it is necessary for x and y to be coprime. This is because if x and y are not coprime, the equation becomes d= m(au+bv) where m is a common factor of x and y. However, since d=(a,b), it is impossible for d to be divisible by m, which contradicts the equation. Therefore, x and y must be coprime in order for the equation to hold.
  • #1
thomas430
17
0
Hi everyone,

I saw that for the linear diophantine equation [tex]d=ax+by[/tex], where d=(a,b), that x and y must be coprime.

Why is this? I feel like there are properties of coprime numbers that I am not aware of, because there are a few things like this that I have encountered.

Any help appreciated :-)


Thomas.
 
Physics news on Phys.org
  • #2
If x and y are NOT coprime, that is, if x= mu and y= mv for some integers m, u, and v, then the Diophantine equation becomes d= amu+ bmv= m(au+bv). Since the right hand side is divisible by m, the left side, d, must be also, say, d= mc. Then we could divide the entire equation by m to get the simpler equation c= au+ bv. But since d= (a,b) that is impossible.
 
  • #3
Oh! So d /should/ divide c, because d=(a,b)... but this contradicts d=mc, which suggests d cannot divide c, as d > c. (as m>1 because m=(x,y) and we said that (x,y) != 1)

Thanks, HallsofIvy :-)
 

1. What is a Diophantine equation?

A Diophantine equation is a polynomial equation in two or more variables where only integer solutions are allowed. These equations are named after the ancient Greek mathematician Diophantus, who studied them extensively.

2. How do you find solutions to a Diophantine equation?

Finding solutions to a Diophantine equation often involves using techniques from number theory and algebra. Some common methods include factoring, substitution, and modular arithmetic. In some cases, advanced techniques such as elliptic curves or continued fractions may be used.

3. What is a coprime solution?

A coprime solution to a Diophantine equation is a solution where the two or more variables have no common factors other than 1. In other words, the greatest common divisor of the variables is 1.

4. Why are Diophantine equations important?

Diophantine equations have applications in many areas of mathematics and science, including number theory, cryptography, and coding theory. They also provide a challenging and interesting area of study for mathematicians.

5. Can all Diophantine equations be solved?

No, not all Diophantine equations have solutions. In fact, some equations may have an infinite number of solutions, while others may have no solutions at all. It is an ongoing area of research to determine which equations have solutions and how to find them.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
583
Replies
4
Views
668
  • Linear and Abstract Algebra
Replies
1
Views
3K
  • Linear and Abstract Algebra
Replies
21
Views
8K
  • Linear and Abstract Algebra
Replies
2
Views
696
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
4K
  • Linear and Abstract Algebra
Replies
13
Views
6K
Back
Top