Re: Simultaneous Linear Congruent Equations (solving)...

On Oct 11, 2:11�pm, gg_sci_m...@xxxxxxxxxxxxx wrote:
Hello,

Having reviewed dozens of web sites, I am still having trouble
understanding of how to apply the extended Euclidean Algorithm (I'll
call this EA) in the solving of the above types of equations.

Most of the sites are like this one...

http://encyclopedia.kids.net.au/page/ch/Chinese_remainder_theorem

...where they get the equations into the form of

� �x equiv b1 (mod n1)
� �x equiv b2 (mod n2)

...and then say something the the effect of 'using the extended
Euclidean algorithm' we get.....' etc.Then proceed to write down a sum
the operands of which don't bear any resemblance to the what can
actually be found on the link they give for the 'Euclidean algorithm'.
In this example, that link takes you here...

http://encyclopedia.kids.net.au/page/ex/Extended_Euclidean_algorithm

Sorry, but in the above example, how do I plug the x, b and n values
into the EA? What's also frustrating is that this example seems to be
on many other pages only with different formatting.

Does anyone have an idiot's guide (step by step that explains
precisely the origins of all operands used) on how to find x given I
have b1, n1, b2, n2?

Thanks,

Matthew

On Oct 11, 2:11 pm, gg_sci_m...@xxxxxxxxxxxxx wrote:
Hello,

Having reviewed dozens of web sites, I am still having trouble
understanding of how to apply the extended Euclidean Algorithm (I'll
call this EA) in the solving of the above types of equations.

Most of the sites are like this one...

http://encyclopedia.kids.net.au/page/ch/Chinese_remainder_theorem

...where they get the equations into the form of

x equiv b1 (mod n1)
x equiv b2 (mod n2)

...and then say something the the effect of 'using the extended
Euclidean algorithm' we get.....' etc.Then proceed to write down a sum
the operands of which don't bear any resemblance to the what can
actually be found on the link they give for the 'Euclidean algorithm'.
In this example, that link takes you here...

http://encyclopedia.kids.net.au/page/ex/Extended_Euclidean_algorithm

Sorry, but in the above example, how do I plug the x, b and n values
into the EA? What's also frustrating is that this example seems to be
on many other pages only with different formatting.

Does anyone have an idiot's guide (step by step that explains
precisely the origins of all operands used) on how to find x given I
have b1, n1, b2, n2?


Your lucky day, an idiot just happened to walk by.

Those links were a bit hard to understand, but I can
see what they're doing. So this will be more of a how-to
guide than a why-does-it-work-that-way guide.

I set this up to exactly match the example in the link
(the reason they all look alike is that they all steal
from the same source). But once you understand the motions,
doing it with two congruences will be a doddle.

Take the 3 congruences: 2 (mod 3), 3 (mod 4) and 2 (mod 5)
and show them as simply a list of 2 numbers (for the
computer's benefit) [remainder,modulus].

x1 = [2,3]
x2 = [3,4]
x3 = [2,5]

From these, we make 3 more lists using the three moduli.
We take each modulus and the product of the remaing two
and make a list:

ea1 = [x1[1],x2[1]*x3[1]]
ea2 = [x2[1],x1[1]*x3[1]]
ea3 = [x3[1],x1[1]*x2[1]]

or

[3, 20]
[4, 15]
[5, 12]

Note how we got that [2,3] [3,4] [2,5]
| | |
| 4 * 5
| |
ea1 = [3 , 20]

The second is [3,4] [2,3] [2,5]
| | |
| 3 * 5
| |
ea2 = [4 , 15]


Last is [2,5] [2,3] [3,4]
| | |
| 3 * 4
| |
ea3 = [5 , 12]

The ea1 numbers are what we give to the Extended
Euclidean Algorithm. I'm not going to explain
how to do that because the math library I use has
that function built in. I just give it two numbers
and it spits back three. So when I ask for
gcdext(3,20) it returns (1, 7, -1).

What are these numbers?

As help(gmpy.gcdext) says:
(g,s,t) such that g==gcd(a,b) and g == a*s + b*t

So, the first number (1) represents the gcd of
3 & 20, which looks right. and the second two
numbers (7,-1) when multiplied by 3 & 20 will sum
to the gcd. The (1,7,-1) means that

1 = 3*7 + 20*-1

which should be obviously true. You'll see the same
for the other ea's [1, 4, -1] & [1, 5, -2]

[4,15]: 1 = 4*4 + 15*-1
[5,12]: 1 = 5*5 + 12*-2

REVIEW
------

So far we've got the congruences
x1 = [2,3]
x2 = [3,4]
x3 = [2,5]
the [modulus, moduli prouct]
ea1 = [3, 20]
ea2 = [4, 15]
ea3 = [5, 12]
and the results of the EEA
gcdext1 = [1, 7, -1]
gcdext2 = [1, 4, -1]
gcdext3 = [1, 5, -2]

From the EEA, we only need the third number.
Here's how we use it: we multiply it by the
corresponding moduli product.

ea1 = [3,20]
|
|--multiply these, call it s1
|
gcdext1 = [1, 7, -1]

Likewise for the other two, giving us
s1 = -20
s2 = -15
s3 = -24

Now, a similar step only using these numbers and
the original remainders

s1 = -20
|
|--multiply these
|
x1 = [2,3]

For each set of course, giving us
mptr1 = -40
mptr2 = -45
mptr3 = -48

Now, I just need to add these three numbers
-40 + -45 + -48 = -133

And, using the product of the original moduli,
3 * 4 * 5 = 60

The answer is <drum roll>...

-133 mod 60

which is

47

Nifty, eh?

But what, exactly does this mean and how do we
know it's right? After all, without the theory,
it looks like a lot of hocus-pocus.

First, it means x1, x2 and x3 are all the same number.

But remember, there is an infinite list of numbers
that are 2 (mod 3). In fact, you can generate the
ith one using i*modulus + remainder or i*3+2:
2 5 8 11 14 ...

That's just for x1. We can do the same for x2: i*4+3
3 7 11 15 ...

Note that 11 appears in both lists. Alas, there's no 11
in the x3 list: i*5+2
2 7 12 17 ...

What the 47 means is that if we extend the 3 lists far
enough, 47 will be the first number that appears in
all three lists (for different i), which we can easily
verify.

i i*3+2 i*4+3 i*5+2
-- ----- ----- -----
1: 5 7 7
2: 8 11 12
3: 11 15 17
4: 14 19 22
5: 17 23 27
6: 20 27 32
7: 23 31 37
8: 26 35 42
9: 29 39 47 True 47 in the i*5+2 list
10: 32 43 52
11: 35 47 57 True 47 in the i*4+3 list
12: 38 51 62
13: 41 55 67
14: 44 59 72
15: 47 63 77 True 47 in the i*3+2 list

Putting it all together and trying 4 (mod 5) instead of
2 (mod 5):

[remainder, modulus]
[2, 3]
[3, 4]
[4, 5]

[one modulus, product of other two moduli]
[3, 20]
[4, 15]
[5, 12]

extended Euclidean Algorithm result: (g,s,t)
such that g==gcd(a,b) and g == a*s + b*t
[1, 7, -1]
[1, 4, -1]
[1, 5, -2]

moduli product * t
-20
-15
-24

remainder * (moduli product * t)
-40
-45
-96
-40 + -45 + -96 = -181

all moduli product
3 * 4 * 5 = 60

the answer
-181 mod 60 = 59

------------------------------------------------------------
check
1: 5 7 9
2: 8 11 14
3: 11 15 19
4: 14 19 24
5: 17 23 29
6: 20 27 34
7: 23 31 39
8: 26 35 44
9: 29 39 49
10: 32 43 54
11: 35 47 59 True
12: 38 51 64
13: 41 55 69
14: 44 59 74 True
15: 47 63 79
16: 50 67 84
17: 53 71 89
18: 56 75 94
19: 59 79 99 True

HTH
.

Relevant Pages