Existence of solution to linear congruence [closed]
$begingroup$
Given that $a$ and $b$ are relatively prime positive integers, and that $a$ is relatively prime to all the following primes: $p_1,p_2,...,p_n$ then the following congruence:$${a+bx}equiv 1pmod{ p_1cdot p_2cdot p_3 cdot...cdot p_n}$$
Has solution in x, why can we claim this?
modular-arithmetic inverse
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
$endgroup$
closed as off-topic by Carl Mummert, amWhy, Gibbs, Dave, Shailesh Dec 7 '18 at 2:29
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, amWhy, Gibbs, Dave, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Given that $a$ and $b$ are relatively prime positive integers, and that $a$ is relatively prime to all the following primes: $p_1,p_2,...,p_n$ then the following congruence:$${a+bx}equiv 1pmod{ p_1cdot p_2cdot p_3 cdot...cdot p_n}$$
Has solution in x, why can we claim this?
modular-arithmetic inverse
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
$endgroup$
closed as off-topic by Carl Mummert, amWhy, Gibbs, Dave, Shailesh Dec 7 '18 at 2:29
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, amWhy, Gibbs, Dave, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48
add a comment |
$begingroup$
Given that $a$ and $b$ are relatively prime positive integers, and that $a$ is relatively prime to all the following primes: $p_1,p_2,...,p_n$ then the following congruence:$${a+bx}equiv 1pmod{ p_1cdot p_2cdot p_3 cdot...cdot p_n}$$
Has solution in x, why can we claim this?
modular-arithmetic inverse
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
$endgroup$
Given that $a$ and $b$ are relatively prime positive integers, and that $a$ is relatively prime to all the following primes: $p_1,p_2,...,p_n$ then the following congruence:$${a+bx}equiv 1pmod{ p_1cdot p_2cdot p_3 cdot...cdot p_n}$$
Has solution in x, why can we claim this?
modular-arithmetic inverse
modular-arithmetic inverse
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
edited Dec 2 '18 at 20:47
Spasoje Durovic
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
asked Dec 2 '18 at 12:03
Spasoje DurovicSpasoje Durovic
30610
30610
closed as off-topic by Carl Mummert, amWhy, Gibbs, Dave, Shailesh Dec 7 '18 at 2:29
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, amWhy, Gibbs, Dave, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Carl Mummert, amWhy, Gibbs, Dave, Shailesh Dec 7 '18 at 2:29
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, amWhy, Gibbs, Dave, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48
add a comment |
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is solvable $iff gcd(n,b)mid 1!-!a,,$ where $n = prod p_i.,$ Indeed
$qquadqquad begin{align}
!bmod n!: exists x!: bxequiv&, 1!-!a\[.3em]
iff exists x,y!: ny+bx =&, 1!-!a\[.3em]
iff gcd(n,,b), mid & 1!-!a {rm by Bezout}end{align}$
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is solvable $iff gcd(n,b)mid 1!-!a,,$ where $n = prod p_i.,$ Indeed
$qquadqquad begin{align}
!bmod n!: exists x!: bxequiv&, 1!-!a\[.3em]
iff exists x,y!: ny+bx =&, 1!-!a\[.3em]
iff gcd(n,,b), mid & 1!-!a {rm by Bezout}end{align}$
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
add a comment |
$begingroup$
It is solvable $iff gcd(n,b)mid 1!-!a,,$ where $n = prod p_i.,$ Indeed
$qquadqquad begin{align}
!bmod n!: exists x!: bxequiv&, 1!-!a\[.3em]
iff exists x,y!: ny+bx =&, 1!-!a\[.3em]
iff gcd(n,,b), mid & 1!-!a {rm by Bezout}end{align}$
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
add a comment |
$begingroup$
It is solvable $iff gcd(n,b)mid 1!-!a,,$ where $n = prod p_i.,$ Indeed
$qquadqquad begin{align}
!bmod n!: exists x!: bxequiv&, 1!-!a\[.3em]
iff exists x,y!: ny+bx =&, 1!-!a\[.3em]
iff gcd(n,,b), mid & 1!-!a {rm by Bezout}end{align}$
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
It is solvable $iff gcd(n,b)mid 1!-!a,,$ where $n = prod p_i.,$ Indeed
$qquadqquad begin{align}
!bmod n!: exists x!: bxequiv&, 1!-!a\[.3em]
iff exists x,y!: ny+bx =&, 1!-!a\[.3em]
iff gcd(n,,b), mid & 1!-!a {rm by Bezout}end{align}$
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
answered Dec 2 '18 at 22:14
Bill DubuqueBill Dubuque
209k29190633
209k29190633
add a comment |
add a comment |
$begingroup$
Something may be wrong. Is it $b$ that is coprime to all $p_i$? Is the modulus their product?
$endgroup$
– Bill Dubuque
Dec 2 '18 at 17:38
$begingroup$
@BillDubuque Oh, you're right, messed up the LaTeX, the modulus it's their product, I'll fix it immediately!
$endgroup$
– Spasoje Durovic
Dec 2 '18 at 20:46
$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Dec 6 '18 at 17:48