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

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

$4048x+418y=66$
$184x+19y=3$
$(19\cdot 9+13)x+19y=3$
$13x+19(9x+y)=3$ Substitute, say $z=9x+y$.
$13x+19z=3$
$13x+(13+6)z=3$
$13(x+z)+6z=3$ Now, let say $t=x+z$.
$13t+6z=3$
$(7+6)t+6z=3$
$7t+6(t+z)=3$ Say $u=t+z$.
$7t+6u=3$
From this equation you can guess the values of t and u which reduce the equation to identity.

Take $u=4$ and $t=-3$. 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 $x=-10$ and $y=97$.

Of course you could use values say $u=-3$ and $t=3$ but that would give you $x=9$ and $y=-87$ which you don't like since you have the constraint $y>0$.