# Thread: Am I applying Euclid's algorithm effectively?

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

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

3. ## Re: Am I applying Euclid's algorithm effectively?

Originally Posted by Deveno
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.

Originally Posted by Deveno
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)

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

5. ## 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?

6. ## 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).

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

8. ## 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).

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".

9. ## Re: Am I applying Euclid's algorithm effectively?

Ah, ok. Thanks for that!

10. ## Re: Am I applying Euclid's algorithm effectively?

Originally Posted by terrorsquid
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$.