Results 1 to 2 of 2

Math Help - Factorization in Z

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    Quote Originally Posted by aceOfPentacles View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factorization
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 25th 2010, 08:48 PM
  2. [Factorization] Factorization of polynomials
    Posted in the Algebra Forum
    Replies: 9
    Last Post: April 9th 2010, 12:15 AM
  3. Replies: 2
    Last Post: March 4th 2010, 01:49 AM
  4. a better factorization?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 11th 2009, 05:36 AM
  5. factorization
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 1st 2009, 06:21 PM

Search Tags


/mathhelpforum @mathhelpforum