This question already has an answer here:

I have an equation as follows: $27217 = 5s $ mod $42547$

Using this website https://www.dcode.fr/modular-equation-solver, the correct result for s is 39481 as shown below however it does not list what steps are being done.

Solving modular equation using dCode

How would one go about to find the value of s in this modular equation?


marked as duplicate by Dietrich Burde, Namaste, Jaap Scherphuis, metamorphy, TMM Dec 21 '18 at 11:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You need the multiplicative inverse of $5$ modulo $42547$, which can be found out with the extended-Euclid-Algorithm. $\endgroup$ – Peter Dec 21 '18 at 9:10
  • $\begingroup$ Unfortunately that link didn't help much because the structure of that equation is different than mine and the unknown value is on the left hand side whereas mine is on the right. @Peter I also thought of using EEA but the multiplicative inverse of 5 modulo 42547 is 17019 which does not match the result found from the website in my post. $\endgroup$ – Mulishia Dec 21 '18 at 9:46
  • $\begingroup$ It does not matter on which side the variable is. If $27217=5s \mod 42547$ then $5s=27217 \mod 42547$. The mod is not a function - it denotes that the whole equation to its left is to be evaluated modulo that number. $\endgroup$ – Jaap Scherphuis Dec 21 '18 at 10:58
  • $\begingroup$ @Mulishia The multiplicative inverse must be multiplied with the number on the left side mod 42547 $\endgroup$ – Peter Dec 21 '18 at 12:16
  • $\begingroup$ You have $42547 = 157\cdot 271.$ You can reduce mod each of these factors and solve. Then use Chinese Remainder Theorem. $\endgroup$ – B. Goddard Dec 21 '18 at 14:12

We must have that $$5s-27217=42547t$$for some integer $t$. Therefore $$5(s-5443-8509t)=2t+2$$thereby dividing $27217$ and $42547$ over $5$. By defining $q=5-5443-8509t$ we obtain the following easy-to-solve equation$$5q=2t+2$$which has an answer $q=2$ and $t=4$ yielding to $$s=39481$$therefore all the answers can be found as follows $$s=39481+42547k\quad,\quad k\in \Bbb Z$$


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