I need to solve a congruence system like this:

$30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ $40f_0+20f_1+30f_2+26f_3+8f_4+38f_5+2f_6 \equiv 0 \pmod{41}$

I cannot find an algorithm to do this. I found CRT, Euclidean alg etc., but Im not sure if they can be used. How is this kind of congruences solved ? Is there any C++/Java library(like NTL), which I can use ?

  • $\begingroup$ Hello! Here on Math SE we would generally like to know where you got your problem from, so that we can understand what exactly you need. $\endgroup$ – user21820 May 13 '14 at 13:01
  • $\begingroup$ It would be better to rewrite the system in another form. Enter 3 more variables or one. Well, then the system to solve elementary. $\endgroup$ – individ May 13 '14 at 13:11
  • $\begingroup$ I have 7 congruences in the system, with 7 unknowns, but only this three have right side equal to 0(the others are unknown). So I need to solve these three congruences in terms of other four and substitute back to get a new system of congruences. For more detail of what I want to do, see link, page 4. Thanks for any kind of help. $\endgroup$ – user2778945 May 13 '14 at 13:13
  • $\begingroup$ Thankfully $41$ is a prime, so the residue classes modulo $41$ form a field. Thus you can solve this using the regular row reduction algorithm (exactly the way you were taught to solve linear systems over the reals in Linear algebra). Here I give a walk through example modulo $29$. $\endgroup$ – Jyrki Lahtonen May 13 '14 at 13:16
  • $\begingroup$ Thanx @JyrkiLahtonen. That helped. $\endgroup$ – user2778945 May 13 '14 at 18:49

Your Answer

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

Browse other questions tagged or ask your own question.