Number Theory Question

I doubt this is the right group to ask, but I cant find one on number theory
so here goes.

I am solving systems of linear congruences using Garners Algorithm, and as
the algorithm stands it will solve systems of the type :-

u 'congruent to' 49 (mod 99)
u 'congruent to' -21 (mod 97)
u 'congruent to' -30 (mod 95)

yielding a solution in this case of u = -272300

But, I am interested in solving systems of the type :-

a1 * u 'congruent to' b1 (mod m1)
a2 * u 'congruent to' b2 (mod m2)
a3 * u 'congruent to' b3 (mod m3)

Now, I thought it would be possible to simply multiply each side of the
congruences in the above system by their respective multiplicative inverses
of a1, a2 etc. to yield an equivalent system where there are no
co-efficients for the u's, so the above would become :-

u 'congruent to' b1' (mod m1)
u 'congruent to' b2' (mod m2)
u 'congruent to' b3' (mod m3)

where b1' = a1^-1 * b1 (mod m1), and so on for b2, b3

Now looking at this example :-

3u 'congruent to' 49 (mod 3)
9u 'congruent to' -21 (mod 7)
7u 'congruent to' -30 (mod 5)

then I am pretty sure that no solutions exist for this... (does anyone agree
with that? )

But, converting this to its equivalent system, that being, :-

u 'congruent to' 49 (mod 3)
u 'congruent to' -84 (mod 7)
u 'congruent to' -90 (mod 5)

and using Garners' Algorithm, then this does have a solution of u = -35

This value satisfies the 'equivalent system' but not the original

Why the inconsistency? Where is the flaw in my thinking that one can use an
'equivalent system' like this?

Thanks
Jeremy Watts


.