Thread: Factorization in Z

Does 4048x + 418y = 66 have integer solutions? If an integer solution exists, find the solution for which y is positive and small as possible.

- I can never seem to get these sorts of problems right...

Here's my working:

GCD(4048, 418) = 22 and 22 | 66.

So 4048*3 + 418*-29 = 22

which implies 4048*9 + 418*-87 = 66
so x = 9, y = -87

So solutions are:
x = 9 + 418t
y = -87 - 4048t

Now, y must be > 0 :
-87 - 4048t > 0
-4048t > 87
t < -87/4048
t < -0.02(2dp)

So t must be < -1 since we are dealing with real numbers.

When I try to go any further I get crazy results. (Am I doing it right so far?)

Any help would be greatly appreciated thanks.

Originally Posted by aceOfPentacles

Does 4048x + 418y = 66 have integer solutions? If an integer solution exists, find the solution for which y is positive and small as possible.

- I can never seem to get these sorts of problems right...

Here's my working:

GCD(4048, 418) = 22 and 22 | 66.

So 4048*3 + 418*-29 = 22

which implies 4048*9 + 418*-87 = 66
so x = 9, y = -87

So solutions are:
x = 9 + 418t
y = -87 - 4048t

Now, y must be > 0 :
-87 - 4048t > 0
-4048t > 87
t < -87/4048
t < -0.02(2dp)

So t must be < -1 since we are dealing with real numbers.

When I try to go any further I get crazy results. (Am I doing it right so far?)

Any help would be greatly appreciated thanks.

Try this:




Substitute, say .


Now, let say .


Say .

From this equation you can guess the values of t and u which reduce the equation to identity.

Take and . That will do. From here you can work your way back towards x and y, just use the substitutions you previously introduced. You will get and .

Of course you could use values say and but that would give you and which you don't like since you have the constraint .