Question 459304: Find the smallest possible integer which, when divided by 3 has a remainder of 1, when divided by 4 has a remainder of 2, and when divided by 5 has a remainder of 3.
Found 2 solutions by richard1234, Edwin McCravy:
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! According to the Chinese remainder theorem, there must exist an integer and all such solutions are congruent modulo 60. Since adding 60 will not change the residue of each of the three cases (3, 4, 5), we now know that the smallest possible positive integer that satisfies is less than 60. I just used trial and error and got 58 as the smallest possible integer. We can also see that 118, 178, ... satisfy as well.
Answer by Edwin McCravy(20054)  (Show Source):
You can put this solution on YOUR website!
Here it is worked out using algebra:
Let N be the answer. Then there exist positive integers A, B, and C
such that:
N = 3A + 1 = 4B + 2 = 5C + 3
3A + 1 = 4B + 2
3A - 4B = 1
Principle P:
This is the principle of
1. Writing the absolute value of
each integer or coefficient in an equation in terms
of its nearest multiple of the coefficient in absolute
value that occurs in the equation,considering 0 as a
multiple of every integer,
2. Removing parentheses
3. Dividing every term by that least coefficient in
absolute value.
4. Isolating all fractional
terms.
5. Setting both sides equal to a new positive integer
variable:
Using principle P on
3A - 4B = 1
3A - (3 + 1)B = 1
3A - 3B - B = 1
A - B - B/3 = 1/3
A - B = 1/3 + B/3
Let D = A - B = 1/3 + B/3
D = 1/3 + B/3
3D = 1 + B
(1) B = 3D - 1
D = A - B
D = A - (3D - 1)
D = A - 3D + 1
4D - 1 = A
(2) A = 4D - 1
4B + 2 = 5C + 3
4(3D - 1) + 2 = 5C + 3
12D - 4 + 2 = 5C + 3
12D - 2 = 5C + 3
12D - 5C = 5
Use principle P on that equation:
(10+2)D - 5C = 5
10D + 2D - 5C = 5
2D + 2D/5 - C = 1
2D/5 = C - 2D + 1
2D/5 = C - 2D + 1 = E
C - 2D + 1 = E
(3) C = E + 2D - 1
2D/5 = E
2D = 5E
Use the principle P again:
2D = (4+1)E
2D = 4E + E
D = 2E + E/2
D - 2E = E/2
E/2 = D - 2E = F
E/2 = F, D - 2E = F
E = 2F
D - 2(2F) = F
D - 4F = F
(4) D = 5F
From (3)
C = E + 2D - 1
C = 2F + 2(5F) - 1
C = 2F + 10F - 1
C = 12F - 1
(5) C = 12F - 1
From (1)
B = 3D - 1
B = 3(5F) - 1
(6) B = 15F - 1
D = A - B
5F = A - (15F - 1)
5F = A - 15F + 1
20F - 1 = A
A = 20F - 1
B = 15F - 1
C = 12F - 1
Therefore the smallest values of A, B, and C
will be when F=11
A = 20F - 1 = 20 - 1 = 19
B = 15F - 1 = 15 - 1 = 14
C = 7F - 1 = 12 - 1 = 11
N = 3A + 1 = 4B + 2 = 5C + 3
N = 3(19) + 1 = 4(14) + 2 = 5(11) + 3
N = 58 = 58 = 58
Edwin
|
|
|
