A good math problem... and then a couple neat tricks

[Jothaxe]

Ok, time for trick number 1.

This is known as Euclid's Algorithm.

The algorithm is normally something you can use to find the GCD or greatest common devisor of two numbers. Maybe some of you have seen it? To do it take 21 and divide by 17, noting the remainder. Then divide 17 by the remainder and get a second remainder. Then divide the first remainder by the second... like this:

21 = 17*1 + 4
17 = 04*4 + 1
04 = 01*4 + 0

Note that I only write the number "4" as "04" and "1" as "01" to try to line up the columns.

Because we are able to start with 21 and 17 and end up with a remainder of 0 only after dividing by 1, this means that the GCD of the two numbers is one, which is obvious if you just look at the two numbers...

Another example: say we started with 66 and 30

66 = 30*2 + 6
30 = 06*5 + 0

here we get a remainder of zero when we divide by 6 in the last line, se the GCD of 30 and 66 is 6.


We could probably see that the GCD of 66 and 30 is 6 without using this method, but it becomes very useful when the numbers start to get bigger...



So this is the first of two tricks that are necessary for solving this sort of problem.

The second trick is a matter of taking the numbers that I have highlighted above and reconstructing the original numbers from them.

I will post this soon.

Does this make sense to anybody? Its kinda hard to explain well on the forum... does anybody have any questions so I can try to clarify?

 

[blueghost75]

i think this was one of the two types of math problems that I missed on the SAT. (I only missed two, I think....)

I'm curious to know the answer. Unfortunatly, I have suffered from a really crappy math teacher for the past year and a half. I will have the same guy in AP Calculus next year too, unfortunatly.....

 

[Jothaxe]

<< Unfortunatly, I have suffered from a really crappy math teacher for the past year and a half. I will have the same guy in AP Calculus next year too, unfortunatly..... >>



That is terrible to hear. I think that so many more people would love math if they had had the same teachers that I was lucky enough to get. Its amazing how much difference a good teach can make!


BTW, here is a mini problem to see if anybody understand my post about how to use Euclids Algorithm:


What is the Greatest Common Devisor of the numbers 195 and 182 ???

if you solve this, please show your work, so other people can learn how you do it...


*edit*

after someone solves this, I will teach you the last trick, known as &quot;The Magic Box&quot;

-jothaxe

 

[Imaginer]

<< Seems pretty straightforward, why has no one said it?

the answer is:

(x,y) = ( -4 + 17n, 5 - 21n )

where n is any integer (....-3, -2, -1, 0, 1, 2, 3....)

- seb >>



I knew it had to be a sequence with n. But I was away.

 

[nd]

<< What is the Greatest Common Devisor of the numbers 195 and 182 ???

if you solve this, please show your work, so other people can learn how you do it...
>>



195 = 182*1 + 13
182 = 013*14 + 0

So the answer is 13.

Magic box please

 

[mundania]

MAGIC BOX!

 

[goodoptics]

nm

 

[Static911]

dang...u guys too smart

static911

 

[Jothaxe]

Its pretty hard to explain the magic box just because of the limitations of the thread. So I am just going to write in down on a piece of paper, and then scan in so you can look at the work. Sorry, but the picture is a little bit large... pictures of the box

The idea is to take the divisors you get from Euclid's Algorithm and use them to reconstruct the starting numbers. For example, let us use 21 and 17 from above...

Notice that in descending order, the divisors are 1,4,4. I highlighted them earlier so I could emphasize them now.

1) The magic box looks like this to start with: (figure 1)

2) We place the divisors we found (1,4,4) in the slots at the tops like this: (figure 2)

3) Next we take the divisor &quot;1&quot; (from spot marked a in figure 1) and multiply it with the number in the square to its bottom left corner. In that square is a &quot;1&quot; also, so the total is now &quot;1.&quot; To this we add the number to the left of the multiplier, and write it in the square to the right of the multiplier. (figure 3)

4) Now repeat this with the middle multiplier &quot;4.&quot; Since 4*1+1 = 5 we write this in the next box. Then for the third multiplier take 4*5 + 1 = 21 and write this in the last box on the top (figure 4)

5) Now do the same operation for the bottom row, pretending the top isnt there at all. First we get 1*0 + 1 =1. Then we take 4*1 + 0 = 4. Finally 4*4 +1 = 17. (figure 5)


So now we have the box filled out completely... notice how we have 21 and 17 back again? Notice also how the numbers to the left of 21 &amp; 17 have nearly the same ratio (i.e. 21/17 is close to 5/4) This is no coincidence.


Now look and realize that ( 5, -4 ) were a solution to the original problem for 21x + 17y = 1


This will always be the case, as long as you pick two numbers that have a GCD of 1. Try it with some other numbers to see for yourself. Like with


37x + 22y = 1


use Euclids algorithm to get (1,1,2,7) as the factors in the top spots of the box (four columns this time) and see what numbers lie to the left of 37 &amp; 22. This will be a solution to the above equation (if you take one of them to be negative.)


Now I know this was a lot to explain without seeing me write it down, so please ask questions so I can clarify anything confusing.



If you understand what I have explained, then try to use the magic box on 37 &amp; 22 to solve the equation above in the integers.

What is the solution the box gives you??? Anybody know???

 

[nd]

<< If you understand what I have explained, then try to use the magic box on 37 &amp; 22 to solve the equation above in the integers.

What is the solution the box gives you??? Anybody know??? >>

Here's the box (formatted best I can)

[=][=][1][1][2][7]
[0][1][1][2][5][37]
[1][0][1][1][3][22]

The solution that seems to work is x=3, and y=-5. Is there an easier way to tell which things to throw out? You told us that the one to the left of 37 and 22 would be correct. Why are the 2 and 1 useless? What if there were 2 answers? What's the systematic way after you get the box to get the answers other than &quot;just figuring it out&quot;?

 

[Jothaxe]

<< The solution that seems to work is x=3, and y=-5. Is there an easier way to tell which things to throw out? You told us that the one to the left of 37 and 22 would be correct. Why are the 2 and 1 useless? What if there were 2 answers? What's the systematic way after you get the box to get the answers other than &quot;just figuring it out&quot;? >>



This is correct!

The 2 and the 1 arent exactly useless, since they are also approximations for the value 37/22

Notice that each column of the box gives another approximation, each alternating above and below under you get to 37/22. That is:

0/1 = too small try again
1/0 = way too big, go smaller
1/1 = too small, but closer
2/1 = pretty close but too large
5/3 = good approximation
37/22 = is the actual ratio of two numbers!

In the case of solving the linear diophantine equation though, we use the magic box to get the closest ratio without actually writing the original, i.e. the numbers adjacent to the originals...

because 37*3 - 22*5 = 1 which is what we want to solve...

that is, x = 3 and y = -5

Now that we have one solution, we can find the rest using the method above, noting that 37*(22n) - 22*(37n) =
0 and adding this to our first solution as before...

the magic box can be used in other ways too, but I like the way it helps you solve the diophantine equation.



Btw, if anyone really wants to test their skills, solve the one I posted above:

132412343*x + 34208309*y = 1


Good luck, and post your work if you can solve it!

-jothaxe

 

[mikef208]

When i was in high school, my algebra teacher should us a forumla, to make 0=1. The formula involved a variable, and the only problem with it was if you used a certain number, then you ended up dividing by 0, which we all know is a no no, but for the laymen when you should it to them, they all thought you were the devil and wanted to burn you on a stake?

Does anyone know the formula I speak of, cause I can't remember it.

 

[MereMortal]

132412343*x + 34208309*y = 1

[o][o][3][1][06][01][02][001][004][0002][0002][00010][000021][000001][00000022][00000002][00000001]
[0][1][3][4][27][31][89][120][569][1258][3085][32108][677353][709461][16285495][33280451][49565946]
[1][0][1][1][07][08][23][031][147][0325][0797][08295][174992][183287][04207306][08597899][12805205]

x=12805205
y=-49565946

Other solutions follow by explained previous methods. (Like I haven't done enough! )

 

[nd]

I got the same answer, except I included the last &quot;2&quot; column in my square table. I also used 2 calculator programs I wrote quickly on my TI-86 to assist in the tedious calculations (one for Euclid's method and one for the square)

 

[Jothaxe]

MereMortal, nd

You guys are both awesome, and extremely quick learners. Not bad considering the limited amount of information I was actually able to explain on the forum.

Although I didnt do the calculation out, I checked the answer you post MereMortal and it is definately correct.

Perhaps now you can see how this method can be applied to the thread j@cko posted about the math problem involving &quot;farm animals&quot;


So the general form of the diophantine equation is:

ax + by = 1 where a,b,x,y are all integers.


A follow up question:

Can you tell me the necessary constraint on a &amp; b so that there are solutions to this equation?

hint: consider the simple example of

15x + 5y = 1 for example... what goes wrong with this choice of a &amp; b???

 

[nd]

<< A follow up question:

Can you tell me the necessary constraint on a &amp; b so that there are solutions to this equation?

hint: consider the simple example of

15x + 5y = 1 for example... what goes wrong with this choice of a &amp; b??? >>

Hmm. The example doesn't work because 5 is the GCD, and hence there is only 1 column in the magic square (3:1). This is the exact same ratio as A:B, so there is obviously no column before it to give us a solution. This is a really informal way to describe the constraint though, so I'll try to be more precise in a second when I edit this.

Edit: Ok, I'm going to guess that the constraint is that the A and B are not equal to the GCD(A,B). In other words, A is not evenly divisible by B, and vice versa.

 

[kingz]

Dude, its summer, stop with math!

 

[kxy]

Dude, it is summer, I want more math tricks!!!

 

[Pretender]

crazy thing is something like this was on the SAT today:

2x + 3y = 201
x and y are integers

a) The number of possible values of x are greater than the number of possible values of y
b) The number of possible values of y are greater than the number of possibile values of x
c) The number of possibilities of x is equal to the number of possibilities of y
d) None of the above can be determined using the given info


I put c, because for all valid x's there is 1 valid y, and vice versa.

 

[Jothaxe]

<< I put c, because for all valid x's there is 1 valid y, and vice versa. >>



Pretender, that is the correct answer, nice work!

 

[Jothaxe]

<< Edit: Ok, I'm going to guess that the constraint is that the A and B are not equal to the GCD(A,B). In other words, A is not evenly divisible by B, and vice versa. >>



nd, good guess, and it is true that if the GCD of a,b is either a or b, then you will not be able to find a solution to

ax + by = 1

The exact answer is that you will always be able to find an integer solution to the equation iff

GCD of a,b = 1.

In other words the two numbers should be &quot;relatively prime.&quot;

-jothaxe