I'm looking at this example and it doesn't make sense to me.

We have to solve the following systems of linear congruences :

$x\equiv 1\pmod 5$

$x\equiv 2\pmod 6$

$x\equiv 3\pmod 7$

We take congruence no. 1 as $x=5t+1$.

We plug it into the second one :

$5t + 1\equiv 2\pmod 6$

  • Now, how do we get from that to $t\equiv 5\pmod 6$ ?

Next, we make the $t = 6u + 5$

The equation now becomes $30u + 26$

We plug this into the third congruence :

$30u + 26\equiv 3\pmod 7$

  • Now, how do we get from that to $u\equiv 6\pmod 7$ ?

$5t + 1 \equiv_6 2 \implies 5t \equiv_6 1$. The inverse of $5$ is $5$, since $5 \cdot 5 = 25 \equiv_6 1$, so multiply by the inverse on both sides to get $t \equiv_6 5$. Similarly, $30u + 26 \equiv_7 3 \implies 2u + 5 \equiv_7 3 \implies 2u \equiv_7 5$ and the inverse of $2$ is $4$, so $u \equiv_7 6$.

  • $\begingroup$ What method did you use for calculating the inverse ? Won't the Euclidean algorithm method return -1 as the inverse of 5 ? $\endgroup$ – Objective-J Apr 20 '16 at 14:12
  • $\begingroup$ As a remark: there are nonzero numbers that are not invertible mod n for every n which isn't prime, so you won't always be able to multiply by the inverse as above. for example 2t = 1 has no solutions mod 4. $\endgroup$ – rVitale Apr 20 '16 at 14:13
  • $\begingroup$ -1 is equal to 5 mod 6 so that works, but here I just did it by inspection since there aren't many congruence classes $\endgroup$ – rVitale Apr 20 '16 at 14:14
  • 1
    $\begingroup$ it's ok to apply it whenever, wherever, and as often as you want, since (a + b) mod n = (a mod n) + (b mod n), and (ab) mod n = (a mod n)(b mod n). You can always work with whatever representative you prefer as they are all equivalent, in the sense that addition and multiplication work on whole equivalence classes of numbers mod n. It is common to do a final reduction to a representative in the range 0..n-1 $\endgroup$ – rVitale Apr 20 '16 at 14:24
  • 1
    $\begingroup$ whenever you see any number in a congruence equation or when you're doing modular arithmetic in general you can think of that number as every number of the congruence class. You can write any representative at any time since they're all the same up to adding a multiple of n, and n = 0 mod n. $\endgroup$ – rVitale Apr 20 '16 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.