Talk:Method of successive substitution

From Wikipedia, the free encyclopedia

The math is wrong. You didn't subtract 3 from both side like you said you should.

Notice 11 is a solution.

Contents 1 Incorrect solution 2 multiplicative inverse 3 "multiplactive"? 4 "relative prime moduli" 5 Falling back to CRT?

[edit] Incorrect solution

The solution presented here is incorrect.

The multiplicative inverse of 4 (mod 12) is not 1. In fact, there is no such inverse.

Two simultaneous congruences x = r (mod a) and n = s (mod b) are only solvable when a = b (mod gcd(a,b)). The solution is unique modulo lcm(a,b). (gcd = greatest common divisor. lcm = lowest common multiple.)

The answer to the example given is x = 11 (mod 12).

[edit] multiplicative inverse

The solution for

4j ≡ 8 (mod 12)

is j ≡ 2 mod 3 (dividing all sides by the GCD(4,8,12)=4 and using the euclidean multiplicative inverse afterwards)

I have corrected the solution on the main page after receiving no comments for a couple of months

I have changed the equations at the start to get a less trivial result. The previous comments don't describe the actual example anymore.

[edit] "multiplactive"?

I have changed "multiplactive" to "multiplicative", since it seems to be an unusual spelling, rather than a technical term. -- 80.168.228.51 09:14, 26 Oct 2004 (UTC)

[edit] "relative prime moduli"

In my last example the moduli are relatively prime, and could be solved easier using the Chinese Remainder Theorem. So I am changing the example again.

[edit] Falling back to CRT?

If the moduli are coprime, the Chinese remainder theorem can be used directly.

Can't we simply adjust one of the simultaneous congruences to make the moduli coprime?

For example: The two simultaneous congruences of the form

  x ≡ r1 (mod m1)
  x ≡ r2 (mod m2)

can be solved directly by first calculating gcd(m1,m2) and replacing e.g.

  x ≡ r1 (mod m1)

with

  x ≡ r3 (mod m3)

where m3 = m1/gcd(m1,m2) and r3 = r1 mod m3.

Now, the remaining moduli (m2 and m3) are coprime.