Mixing
Finding largest number with GCD.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
The question is:
Find the largest number which when divided by 20,25,35 and 40 leaves a remainder of 14,19,29 and 34 respectively.
The solution is to find the difference which in this case is 20-14=6,25-19=6 and similarly for others.
Then finding GCD of all the numbers 20,25,35 and 40 and subtracting 6 from the obtained GCD.
I really did not understand why this solution works, if anyone could explain me the logic behind this in plain english. I am sorry I am weak in mathematics.
greatest-common-divisor
asked 2 days ago
Bravo Jades
61
add a comment |Â
up vote
1
down vote
favorite
The question is:
Find the largest number which when divided by 20,25,35 and 40 leaves a remainder of 14,19,29 and 34 respectively.
The solution is to find the difference which in this case is 20-14=6,25-19=6 and similarly for others.
Then finding GCD of all the numbers 20,25,35 and 40 and subtracting 6 from the obtained GCD.
I really did not understand why this solution works, if anyone could explain me the logic behind this in plain english. I am sorry I am weak in mathematics.
greatest-common-divisor
asked 2 days ago
Bravo Jades
61
You want the LCM, not the GCD here
– Ross Millikan
2 days ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The question is:
Find the largest number which when divided by 20,25,35 and 40 leaves a remainder of 14,19,29 and 34 respectively.
The solution is to find the difference which in this case is 20-14=6,25-19=6 and similarly for others.
Then finding GCD of all the numbers 20,25,35 and 40 and subtracting 6 from the obtained GCD.
I really did not understand why this solution works, if anyone could explain me the logic behind this in plain english. I am sorry I am weak in mathematics.
greatest-common-divisor
asked 2 days ago
Bravo Jades
61
The question is:
Find the largest number which when divided by 20,25,35 and 40 leaves a remainder of 14,19,29 and 34 respectively.
The solution is to find the difference which in this case is 20-14=6,25-19=6 and similarly for others.
Then finding GCD of all the numbers 20,25,35 and 40 and subtracting 6 from the obtained GCD.
I really did not understand why this solution works, if anyone could explain me the logic behind this in plain english. I am sorry I am weak in mathematics.
greatest-common-divisor
asked 2 days ago
Bravo Jades
61
asked 2 days ago
Bravo Jades
61
asked 2 days ago
Bravo Jades
61
asked 2 days ago
Bravo Jades
61
61
You want the LCM, not the GCD here
– Ross Millikan
2 days ago
add a comment |Â
You want the LCM, not the GCD here
– Ross Millikan
2 days ago
You want the LCM, not the GCD here
– Ross Millikan
2 days ago
You want the LCM, not the GCD here
– Ross Millikan
2 days ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$
answered 2 days ago
lab bhattacharjee
214k14152263
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
add a comment |Â
up vote
1
down vote
First take the LCM of $20,25,35,40$ which is $1400$
Now, Since the $$20-6=14\25-6=19\35-6=29\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$
Edit:
Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.
Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.
We took $-6$ form because it is common among all the given $4$ divisors.
answered 2 days ago
Key Flex
3,633422
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
add a comment |Â
up vote
0
down vote
The question is flawed. There is no largest number like that, as you can add $operatornameLCM(20,25,35,40)=1400$ to any solution and get a larger one.
The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $operatornameLCM(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.
This is all based on the Chinese Remainder Theorem.
answered 2 days ago
Ross Millikan
275k21184350
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$
answered 2 days ago
lab bhattacharjee
214k14152263
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
add a comment |Â
up vote
1
down vote
If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$
answered 2 days ago
lab bhattacharjee
214k14152263
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$
answered 2 days ago
lab bhattacharjee
214k14152263
If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$
answered 2 days ago
lab bhattacharjee
214k14152263
answered 2 days ago
lab bhattacharjee
214k14152263
answered 2 days ago
lab bhattacharjee
214k14152263
answered 2 days ago
lab bhattacharjee
214k14152263
214k14152263
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
add a comment |Â
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
Why with x+6? What is the logic?
– Bravo Jades
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
@BravoJades, Observe that all remainders are $-6$
– lab bhattacharjee
2 days ago
add a comment |Â
up vote
1
down vote
First take the LCM of $20,25,35,40$ which is $1400$
Now, Since the $$20-6=14\25-6=19\35-6=29\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$
Edit:
Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.
Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.
We took $-6$ form because it is common among all the given $4$ divisors.
answered 2 days ago
Key Flex
3,633422
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
add a comment |Â
up vote
1
down vote
First take the LCM of $20,25,35,40$ which is $1400$
Now, Since the $$20-6=14\25-6=19\35-6=29\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$
Edit:
Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.
Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.
We took $-6$ form because it is common among all the given $4$ divisors.
answered 2 days ago
Key Flex
3,633422
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
First take the LCM of $20,25,35,40$ which is $1400$
Now, Since the $$20-6=14\25-6=19\35-6=29\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$
Edit:
Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.
Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.
We took $-6$ form because it is common among all the given $4$ divisors.
answered 2 days ago
Key Flex
3,633422
First take the LCM of $20,25,35,40$ which is $1400$
Now, Since the $$20-6=14\25-6=19\35-6=29\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$
Edit:
Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.
Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.
We took $-6$ form because it is common among all the given $4$ divisors.
answered 2 days ago
Key Flex
3,633422
edited 2 days ago
answered 2 days ago
Key Flex
3,633422
answered 2 days ago
Key Flex
3,633422
answered 2 days ago
Key Flex
3,633422
3,633422
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
add a comment |Â
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately?
– Bravo Jades
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
@BravoJades See the edit.
– Key Flex
2 days ago
add a comment |Â
up vote
0
down vote
The question is flawed. There is no largest number like that, as you can add $operatornameLCM(20,25,35,40)=1400$ to any solution and get a larger one.
The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $operatornameLCM(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.
This is all based on the Chinese Remainder Theorem.
answered 2 days ago
Ross Millikan
275k21184350
add a comment |Â
up vote
0
down vote
The question is flawed. There is no largest number like that, as you can add $operatornameLCM(20,25,35,40)=1400$ to any solution and get a larger one.
The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $operatornameLCM(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.
This is all based on the Chinese Remainder Theorem.
answered 2 days ago
Ross Millikan
275k21184350
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The question is flawed. There is no largest number like that, as you can add $operatornameLCM(20,25,35,40)=1400$ to any solution and get a larger one.
The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $operatornameLCM(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.
This is all based on the Chinese Remainder Theorem.
answered 2 days ago
Ross Millikan
275k21184350
The question is flawed. There is no largest number like that, as you can add $operatornameLCM(20,25,35,40)=1400$ to any solution and get a larger one.
The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $operatornameLCM(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.
This is all based on the Chinese Remainder Theorem.
answered 2 days ago
Ross Millikan
275k21184350
answered 2 days ago
Ross Millikan
275k21184350
answered 2 days ago
Ross Millikan
275k21184350
answered 2 days ago
Ross Millikan
275k21184350
275k21184350
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%2f2871987%2ffinding-largest-number-with-gcd%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
You want the LCM, not the GCD here
– Ross Millikan
2 days ago