How to solve such a modular equation? [duplicate]
$begingroup$
This question already has an answer here:
modular arithmetic, solving $ax + b equiv c pmod d$?
2 answers
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?
elementary-number-theory modular-arithmetic
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
$endgroup$
marked as duplicate by Dietrich Burde, amWhy, 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.
|
show 1 more comment
$begingroup$
This question already has an answer here:
modular arithmetic, solving $ax + b equiv c pmod d$?
2 answers
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?
elementary-number-theory modular-arithmetic
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
$endgroup$
marked as duplicate by Dietrich Burde, amWhy, 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 = 157cdot 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
|
show 1 more comment
$begingroup$
This question already has an answer here:
modular arithmetic, solving $ax + b equiv c pmod d$?
2 answers
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?
elementary-number-theory modular-arithmetic
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
$endgroup$
This question already has an answer here:
modular arithmetic, solving $ax + b equiv c pmod d$?
2 answers
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?
This question already has an answer here:
modular arithmetic, solving $ax + b equiv c pmod d$?
2 answers
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
asked Dec 21 '18 at 9:06
MulishiaMulishia
62
62
marked as duplicate by Dietrich Burde, amWhy, 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.
marked as duplicate by Dietrich Burde, amWhy, 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 = 157cdot 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
|
show 1 more comment
$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 = 157cdot 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
$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$
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$
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$
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$
@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 = 157cdot 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
$begingroup$
You have $42547 = 157cdot 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
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
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+42547kquad,quad kin Bbb Z$$
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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+42547kquad,quad kin Bbb Z$$
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
$endgroup$
add a comment |
$begingroup$
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+42547kquad,quad kin Bbb Z$$
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
$endgroup$
add a comment |
$begingroup$
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+42547kquad,quad kin Bbb Z$$
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
$endgroup$
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+42547kquad,quad kin Bbb Z$$
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
answered Dec 21 '18 at 10:55
Mostafa AyazMostafa Ayaz
15.3k3939
15.3k3939
add a comment |
add a comment |
$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 = 157cdot 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