How to use the Euclidean Algorithm to find the gcd?

[Bellarosa]

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...

 

[Bellarosa]

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

 

[HallsofIvy]

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?

 

[Bellarosa]

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?

 

[HallsofIvy]

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.

 

[Bellarosa]

ok I understand...thank you

 

[Bellarosa]

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

 

[Bellarosa]

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?

 

[Dick]

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.