How to find if there's exists an integer X that fullfil this equation [closed]
$begingroup$
Given A, B, C & D and the equation :
(A*X + B)%D = C
I tried to move the modulo to the other side but I end up with 2 unknown variables.
modules
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
$endgroup$
closed as unclear what you're asking by Xander Henderson, Holo, user91500, A. Pongrácz, Riccardo.Alestra Jan 15 at 9:14
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Given A, B, C & D and the equation :
(A*X + B)%D = C
I tried to move the modulo to the other side but I end up with 2 unknown variables.
modules
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
$endgroup$
closed as unclear what you're asking by Xander Henderson, Holo, user91500, A. Pongrácz, Riccardo.Alestra Jan 15 at 9:14
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56
add a comment |
$begingroup$
Given A, B, C & D and the equation :
(A*X + B)%D = C
I tried to move the modulo to the other side but I end up with 2 unknown variables.
modules
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
$endgroup$
Given A, B, C & D and the equation :
(A*X + B)%D = C
I tried to move the modulo to the other side but I end up with 2 unknown variables.
modules
modules
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
asked Jan 9 at 11:43
Andrean LayAndrean Lay
83
83
closed as unclear what you're asking by Xander Henderson, Holo, user91500, A. Pongrácz, Riccardo.Alestra Jan 15 at 9:14
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Xander Henderson, Holo, user91500, A. Pongrácz, Riccardo.Alestra Jan 15 at 9:14
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56
add a comment |
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I assume you mean $$AX+Bequiv Cmod D$$
or$$AXequiv C-B=B'mod D$$let $$E=gcd(A,B',D)$$ then the latter equation is equivalent to $${Aover E}Xequiv {B'over E}mod {{Dover E}}$$by redefining the variables, we finally obtain$$PXequiv Qmod R$$where $$gcd(P,Q,R)=1$$ note that $gcd(P,R)=1$ (a proof is easy by definition of $gcd$) therefore if $X_0$ is a particular solution, i.e. $PX_0equiv Qmod R$ then all the solutions are of the form $$X=Ru+X_0quad,quad uin Bbb Z$$
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I assume you mean $$AX+Bequiv Cmod D$$
or$$AXequiv C-B=B'mod D$$let $$E=gcd(A,B',D)$$ then the latter equation is equivalent to $${Aover E}Xequiv {B'over E}mod {{Dover E}}$$by redefining the variables, we finally obtain$$PXequiv Qmod R$$where $$gcd(P,Q,R)=1$$ note that $gcd(P,R)=1$ (a proof is easy by definition of $gcd$) therefore if $X_0$ is a particular solution, i.e. $PX_0equiv Qmod R$ then all the solutions are of the form $$X=Ru+X_0quad,quad uin Bbb Z$$
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
$endgroup$
add a comment |
$begingroup$
I assume you mean $$AX+Bequiv Cmod D$$
or$$AXequiv C-B=B'mod D$$let $$E=gcd(A,B',D)$$ then the latter equation is equivalent to $${Aover E}Xequiv {B'over E}mod {{Dover E}}$$by redefining the variables, we finally obtain$$PXequiv Qmod R$$where $$gcd(P,Q,R)=1$$ note that $gcd(P,R)=1$ (a proof is easy by definition of $gcd$) therefore if $X_0$ is a particular solution, i.e. $PX_0equiv Qmod R$ then all the solutions are of the form $$X=Ru+X_0quad,quad uin Bbb Z$$
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
$endgroup$
add a comment |
$begingroup$
I assume you mean $$AX+Bequiv Cmod D$$
or$$AXequiv C-B=B'mod D$$let $$E=gcd(A,B',D)$$ then the latter equation is equivalent to $${Aover E}Xequiv {B'over E}mod {{Dover E}}$$by redefining the variables, we finally obtain$$PXequiv Qmod R$$where $$gcd(P,Q,R)=1$$ note that $gcd(P,R)=1$ (a proof is easy by definition of $gcd$) therefore if $X_0$ is a particular solution, i.e. $PX_0equiv Qmod R$ then all the solutions are of the form $$X=Ru+X_0quad,quad uin Bbb Z$$
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
$endgroup$
I assume you mean $$AX+Bequiv Cmod D$$
or$$AXequiv C-B=B'mod D$$let $$E=gcd(A,B',D)$$ then the latter equation is equivalent to $${Aover E}Xequiv {B'over E}mod {{Dover E}}$$by redefining the variables, we finally obtain$$PXequiv Qmod R$$where $$gcd(P,Q,R)=1$$ note that $gcd(P,R)=1$ (a proof is easy by definition of $gcd$) therefore if $X_0$ is a particular solution, i.e. $PX_0equiv Qmod R$ then all the solutions are of the form $$X=Ru+X_0quad,quad uin Bbb Z$$
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
answered Jan 9 at 12:04
Mostafa AyazMostafa Ayaz
18.1k31040
18.1k31040
add a comment |
add a comment |
$begingroup$
What is the % ? Do you mean $equiv$ ? instead?
$endgroup$
– dmtri
Jan 9 at 11:46
$begingroup$
So what do you want to do, specifically? Solve for X? Maybe you can try giving values to A, B, C and D and seeing what happens.
$endgroup$
– Matti P.
Jan 9 at 11:55
$begingroup$
@dmtri No, It's (AX+B) mod D = C
$endgroup$
– Andrean Lay
Jan 9 at 11:55
$begingroup$
@MattiP. Trying to check if there's exists an integer X or not without brute force method
$endgroup$
– Andrean Lay
Jan 9 at 11:56
$begingroup$
I think you can assume A%D = A (remains unchanged) and B%D = B. In that case, you can write AX+B = C + kD for some k ...
$endgroup$
– Matti P.
Jan 9 at 11:56