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:

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

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

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