Linear Diophantine Equations

  • Thread starter Bellarosa
  • Start date
  • Tags
    Linear
In summary: You get 1.In summary, the Japanese businessman exchanged 39 US dollars and 94 Canadian dollars for a total of 15286 yen, receiving 122 yen for each US dollar and 112 yen for each Canadian dollar. The correct equation to solve is 122x+ 112y= 15286, where x represents the number of US dollars and y represents the number of Canadian dollars. The solutions to this equation are x= 39 and y= 94. The Euclidean Algorithm is used to find the greatest common divisor, but the total number of yen can be found without incorporating it.
  • #1
Bellarosa
48
0
1. A Japanese businessman returning from a trip in North America exchanges his US and Canadian dollars for yen. If he receives 15286 yen, and received 122 yen for each US and 112 yen foer eac Canadian dollar, how many of each type of currency did he exchange?

2. I know in solving this type of equations you find the gcd, I did that but I did not get the exact answer as the book did



3. Let x = #of yens for each US and y = # of ens for each Canadian
122 x + 112 y = 15286
the gcd(122,112) = 2 which divides 15286
by using the Euclidean Algorithm I found x to be -11 and y = 12
so I have 122(-11) 7643 + 112(12) 7643 = (2) 7643
122(-84073) + 112(91716) = 15286, along with other solutions x = -84073 + 112t and y = 91716 - 122t, which I think does not apply here...
the book's answer is 39 US and 94 Cand or 95 US and 33 Cand.
From this it seems as if they just used the Euclidean Algorithm without incorporating the gcd...
 
Physics news on Phys.org
  • #2
ok I think I see what I missed...there are two equations x + y = 15286, and 122 x + 112y = ? I don't know exactly what it should be... I know I am missing something but I can't quite figure it out
 
  • #3
Bellarosa said:
1. A Japanese businessman returning from a trip in North America exchanges his US and Canadian dollars for yen. If he receives 15286 yen, and received 122 yen for each US and 112 yen foer eac Canadian dollar, how many of each type of currency did he exchange?

2. I know in solving this type of equations you find the gcd, I did that but I did not get the exact answer as the book did



3. Let x = #of yens for each US and y = # of ens for each Canadian

Here's your first mistake. You already know that he received 122 yen for each US dollar and 112 yen for each Canadian dollar. You don't need to "let" them equal anything. What you mean is that x= number of US Dollars exchanged and y= number of Canadian Dollars exchanged.

122 x + 112 y = 15286
Now this is correct.

the gcd(122,112) = 2 which divides 15286
by using the Euclidean Algorithm I found x to be -11 and y = 12
For what problem? NOT for 122x+ 112y= 15286 nor for 61x+ 56y= 7643.
x= -11 and y= 12 satisfy 61x+ 56y= 1. Be sure to say what you mean!

so I have 122(-11) 7643 + 112(12) 7643 = (2) 7643
122(-84073) + 112(91716) = 15286, along with other solutions x = -84073 + 112t and y = 91716 - 122t, which I think does not apply here...
the book's answer is 39 US and 94 Cand or 95 US and 33 Cand.
From this it seems as if they just used the Euclidean Algorithm without incorporating the gcd...

The general solutions x= -84073+ 122t and y= 91716- 122t are crucial here! In order that x and y represent values in US and Canadian Dollars, they must be positive. Your answer "x= -84073 and y= 91716" is impossible because x is not positive. In order that x= -84073+ 112t> 0, you must have t> 84073/112= 750.6 so t must be at least 751. In order that y= 91716- 122t> 0, you must have t< 91716/122= 751.8 so t cannot be more than 751. If you take t= 751, what are x and y?
 
Last edited by a moderator:
  • #4
Ok I knew the answer couldn't be negative and I think I missed what the problem was saying by focusing on the general way of solving these types of equations. Just to be clear, are you saying that because we are given the amount of yens both in US and Cand. that all i have to solve is 122 x + 112 y = 15286?
 
  • #5
I am saying that because x is the number of US dollars, 122x is the number of yen the US dollars convert to and because y is the number of Canadian dollars, 112y is the number of yen the Canadian dollar convert to. So the total number of yen is, as you say, 122x+ 112y= 15286 yen. Yes, that is the equation you want to solve.

(You don't need to carry that GCD of "2" along. Solving 61x+ 56y= 7643 is simpler and gives exactly the same solutions.
 
  • #6
ok I understand...thank you
 
  • #7
ok I am using the Euclidean Algorithm to find the gcd of 111 and 169 which I know is 1 but the EA says otherwise

169 = 1(111) + 58
111 = 1(58) + 53
58 = 1(53) + 5
53 = 10(5) + 3
5 = 1(5) + 0
I can't understand why I am getting 3 when 3 does not even divide 169, neither does it divide 11798 in the equation 111x + 169y = 11798
 
  • #8
or is it because I ended the last entry wrong...should I continue as follow?
5 = 1(3) +2
3 = 1(2) + 1
2 = 1(2) + 0
why can't I just end it at 5?
 
  • #9
Bellarosa said:
ok I am using the Euclidean Algorithm to find the gcd of 111 and 169 which I know is 1 but the EA says otherwise

169 = 1(111) + 58
111 = 1(58) + 53
58 = 1(53) + 5
53 = 10(5) + 3
5 = 1(5) + 0
I can't understand why I am getting 3 when 3 does not even divide 169, neither does it divide 11798 in the equation 111x + 169y = 11798

Think about what each line is telling you. The first says gcd(111,169)=gcd(111,58). The second that that is equal gcd(53,58). The third that that is equal gcd(53,5). The fourth that that is equal gcd(3,5). The next line doesn't fit. If you continue as you did in the other post, that becomes gcd(2,3), gcd(2,1) and gcd(1,1). Now you can stop.
 

1. What is a Linear Diophantine Equation?

A Linear Diophantine Equation is an equation where the variables can only take integer values and the coefficients are also integers. It is written in the form of ax + by = c, where a, b, and c are integers, and x and y are the unknown variables.

2. How do you solve a Linear Diophantine Equation?

To solve a Linear Diophantine Equation, you can use the Extended Euclidean Algorithm or the Bezout's Identity. These methods involve finding the greatest common divisor (GCD) of the coefficients and using it to find the solutions to the equation.

3. What are the applications of Linear Diophantine Equations?

Linear Diophantine Equations have various applications in mathematical modeling, cryptography, and number theory. They are used to solve problems related to finding integer solutions to equations and are also used in optimization problems.

4. Can all Linear Diophantine Equations have solutions?

No, not all Linear Diophantine Equations have solutions. Some equations may have no solutions, while others may have infinite solutions. The existence of solutions depends on the coefficients of the equation and their relationship with the GCD.

5. How do Linear Diophantine Equations differ from Linear Equations?

The main difference between Linear Diophantine Equations and Linear Equations is that the former only allows integer solutions, while the latter can have any real number as a solution. Additionally, the coefficients in Linear Diophantine Equations are also integers, whereas they can be any real number in Linear Equations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
969
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
  • Introductory Physics Homework Help
Replies
2
Views
9K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
7
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
7
Views
3K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • Atomic and Condensed Matter
Replies
4
Views
6K
Replies
3
Views
3K
Back
Top