Solving for a variable in a modular arithmetic equation [duplicate]
This question already has an answer here:
How to solve $ 13x equiv 1 ~ (text{mod} ~ 17) $?
6 answers
$fbox{$13x + 1 equiv 0 pmod {100}$}$
I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions:
$fbox{$1.$} $ What if there was no solution for $x$? How would I be able to prove it?
$fbox{$2.$} $ Are there a set of steps that I could program a computer to follow and get an answer if other similar modular equations are inputted?
My solution is below:
$13x +1 equiv 0 pmod {100}$
$13x equiv 99 pmod {100}$ (added $99$ to both of equation and applied the $mod 100$ to the left side)
$104x equiv 792 pmod {100}$ (multiplied both sides by $8$)
$4x equiv 792 pmod {100}$ (removed a $100$ from the left side)
$x equiv 198 pmod {100}$ (divided both side by $4$)
Like I said, I believe I got the right solution but only through trial and error. I was wondering if there is a more systematic way of solving these problems.
Thank you for any help.
modular-arithmetic
edited Dec 15 '18 at 9:44
thesagniksaha
160115
asked Dec 15 '18 at 9:09
Dan
191
marked as duplicate by Dietrich Burde, José Carlos Santos, ancientmathematician, amWhy, kjetil b halvorsen Dec 15 '18 at 17:48
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.
add a comment |
This question already has an answer here:
How to solve $ 13x equiv 1 ~ (text{mod} ~ 17) $?
6 answers
$fbox{$13x + 1 equiv 0 pmod {100}$}$
I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions:
$fbox{$1.$} $ What if there was no solution for $x$? How would I be able to prove it?
$fbox{$2.$} $ Are there a set of steps that I could program a computer to follow and get an answer if other similar modular equations are inputted?
My solution is below:
$13x +1 equiv 0 pmod {100}$
$13x equiv 99 pmod {100}$ (added $99$ to both of equation and applied the $mod 100$ to the left side)
$104x equiv 792 pmod {100}$ (multiplied both sides by $8$)
$4x equiv 792 pmod {100}$ (removed a $100$ from the left side)
$x equiv 198 pmod {100}$ (divided both side by $4$)
Like I said, I believe I got the right solution but only through trial and error. I was wondering if there is a more systematic way of solving these problems.
Thank you for any help.
modular-arithmetic
edited Dec 15 '18 at 9:44
thesagniksaha
160115
asked Dec 15 '18 at 9:09
Dan
191
marked as duplicate by Dietrich Burde, José Carlos Santos, ancientmathematician, amWhy, kjetil b halvorsen Dec 15 '18 at 17:48
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.
1
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49
add a comment |
This question already has an answer here:
How to solve $ 13x equiv 1 ~ (text{mod} ~ 17) $?
6 answers
$fbox{$13x + 1 equiv 0 pmod {100}$}$
I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions:
$fbox{$1.$} $ What if there was no solution for $x$? How would I be able to prove it?
$fbox{$2.$} $ Are there a set of steps that I could program a computer to follow and get an answer if other similar modular equations are inputted?
My solution is below:
$13x +1 equiv 0 pmod {100}$
$13x equiv 99 pmod {100}$ (added $99$ to both of equation and applied the $mod 100$ to the left side)
$104x equiv 792 pmod {100}$ (multiplied both sides by $8$)
$4x equiv 792 pmod {100}$ (removed a $100$ from the left side)
$x equiv 198 pmod {100}$ (divided both side by $4$)
Like I said, I believe I got the right solution but only through trial and error. I was wondering if there is a more systematic way of solving these problems.
Thank you for any help.
modular-arithmetic
edited Dec 15 '18 at 9:44
thesagniksaha
160115
asked Dec 15 '18 at 9:09
Dan
191
This question already has an answer here:
How to solve $ 13x equiv 1 ~ (text{mod} ~ 17) $?
6 answers
$fbox{$13x + 1 equiv 0 pmod {100}$}$
I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions:
$fbox{$1.$} $ What if there was no solution for $x$? How would I be able to prove it?
$fbox{$2.$} $ Are there a set of steps that I could program a computer to follow and get an answer if other similar modular equations are inputted?
My solution is below:
$13x +1 equiv 0 pmod {100}$
$13x equiv 99 pmod {100}$ (added $99$ to both of equation and applied the $mod 100$ to the left side)
$104x equiv 792 pmod {100}$ (multiplied both sides by $8$)
$4x equiv 792 pmod {100}$ (removed a $100$ from the left side)
$x equiv 198 pmod {100}$ (divided both side by $4$)
Like I said, I believe I got the right solution but only through trial and error. I was wondering if there is a more systematic way of solving these problems.
Thank you for any help.
This question already has an answer here:
How to solve $ 13x equiv 1 ~ (text{mod} ~ 17) $?
6 answers
modular-arithmetic
modular-arithmetic
edited Dec 15 '18 at 9:44
thesagniksaha
160115
asked Dec 15 '18 at 9:09
Dan
191
edited Dec 15 '18 at 9:44
thesagniksaha
160115
asked Dec 15 '18 at 9:09
Dan
191
edited Dec 15 '18 at 9:44
thesagniksaha
160115
edited Dec 15 '18 at 9:44
thesagniksaha
160115
edited Dec 15 '18 at 9:44
thesagniksaha
160115
160115
asked Dec 15 '18 at 9:09
Dan
191
asked Dec 15 '18 at 9:09
Dan
191
asked Dec 15 '18 at 9:09
Dan
191
191
marked as duplicate by Dietrich Burde, José Carlos Santos, ancientmathematician, amWhy, kjetil b halvorsen Dec 15 '18 at 17:48
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, José Carlos Santos, ancientmathematician, amWhy, kjetil b halvorsen Dec 15 '18 at 17:48
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.
1
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49
add a comment |
1
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49
1
1
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49
add a comment |
2 Answers
2
active
oldest
votes
Writing $$xequiv -frac{1}{13}mod 100$$ adding the module to the numerator we get
$$xequiv frac {99}{13}equiv frac{199}{13}equiv frac{299}{13}equiv 23mod 100$$
so $$xequiv 23mod 100$$
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
add a comment |
This is equivalent to the congruence equation
$$13xequiv -1mod 100,$$
so you only have to find an inverse of $13bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm:
begin{array}{rrrl}
r_i & u_i & v_i & q_i \hline
100 & 0 & 1 \ 13 & 1 & 0 & 7 \hline
9 & -7 & 1 & 1 \
4 & 8 & -1 & 2 \
1 & color{red}{-23} & 3 \
hline
end{array}
Thus the inverse of $13$ is $-23$, and
$$13xequiv -1mod 100iff xequiv(-23)(-1)= 23mod 100.$$
answered Dec 15 '18 at 9:55
Bernard
118k639112
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Writing $$xequiv -frac{1}{13}mod 100$$ adding the module to the numerator we get
$$xequiv frac {99}{13}equiv frac{199}{13}equiv frac{299}{13}equiv 23mod 100$$
so $$xequiv 23mod 100$$
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
add a comment |
Writing $$xequiv -frac{1}{13}mod 100$$ adding the module to the numerator we get
$$xequiv frac {99}{13}equiv frac{199}{13}equiv frac{299}{13}equiv 23mod 100$$
so $$xequiv 23mod 100$$
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
add a comment |
Writing $$xequiv -frac{1}{13}mod 100$$ adding the module to the numerator we get
$$xequiv frac {99}{13}equiv frac{199}{13}equiv frac{299}{13}equiv 23mod 100$$
so $$xequiv 23mod 100$$
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
Writing $$xequiv -frac{1}{13}mod 100$$ adding the module to the numerator we get
$$xequiv frac {99}{13}equiv frac{199}{13}equiv frac{299}{13}equiv 23mod 100$$
so $$xequiv 23mod 100$$
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
answered Dec 15 '18 at 9:17
Dr. Sonnhard Graubner
73.4k42865
73.4k42865
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
add a comment |
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
Thank you. I understand that it better now.
– Dan
Dec 15 '18 at 22:19
add a comment |
This is equivalent to the congruence equation
$$13xequiv -1mod 100,$$
so you only have to find an inverse of $13bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm:
begin{array}{rrrl}
r_i & u_i & v_i & q_i \hline
100 & 0 & 1 \ 13 & 1 & 0 & 7 \hline
9 & -7 & 1 & 1 \
4 & 8 & -1 & 2 \
1 & color{red}{-23} & 3 \
hline
end{array}
Thus the inverse of $13$ is $-23$, and
$$13xequiv -1mod 100iff xequiv(-23)(-1)= 23mod 100.$$
answered Dec 15 '18 at 9:55
Bernard
118k639112
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
add a comment |
This is equivalent to the congruence equation
$$13xequiv -1mod 100,$$
so you only have to find an inverse of $13bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm:
begin{array}{rrrl}
r_i & u_i & v_i & q_i \hline
100 & 0 & 1 \ 13 & 1 & 0 & 7 \hline
9 & -7 & 1 & 1 \
4 & 8 & -1 & 2 \
1 & color{red}{-23} & 3 \
hline
end{array}
Thus the inverse of $13$ is $-23$, and
$$13xequiv -1mod 100iff xequiv(-23)(-1)= 23mod 100.$$
answered Dec 15 '18 at 9:55
Bernard
118k639112
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
add a comment |
This is equivalent to the congruence equation
$$13xequiv -1mod 100,$$
so you only have to find an inverse of $13bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm:
begin{array}{rrrl}
r_i & u_i & v_i & q_i \hline
100 & 0 & 1 \ 13 & 1 & 0 & 7 \hline
9 & -7 & 1 & 1 \
4 & 8 & -1 & 2 \
1 & color{red}{-23} & 3 \
hline
end{array}
Thus the inverse of $13$ is $-23$, and
$$13xequiv -1mod 100iff xequiv(-23)(-1)= 23mod 100.$$
answered Dec 15 '18 at 9:55
Bernard
118k639112
This is equivalent to the congruence equation
$$13xequiv -1mod 100,$$
so you only have to find an inverse of $13bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm:
begin{array}{rrrl}
r_i & u_i & v_i & q_i \hline
100 & 0 & 1 \ 13 & 1 & 0 & 7 \hline
9 & -7 & 1 & 1 \
4 & 8 & -1 & 2 \
1 & color{red}{-23} & 3 \
hline
end{array}
Thus the inverse of $13$ is $-23$, and
$$13xequiv -1mod 100iff xequiv(-23)(-1)= 23mod 100.$$
answered Dec 15 '18 at 9:55
Bernard
118k639112
answered Dec 15 '18 at 9:55
Bernard
118k639112
answered Dec 15 '18 at 9:55
Bernard
118k639112
answered Dec 15 '18 at 9:55
Bernard
118k639112
118k639112
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
add a comment |
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
Thank you. This helps a lot.
– Dan
Dec 15 '18 at 22:19
add a comment |
1
1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution.
– Dietrich Burde
Dec 15 '18 at 9:15
For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 equiv 0 pmod{100}$ $implies 13x equiv -1 pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x equiv 1 pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done.
– thesagniksaha
Dec 15 '18 at 9:22
math.stackexchange.com/questions/3040108/…
– lab bhattacharjee
Dec 15 '18 at 9:27
The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 equiv 24$ mod $100$ but $31 notequiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions).
– user21820
Dec 15 '18 at 17:49