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

[Jothaxe]

As requested by mundania, here is a general problem that is easy to pose, and good to know how to solve:

I will introduce it with a concrete example first e.g. given



21x + 17y = 1



what integer values of x and y satisfy this equation?

can you state your answer in such a way that you include all solutions?


If anybody has guesses about how to do this, please post. If you have had enough number theory that you formally know how to solve, then you can give hints, but please dont post the solution immediately. Thanks!

*edit to make the example a bit easier*

 

[Atlantean]

0 for y and 1/21 for x, I think

 

[Jothaxe]

<< 0 for y and 1/21 for x, I think >>




Atlantean, thanks for the try. Although this is a valid solution in the real numbers, the problem here is to try to find a solution where x and y are both integers. They can be positive or negative, but they still have to be nice, whole numbers...

 

[Atlantean]

oh oops, I didn't see the integer partwell then how about 1/42 for x and 1/34 for y. does that work?

 

[miniMUNCH]

What Jothaxe posted is an equation to a straight line...that's all you need to know to present a solution.

And represent y in terms of x..ie (x, y[f(x)])

 

[Pretender]

get it in terms of y:

y=(1-21x)/17

plug it into a graphing calc

find all values where an integer val of x matches an integer val of y.

 

[Imaginer]

Yeah but that would get an infinite pair of x and y.

I think the answer he is looking for is what is the relation and patterns of the x and y values and based on that you can determine all of them based on the pattern.

 

[Pretender]

I've gotten these pairs of x/y vals so far:

-4, 5
-21, 26

13, -16
30, -37

 

[Pretender]

true, it doesn't show all numbers, but....blah!

 

[piku]

I could go into my trig notes from last semester and find out for you but... no

 

[Pretender]

alright, you could say that any x value such that (1-21x) is divisable by 17, and any y such that (1-17y) is divisible by 21.

 

[Jothaxe]

<< I've gotten these pairs of x/y vals so far:

-4, 5
-21, 26

13, -16
30, -37 >>



Good work Pretender. You have found some valid solutions in the integers. This was the first part of the problem!

And you have noticed that there is no limit to the number of solution pairs you can find, which is another part of the problem.

Now the trick is to look for a pattern in which solution pairs exist, and try to sum them up in one statement. This is the next part of the problem, and I think you are getting close to it...

 

[Imaginer]

So we know the points could be

( (1-21x)/17 , (1-17y)/x )

 

[Jothaxe]

<< I could go into my trig notes from last semester and find out for you but... no >>



Hmm... I dunno.

*Jothaxe scratches head*

I believe this problem cant be solved using any methods involving trigonometry. Trig is nice for real or even complex number problems, but it doesnt help much with the integers!

 

[Imaginer]

Looks parametric...

 

[Jothaxe]

<< So we know the points could be

( (1-21x)/17 , (1-17y)/x ) >>



You are on the right track too with this idea... in a way.


It is very useful to think about which points the line will go through, and which it will not. This wont give you the answer in itself, but it might help you visualize a method for finding it...

 

[downhiller80]

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

 

[miniMUNCH]

sebfrost:

*********************

edit: doh! you edited your post!

 

[Jothaxe]

^

 

[Jothaxe]

^

 

[Jothaxe]

So sebfrost has pretty much come to the correct general solution:


x = 17n - 4
y = 5 - 21n


where n is any integer (positive or negative of course)

*******************************************************

Now the follow up question:

Is there a simple way to solve this without having to use trial and error until you see the pattern?

What if you want to solve a nasty looking problem like:

132412343*x + 34208309*y = 1 ???


Note:

If it sounds like this sort of problem is useless and abstract think again. This stuff is integrally related to the mathmatics behind incription technology for internet security...


If anybody has any guesses how to go about this, feel free to post them now. I will post the clever trick for solving these in a few minutes...

 

[downhiller80]

Sorry miniMunch, I spotted my mistake!

Doh, but it's still wrong. Will edit that plus to be a minus....

- seb

 

[miniMUNCH]

fun algebra problem Jothaxe...what about the fun tricks?

I love math.

 

[Jothaxe]

<< fun algebra problem Jothaxe...what about the fun tricks?

I love math. >>




Fun tricks are coming very soon... hehe

 

[Adrian1]

i hhmm dont know ??