Natural number that has a remainder of $1, 2, 3, 4$ respectively after dividing⦠[duplicate]

Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
This question already has an answer here:
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.
3 answers
A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of 4. What should be the number ?
Note : I already formulated some formula but I think it might not work:
x = 2a + 1
x = 3b + 2
x = 4c + 3
x = 5d + 4
elementary-number-theory chinese-remainder-theorem
marked as duplicate by Jyrki Lahtonen, Brahadeesh, Claude Leibovici, Community⦠Aug 13 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.
add a comment |Â
up vote
0
down vote
favorite
This question already has an answer here:
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.
3 answers
A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of 4. What should be the number ?
Note : I already formulated some formula but I think it might not work:
x = 2a + 1
x = 3b + 2
x = 4c + 3
x = 5d + 4
elementary-number-theory chinese-remainder-theorem
marked as duplicate by Jyrki Lahtonen, Brahadeesh, Claude Leibovici, Community⦠Aug 13 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.
4
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
1
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
3
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
This question already has an answer here:
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.
3 answers
A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of 4. What should be the number ?
Note : I already formulated some formula but I think it might not work:
x = 2a + 1
x = 3b + 2
x = 4c + 3
x = 5d + 4
elementary-number-theory chinese-remainder-theorem
This question already has an answer here:
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.
3 answers
A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of 4. What should be the number ?
Note : I already formulated some formula but I think it might not work:
x = 2a + 1
x = 3b + 2
x = 4c + 3
x = 5d + 4
This question already has an answer here:
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.
3 answers
elementary-number-theory chinese-remainder-theorem
edited Aug 13 at 4:27
David G. Stork
8,07621232
8,07621232
asked Aug 13 at 4:11
MMJM
205
205
marked as duplicate by Jyrki Lahtonen, Brahadeesh, Claude Leibovici, Community⦠Aug 13 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 Jyrki Lahtonen, Brahadeesh, Claude Leibovici, Community⦠Aug 13 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.
4
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
1
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
3
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47
add a comment |Â
4
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
1
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
3
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47
4
4
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
1
1
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
3
3
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
0
down vote
This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.
add a comment |Â
up vote
0
down vote
Note that if $x equiv 3 pmod4$ you get 'for free' that $x equiv 1 pmod2$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at
$$
cases
x equiv 3 pmod4 \
x equiv 2 pmod3 \
x equiv 4 pmod5
$$
By the chinese remainder theorem, this system of equations has a unique solution modulo $4cdot3cdot5 = 60$. The only numbers in $1,dots,60$ that are congruent to $4$ modulo $5$ are
$$
0, 4,9,14,19,24,29,34,39,44,49,54,59.
$$
Now, our number is odd by the first observation, so we can reduce the former to check only these
$$
9,19,29,39,49,59
$$
and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form
$$
60k + 59
$$
or since $59 equiv -1 pmod60$,
$$
60k -1 quad (k in mathbbZ)
$$
add a comment |Â
up vote
0
down vote
Continuing your thought:
$$begincasesx=2a+1\x=3b+2\x=4c+3\x=5d+4endcases Rightarrow begincasesx=2a+1\2a+1=3b+2\2a+1=4c+3\2a+1=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\3b+2=4c+3\3b+2=5d+4 endcasesRightarrow \
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
4c+3=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
c=frac14(5d+1) endcases$$
Now you must solve the last Diophantine equation (or by trial and error) and find backwards:
$$d=11,c=14,b=19,d=29,x=59.$$
Alternatively, using modular arithmetic:
$$begincases
xequiv 1pmod2\
xequiv 2pmod3\
xequiv 3pmod4\
xequiv 4pmod5endcases Rightarrow
begincases
x=2a+1\
2a+1=2pmod3\
2a+1=3pmod4\
2a+1=4pmod5 endcasesRightarrow
begincases
x=2a+1\
aequiv 2pmod3\
aequiv 1pmod2\
aequiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
3b+2equiv1pmod2\
3b+2equiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
bequiv-1pmod2\
bequiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
b=2c-1\
2c-1equiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
b=2c-1\
cequiv 0pmod5 endcases Rightarrow
begincases
colorredx=2(30n-1)+1=colorred60n-1\
a=3(10n-1)+2=30n-1\
b=2(5n)-1=10n-1\
c=5n, nin mathbb Z endcases$$
add a comment |Â
up vote
0
down vote
If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.
add a comment |Â
up vote
0
down vote
This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.
This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.
answered Aug 13 at 4:24
David G. Stork
8,07621232
8,07621232
add a comment |Â
add a comment |Â
up vote
0
down vote
Note that if $x equiv 3 pmod4$ you get 'for free' that $x equiv 1 pmod2$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at
$$
cases
x equiv 3 pmod4 \
x equiv 2 pmod3 \
x equiv 4 pmod5
$$
By the chinese remainder theorem, this system of equations has a unique solution modulo $4cdot3cdot5 = 60$. The only numbers in $1,dots,60$ that are congruent to $4$ modulo $5$ are
$$
0, 4,9,14,19,24,29,34,39,44,49,54,59.
$$
Now, our number is odd by the first observation, so we can reduce the former to check only these
$$
9,19,29,39,49,59
$$
and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form
$$
60k + 59
$$
or since $59 equiv -1 pmod60$,
$$
60k -1 quad (k in mathbbZ)
$$
add a comment |Â
up vote
0
down vote
Note that if $x equiv 3 pmod4$ you get 'for free' that $x equiv 1 pmod2$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at
$$
cases
x equiv 3 pmod4 \
x equiv 2 pmod3 \
x equiv 4 pmod5
$$
By the chinese remainder theorem, this system of equations has a unique solution modulo $4cdot3cdot5 = 60$. The only numbers in $1,dots,60$ that are congruent to $4$ modulo $5$ are
$$
0, 4,9,14,19,24,29,34,39,44,49,54,59.
$$
Now, our number is odd by the first observation, so we can reduce the former to check only these
$$
9,19,29,39,49,59
$$
and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form
$$
60k + 59
$$
or since $59 equiv -1 pmod60$,
$$
60k -1 quad (k in mathbbZ)
$$
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Note that if $x equiv 3 pmod4$ you get 'for free' that $x equiv 1 pmod2$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at
$$
cases
x equiv 3 pmod4 \
x equiv 2 pmod3 \
x equiv 4 pmod5
$$
By the chinese remainder theorem, this system of equations has a unique solution modulo $4cdot3cdot5 = 60$. The only numbers in $1,dots,60$ that are congruent to $4$ modulo $5$ are
$$
0, 4,9,14,19,24,29,34,39,44,49,54,59.
$$
Now, our number is odd by the first observation, so we can reduce the former to check only these
$$
9,19,29,39,49,59
$$
and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form
$$
60k + 59
$$
or since $59 equiv -1 pmod60$,
$$
60k -1 quad (k in mathbbZ)
$$
Note that if $x equiv 3 pmod4$ you get 'for free' that $x equiv 1 pmod2$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at
$$
cases
x equiv 3 pmod4 \
x equiv 2 pmod3 \
x equiv 4 pmod5
$$
By the chinese remainder theorem, this system of equations has a unique solution modulo $4cdot3cdot5 = 60$. The only numbers in $1,dots,60$ that are congruent to $4$ modulo $5$ are
$$
0, 4,9,14,19,24,29,34,39,44,49,54,59.
$$
Now, our number is odd by the first observation, so we can reduce the former to check only these
$$
9,19,29,39,49,59
$$
and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form
$$
60k + 59
$$
or since $59 equiv -1 pmod60$,
$$
60k -1 quad (k in mathbbZ)
$$
answered Aug 13 at 4:25
Guido A.
4,046725
4,046725
add a comment |Â
add a comment |Â
up vote
0
down vote
Continuing your thought:
$$begincasesx=2a+1\x=3b+2\x=4c+3\x=5d+4endcases Rightarrow begincasesx=2a+1\2a+1=3b+2\2a+1=4c+3\2a+1=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\3b+2=4c+3\3b+2=5d+4 endcasesRightarrow \
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
4c+3=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
c=frac14(5d+1) endcases$$
Now you must solve the last Diophantine equation (or by trial and error) and find backwards:
$$d=11,c=14,b=19,d=29,x=59.$$
Alternatively, using modular arithmetic:
$$begincases
xequiv 1pmod2\
xequiv 2pmod3\
xequiv 3pmod4\
xequiv 4pmod5endcases Rightarrow
begincases
x=2a+1\
2a+1=2pmod3\
2a+1=3pmod4\
2a+1=4pmod5 endcasesRightarrow
begincases
x=2a+1\
aequiv 2pmod3\
aequiv 1pmod2\
aequiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
3b+2equiv1pmod2\
3b+2equiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
bequiv-1pmod2\
bequiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
b=2c-1\
2c-1equiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
b=2c-1\
cequiv 0pmod5 endcases Rightarrow
begincases
colorredx=2(30n-1)+1=colorred60n-1\
a=3(10n-1)+2=30n-1\
b=2(5n)-1=10n-1\
c=5n, nin mathbb Z endcases$$
add a comment |Â
up vote
0
down vote
Continuing your thought:
$$begincasesx=2a+1\x=3b+2\x=4c+3\x=5d+4endcases Rightarrow begincasesx=2a+1\2a+1=3b+2\2a+1=4c+3\2a+1=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\3b+2=4c+3\3b+2=5d+4 endcasesRightarrow \
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
4c+3=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
c=frac14(5d+1) endcases$$
Now you must solve the last Diophantine equation (or by trial and error) and find backwards:
$$d=11,c=14,b=19,d=29,x=59.$$
Alternatively, using modular arithmetic:
$$begincases
xequiv 1pmod2\
xequiv 2pmod3\
xequiv 3pmod4\
xequiv 4pmod5endcases Rightarrow
begincases
x=2a+1\
2a+1=2pmod3\
2a+1=3pmod4\
2a+1=4pmod5 endcasesRightarrow
begincases
x=2a+1\
aequiv 2pmod3\
aequiv 1pmod2\
aequiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
3b+2equiv1pmod2\
3b+2equiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
bequiv-1pmod2\
bequiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
b=2c-1\
2c-1equiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
b=2c-1\
cequiv 0pmod5 endcases Rightarrow
begincases
colorredx=2(30n-1)+1=colorred60n-1\
a=3(10n-1)+2=30n-1\
b=2(5n)-1=10n-1\
c=5n, nin mathbb Z endcases$$
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Continuing your thought:
$$begincasesx=2a+1\x=3b+2\x=4c+3\x=5d+4endcases Rightarrow begincasesx=2a+1\2a+1=3b+2\2a+1=4c+3\2a+1=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\3b+2=4c+3\3b+2=5d+4 endcasesRightarrow \
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
4c+3=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
c=frac14(5d+1) endcases$$
Now you must solve the last Diophantine equation (or by trial and error) and find backwards:
$$d=11,c=14,b=19,d=29,x=59.$$
Alternatively, using modular arithmetic:
$$begincases
xequiv 1pmod2\
xequiv 2pmod3\
xequiv 3pmod4\
xequiv 4pmod5endcases Rightarrow
begincases
x=2a+1\
2a+1=2pmod3\
2a+1=3pmod4\
2a+1=4pmod5 endcasesRightarrow
begincases
x=2a+1\
aequiv 2pmod3\
aequiv 1pmod2\
aequiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
3b+2equiv1pmod2\
3b+2equiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
bequiv-1pmod2\
bequiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
b=2c-1\
2c-1equiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
b=2c-1\
cequiv 0pmod5 endcases Rightarrow
begincases
colorredx=2(30n-1)+1=colorred60n-1\
a=3(10n-1)+2=30n-1\
b=2(5n)-1=10n-1\
c=5n, nin mathbb Z endcases$$
Continuing your thought:
$$begincasesx=2a+1\x=3b+2\x=4c+3\x=5d+4endcases Rightarrow begincasesx=2a+1\2a+1=3b+2\2a+1=4c+3\2a+1=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\3b+2=4c+3\3b+2=5d+4 endcasesRightarrow \
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
4c+3=5d+4 endcasesRightarrow
begincasesx=2a+1\a=frac12(3b+1)\b=frac13(4c+1)\
c=frac14(5d+1) endcases$$
Now you must solve the last Diophantine equation (or by trial and error) and find backwards:
$$d=11,c=14,b=19,d=29,x=59.$$
Alternatively, using modular arithmetic:
$$begincases
xequiv 1pmod2\
xequiv 2pmod3\
xequiv 3pmod4\
xequiv 4pmod5endcases Rightarrow
begincases
x=2a+1\
2a+1=2pmod3\
2a+1=3pmod4\
2a+1=4pmod5 endcasesRightarrow
begincases
x=2a+1\
aequiv 2pmod3\
aequiv 1pmod2\
aequiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
3b+2equiv1pmod2\
3b+2equiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
bequiv-1pmod2\
bequiv 4pmod5 endcasesRightarrow
begincases
x=2a+1\
a=3b+2\
b=2c-1\
2c-1equiv 4pmod5 endcasesRightarrow \
begincases
x=2a+1\
a=3b+2\
b=2c-1\
cequiv 0pmod5 endcases Rightarrow
begincases
colorredx=2(30n-1)+1=colorred60n-1\
a=3(10n-1)+2=30n-1\
b=2(5n)-1=10n-1\
c=5n, nin mathbb Z endcases$$
answered Aug 13 at 6:00
farruhota
13.9k2632
13.9k2632
add a comment |Â
add a comment |Â
up vote
0
down vote
If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.
add a comment |Â
up vote
0
down vote
If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.
If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.
answered Aug 13 at 6:38
Benedict Randall Shaw
3139
3139
add a comment |Â
add a comment |Â
4
$60n-1$ for any integer $n$ (and no others).
â metamorphy
Aug 13 at 4:19
Note: Every number which satisfies that when divided by $4$ it leaves a remainder of $3$ must also satisfy the condition that when divided by $2$ it leaves remainder $1$, so the first condition in your question can be entirely ignored. To solve your question this is a straightforward application of the Chinese remainder theorem.
â JMoravitz
Aug 13 at 4:22
1
The information about the remainder after division by $2$ is redundant. Observe that $2cdot 20=3cdot 13+1$, $3cdot 15=4cdot 11+1$, and $8cdot 12=5cdot 15+1$. Therefore, $3cdot 4cdot 5cdot n+2cdot 20cdot 2+3cdot 15cdot 3+8cdot 12cdot 4$ should leave those remainders. This construction is the interpolation technique used in the existencial part of the Chinese Remainder Theorem.
â user583185
Aug 13 at 4:22
3
The super-simple way on this one, BTW: if $x$ divided by $3$ leaves a remainder of $2$, then $(x+1)$ is a multiple of $3$. Likewise, $x+1$ is a multiple of $4$, and of $5$. What can you say about it, then?
â Steven Stadnicki
Aug 13 at 4:28
Closely related.
â Jyrki Lahtonen
Aug 13 at 4:47