Results 1 to 10 of 10

Math Help - Am I applying Euclid's algorithm effectively?

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Am I applying Euclid's algorithm effectively?

    Use Euclid's algorithm to find integer solutions of the given equation, and hence find the solutions of the congruence equations that are also given

    (a) 127a + 583b = 1, 127x \equiv mod 583

    I seem to need a lot of working to solve these and was just wondering if I was performing everything correctly/efficiently (reasonably).

    My working:

    I drew out the GCD working so I could work backwards:

    583 = 4x127 + 75

    127 = 75 + 52

    75 = 52 + 23

    23 = 3x6 + 5

    6 = 5 + 1

    5 = 5x1 + 0

    \therefore GCD = 1

    Then I worked backwards to find integer values for x and y:

    1 = 6 - 5

    = 6 - (23 - 3x6)

    = 4x6 - 23

    = 4(52 - 2x23) - (75 - 52)

    = 5x52 - 8x23 - 75

    = 5(127 - 75) - 8(75 -52) - 75

    = 5x127 - 14x75 + 8x52

    = 5x127 -14(583 - 4x127) + 8(127 - 75)

    = 69x127 - 14x583 - 8(583 - 4x127)

    = 101x127 - 22x583

    \therefore a = 101 and b = -22

    Is that normal to have to do that much for everyone one of these? I'm not complaining, just wondering if I'm missing something

    For the second part, I'm not quite sure what I need to do...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Am I applying Euclid's algorithm effectively?

    that is exactly how it's done. it's tedious (especially with larger numbers) but it's mechanical...once you see how it works, it's just a matter of "turning the crank" to get the results.

    your second equation (congruence) seems to be missing a number.....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Am I applying Euclid's algorithm effectively?

    Quote Originally Posted by Deveno View Post
    your second equation (congruence) seems to be missing a number.....

    127x \equiv 1 mod 583

    I can see that if I sub in 101 for x, the statement is true, but I don't understand how I find any other solutions.

    Quote Originally Posted by Deveno View Post
    that is exactly how it's done. it's tedious (especially with larger numbers) but it's mechanical...once you see how it works, it's just a matter of "turning the crank" to get the results.
    :S yah, the next one is taking forever 3256a + 237b = 1... (237x \equiv 1 mod 3256)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Am I applying Euclid's algorithm effectively?

    however, once you have done the dirty work, you can now solve:

    127x = 1 (mod 583) easily!

    you know that: 127(101) + (-22)583 = 1, so.....

    (127)(101) = 1 (mod 583)

    any other solution must be congruent to 101 (mod 583) (the proof of this uses some group theory, which you might not have been exposed to),

    and every number congruent to 101 (mod 583) is also a solution.

    this is how division is performed in modular arithmetic, so the appearance of the euclidean algorithm (also known as the division algorithm) should be no surprise.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Am I applying Euclid's algorithm effectively?

    So the answers for a are 101 mod 583 and the answers for b are -22 mod 127... but the multiples have to move in opposite directions for a and b?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Am I applying Euclid's algorithm effectively?

    the integers a,b as solutions to am + bn = 1 aren't always unique.

    for example suppose m = 2, n = 3. we know gcd(2,3) = 1, so we know there ARE integers a,b with 2a + 3b = 1.

    for example, 2(-1) + 3 = 1, but also 2(2) + 3(-1) = 1, and 2(-4) + 3(3) = 1, and

    2(8) + 3(-5) = 1. the euclidean algoritm doesn't say you'll find "every" pair (a,b) such that am + bn = 1, it only gives a way to find one such pair.

    but if am + bn = 1, then writing [k] for the reduced (mod n) form of k, we have:

    [am + bn] = [1]
    [am] + [bn] = [1]
    [a][m] + [b][n] = [1], but [n] = [0], so:
    [a][m] + [b][0] = [1]
    [a][m] + [b0] = [1]
    [a][m] + [0] = [1]
    [a][m] = 1.

    that is, modulo n, the "residue" of a (the reduced mod n form of a) is 1/m (a multiplicative inverse....DON'T think fraction).


    let's go back to a really simple example.

    let's say we want to solve 7x = 1 mod 13.

    so we want to find a,b with 7a + 13b = 1. this is easy, we can use a = 2, b = -1.

    (7)(2) + 13(-1) = 1. let's multiply this out:

    14 - 13 = 1, now let's take everything mod 13:

    1 - 0 = 1. the key is, that 7 mod 13 times 2 mod 13 is the same as 14 mod 13, which is 1 mod 13.

    so back in our original equation:

    7x = 1 (mod 13)
    2(7x) = 2 (mod 13)
    14x = 2 (mod 13)
    x = 2 mod (13).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Am I applying Euclid's algorithm effectively?

    Just one more question... I was just applying some of the things you said in your last post and ran into a problem that I couldn't explain. I was trying to get my equation 127x \equiv 1 mod 583 into the form x \equiv y mod 583 like you did with 7x = 1 (mod 13).

    Here's what I did:

    127x \equiv 1 mod 583 (multiply by 5)

    635x \equiv 5 mod 583 (take mod 583)

    52x \equiv 5 mod 583 (multiply by 11)

    572x \equiv 55 mod 583

    Everything works up to here if I test for x = 101, i.e., \frac{572(101)}{583} = 99.0943396264. Removing the 99.00 and multiplying by 583 I get 55 as intended.

    However, when I went to finish things off by taking mod 583 again:

    -11x \equiv 55 mod 583 (then divide by -11)

    x \equiv -5 mod 583

    I can see that it's wrong but I don't know what I did that was incorrect. The second last line seems to work if I take -11(101) - 55 = -1166 = -2(583) but when I apply my other method,
    \frac{-11(101)}{583} = -1.9056603774. Keep the decimal and multiply by 583, I get -528 \neq 55. Although I can see that -528 \equiv 55 mod 583.

    Sorry, kind of an obscure question, but I wanted to understand what was going on.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Am I applying Euclid's algorithm effectively?

    this is what you did wrong: you divided by 11 (well, -11, but you would get the same thing if you multiplied by -1, and then divided by 11).

    (11,583) = 11

    that is (11)(53) = 583 = 0 (mod 583). such a number, is called a zero-divsor (mod 583).

    you see, even though 11(101) = 55 (mod 583), we can't conclude from that, that 101 = -5 (mod 583).

    let's look at a smaller modulus example:

    solving ax = b (mod 6) depends on finding some c mod 6, so that ca = 1 (mod 6).

    well, what if a = 2? let's look at all the possibilities (all calculations are mod 6):

    (0)(2) = 0, this doesn't work.
    (1)(2) = 2, no go.
    (2)(2) = 4, nyet.
    (3)(2) = 0, been there.
    (4)(2) = 2, bummer.
    (5)(2) = 4, well.....outta luck

    there is no such c, if a = 2. what to do in such a situation?

    well, if b = 1,3 or 5, there's nothing you CAN do, there aren't any solutions.

    if b = 0,2 or 6, then we take out the common factor 2:

    so to solve 2x = 2k (mod 6), we solve instead x = k (mod 3).

    in your example, that means:

    x = -5 (mod 53), which is true for x = 101.

    in other words, it makes a difference whether or not your modulus is prime. if your modulus isn't prime, dividing by a number that isn't co-prime to it WILL NOT WORK.

    for example, mod 6 it is true that 4 is a solution to:

    2x = 2 (mod 6)......but it IS NOT TRUE that 4 is a solution of:

    x = 1 (mod 6), we can't "divide by 2".
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Am I applying Euclid's algorithm effectively?

    Ah, ok. Thanks for that!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Am I applying Euclid's algorithm effectively?

    Quote Originally Posted by terrorsquid View Post
    Is that normal to have to do that much for everyone one of these? I'm not complaining, just wondering if I'm missing something
    I agree that essentially the calculation in the OP is what needs to be done, but instead of working with expressions and parentheses, it is possible to follow a simple iterative procedure.

    The sequence of remainders and quotients in the given Euclid's algorithm is (75, 4), (52, 1), (23, 1), (6, 2), (5, 3) and (1, 1). Consider the following table.

    \begin{array}{ll|rrrrrrrr}\mbox{Step number}& n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline\mbox{Remainder}& r_n & 583 & 127 & 75 & 52 & 23 & 6 & 5 & 1\\\hline\hline\mbox{Quotient}& q_n & & & 4 & 1 & 1 & 2 & 3 & 1\\\mbox{First coefficient}& s_n & 1 & 0 & 1 & -1 & 2 & -5 & 17 & -22\\\hline\hline \mbox{Second coefficient}& t_n & 0 & 1 & -4 & 5 & -9 & 23 & -78 & 101\end{array}

    The important rows are third and fourth (between the double lines) or, alternatively, third and fifth. All other rows are unnecessary. We have

    \begin{aligned}s_{n+2}&=s_n-q_{n+2}s_{n+1}\\t_{n+2}&=t_n-q_{n+2}t_{n+1}\end{aligned}

    If the original numbers are a=r_0 and b=r_1 and the coefficients corresponding to r_n=\mbox{GCD}(a,b) are s_n,t_n in the last column, then as_n+bt_n=r_n. In fact, in each column i we have as_i+bt_i=r_i.

    It is enough to calculate only s_n or only t_n because from as_n+bt_n=r_n we have t_n=(r_n-as_n)/b and similarly for s_n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Applying Euclid's Lemma to a problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2011, 07:05 PM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum