Mixing
Solving $abequiv d pmod c $ knowing $b, c text and d.$
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
Do you know if it's possible to solve the equation :
$$abequiv d pmod c $$
knowing $b, c text and d?$
It's been a while I'm looking for answer but I can't find nothing.
Could you help me?
Thanks a lot!
elementary-number-theory modular-arithmetic
edited Jul 23 at 11:28
Shaun
7,33892972
asked Jul 22 at 20:17
nicoooogna
11
add a comment |Â
up vote
-1
down vote
favorite
Do you know if it's possible to solve the equation :
$$abequiv d pmod c $$
knowing $b, c text and d?$
It's been a while I'm looking for answer but I can't find nothing.
Could you help me?
Thanks a lot!
elementary-number-theory modular-arithmetic
edited Jul 23 at 11:28
Shaun
7,33892972
asked Jul 22 at 20:17
nicoooogna
11
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01
add a comment |Â
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Do you know if it's possible to solve the equation :
$$abequiv d pmod c $$
knowing $b, c text and d?$
It's been a while I'm looking for answer but I can't find nothing.
Could you help me?
Thanks a lot!
elementary-number-theory modular-arithmetic
edited Jul 23 at 11:28
Shaun
7,33892972
asked Jul 22 at 20:17
nicoooogna
11
Do you know if it's possible to solve the equation :
$$abequiv d pmod c $$
knowing $b, c text and d?$
It's been a while I'm looking for answer but I can't find nothing.
Could you help me?
Thanks a lot!
elementary-number-theory modular-arithmetic
edited Jul 23 at 11:28
Shaun
7,33892972
asked Jul 22 at 20:17
nicoooogna
11
edited Jul 23 at 11:28
Shaun
7,33892972
edited Jul 23 at 11:28
Shaun
7,33892972
edited Jul 23 at 11:28
Shaun
7,33892972
7,33892972
asked Jul 22 at 20:17
nicoooogna
11
asked Jul 22 at 20:17
nicoooogna
11
asked Jul 22 at 20:17
nicoooogna
11
11
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01
add a comment |Â
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
0
down vote
accepted
It is possible if and only if $gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $gcd(b,c)=1$.
Indeed, let $delta=gcd(b,c)$. We have a Bézout's relation $; ub+vc=delta$ for some $u,vinbf Z$.
Now we want a relation $; ab+kc=d$ for some $kinbf Z$. Setting $;b_1=dfrac bδ$, $;c_1=dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as
$$ab+kc=(ab_1+kc_1)δ=d,$$
so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= dfrac dδ̓$, and we solve
$;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $;ab+kc=d$.
The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $;ub+vc=1$, so $u$ is the inverse of $bbmod c$, and
$$baequiv dmod ciff ubaequiv udmod ciff aequiv udmod c.$$
̓̓̓̓
answered Jul 22 at 20:46
Bernard
110k635103
add a comment |Â
up vote
0
down vote
Citing Modular multiplicative inverse:
As with the analogous operation on the real numbers, a fundamental use
of this operation is in solving, when possible, linear congruences of
the form,
$a x equiv b pmod m $ .
answered Jul 22 at 20:26
mvw
30.3k22250
add a comment |Â
up vote
0
down vote
We need $gcd (b,c)mid d$. See the following .
answered Jul 22 at 20:46
Chris Custer
5,4082622
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
It is possible if and only if $gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $gcd(b,c)=1$.
Indeed, let $delta=gcd(b,c)$. We have a Bézout's relation $; ub+vc=delta$ for some $u,vinbf Z$.
Now we want a relation $; ab+kc=d$ for some $kinbf Z$. Setting $;b_1=dfrac bδ$, $;c_1=dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as
$$ab+kc=(ab_1+kc_1)δ=d,$$
so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= dfrac dδ̓$, and we solve
$;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $;ab+kc=d$.
The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $;ub+vc=1$, so $u$ is the inverse of $bbmod c$, and
$$baequiv dmod ciff ubaequiv udmod ciff aequiv udmod c.$$
̓̓̓̓
answered Jul 22 at 20:46
Bernard
110k635103
add a comment |Â
up vote
0
down vote
accepted
It is possible if and only if $gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $gcd(b,c)=1$.
Indeed, let $delta=gcd(b,c)$. We have a Bézout's relation $; ub+vc=delta$ for some $u,vinbf Z$.
Now we want a relation $; ab+kc=d$ for some $kinbf Z$. Setting $;b_1=dfrac bδ$, $;c_1=dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as
$$ab+kc=(ab_1+kc_1)δ=d,$$
so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= dfrac dδ̓$, and we solve
$;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $;ab+kc=d$.
The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $;ub+vc=1$, so $u$ is the inverse of $bbmod c$, and
$$baequiv dmod ciff ubaequiv udmod ciff aequiv udmod c.$$
̓̓̓̓
answered Jul 22 at 20:46
Bernard
110k635103
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
It is possible if and only if $gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $gcd(b,c)=1$.
Indeed, let $delta=gcd(b,c)$. We have a Bézout's relation $; ub+vc=delta$ for some $u,vinbf Z$.
Now we want a relation $; ab+kc=d$ for some $kinbf Z$. Setting $;b_1=dfrac bδ$, $;c_1=dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as
$$ab+kc=(ab_1+kc_1)δ=d,$$
so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= dfrac dδ̓$, and we solve
$;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $;ab+kc=d$.
The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $;ub+vc=1$, so $u$ is the inverse of $bbmod c$, and
$$baequiv dmod ciff ubaequiv udmod ciff aequiv udmod c.$$
̓̓̓̓
answered Jul 22 at 20:46
Bernard
110k635103
It is possible if and only if $gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $gcd(b,c)=1$.
Indeed, let $delta=gcd(b,c)$. We have a Bézout's relation $; ub+vc=delta$ for some $u,vinbf Z$.
Now we want a relation $; ab+kc=d$ for some $kinbf Z$. Setting $;b_1=dfrac bδ$, $;c_1=dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as
$$ab+kc=(ab_1+kc_1)δ=d,$$
so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= dfrac dδ̓$, and we solve
$;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $;ab+kc=d$.
The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $;ub+vc=1$, so $u$ is the inverse of $bbmod c$, and
$$baequiv dmod ciff ubaequiv udmod ciff aequiv udmod c.$$
̓̓̓̓
answered Jul 22 at 20:46
Bernard
110k635103
answered Jul 22 at 20:46
Bernard
110k635103
answered Jul 22 at 20:46
Bernard
110k635103
answered Jul 22 at 20:46
Bernard
110k635103
110k635103
add a comment |Â
add a comment |Â
up vote
0
down vote
Citing Modular multiplicative inverse:
As with the analogous operation on the real numbers, a fundamental use
of this operation is in solving, when possible, linear congruences of
the form,
$a x equiv b pmod m $ .
answered Jul 22 at 20:26
mvw
30.3k22250
add a comment |Â
up vote
0
down vote
Citing Modular multiplicative inverse:
As with the analogous operation on the real numbers, a fundamental use
of this operation is in solving, when possible, linear congruences of
the form,
$a x equiv b pmod m $ .
answered Jul 22 at 20:26
mvw
30.3k22250
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Citing Modular multiplicative inverse:
As with the analogous operation on the real numbers, a fundamental use
of this operation is in solving, when possible, linear congruences of
the form,
$a x equiv b pmod m $ .
answered Jul 22 at 20:26
mvw
30.3k22250
Citing Modular multiplicative inverse:
As with the analogous operation on the real numbers, a fundamental use
of this operation is in solving, when possible, linear congruences of
the form,
$a x equiv b pmod m $ .
answered Jul 22 at 20:26
mvw
30.3k22250
answered Jul 22 at 20:26
mvw
30.3k22250
answered Jul 22 at 20:26
mvw
30.3k22250
answered Jul 22 at 20:26
mvw
30.3k22250
30.3k22250
add a comment |Â
add a comment |Â
up vote
0
down vote
We need $gcd (b,c)mid d$. See the following .
answered Jul 22 at 20:46
Chris Custer
5,4082622
add a comment |Â
up vote
0
down vote
We need $gcd (b,c)mid d$. See the following .
answered Jul 22 at 20:46
Chris Custer
5,4082622
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We need $gcd (b,c)mid d$. See the following .
answered Jul 22 at 20:46
Chris Custer
5,4082622
We need $gcd (b,c)mid d$. See the following .
answered Jul 22 at 20:46
Chris Custer
5,4082622
answered Jul 22 at 20:46
Chris Custer
5,4082622
answered Jul 22 at 20:46
Chris Custer
5,4082622
answered Jul 22 at 20:46
Chris Custer
5,4082622
5,4082622
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859737%2fsolving-ab-equiv-d-pmod-c-knowing-b-c-text-and-d%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Welcome to Maths SX! It is possible if $b$ is a unit mod. $c$, i.e. if $b$ and $c$ are coprime. In other cases there are conditions to check on, $c$ and $d$.
– Bernard
Jul 22 at 20:21
This has nothing whatsoever to do with differential equations.
– saulspatz
Jul 22 at 20:23
And of course the answer is only determined mod $c$.
– Robert Israel
Jul 22 at 20:23
A silly, but correct thing to do: If you know $b$, $c$, and $d$, then there are only $c$ values of $a$ to try. Plug these into a computer and see when $(ab - d) bmod c = 0$. This isn't an exact form, of course, but it works.
– rwbogl
Jul 22 at 20:35
$bxequiv d pmod ciff bx-d=yc$ linear equation of two unknowns which infinitely many solutions in general except when .......
– Piquito
Jul 22 at 21:01