Extra Credit Problem: Find the smallest positive integer that is divisible by 13 and than when divided by any of the integers from 2 to 12 (inclusive) leaves a remainder of 1.
I offer you a variety of solution paths which you can apply to your problem.
Remainder Problems
Of the many famous problems from ancient times in circulation today, the remainder problems stand out as popular favorites. The typical format of such problems is of the form, "What is the smallest number that leaves a remainder of "a" when divided by "x' and a remainder of "b" when divided by "y"? The general problem is believed to have originated from the work of the Chinese mathematician Sun Tsu around 200 A.D. Not too surprisingly, problems of this type are referred to as Chinese Remainder Theorem problems as he developed the theorem that facilitates their solution.
A popular simple version that periodically makes the rounds is, "A farmer, taking her eggs to the market, hits a pothole in the road. The eggs all wind up broken. She goes to her insurance agent who asks the farmer how many eggs she had to begin with? She doesn't remember but she does remember that when she put them in groups of 2,3,4,5 and 6 she had one egg left over but when she put them in groups of 7, she had none left over. What is the minimum number of eggs that the farmer could have had? When the remainders are constant, the problem is rather simple to solve.
The L.C.M. (Lowest Common Multiple) of the numbers 2 through 6 inclusive is 2^2x3x5 = 60. The smallest number satisfying the divisors of 2 through 6 with remainders of 1 is therefore 60 + 1 = 61. Clearly, any multiple of 60 plus a 1 will satisfy these limited requirements. However, we are looking for a specific value of (60n + 1) that is evenly divisible by 7.or (60n + 1)/7. Dividing by 7, we get (60n + 1)/7 = 8n + 4n/7 + 1/7 or 8n + (4n + 1)/7 telling us that (4n + 1) must be a multiple of 7. Through observation, we can see that n = 5 is clearly the smallest integral value of n that will satisfy the condition. Therefore, the least number of eggs is (60x5 + 1) = 301.
Checking:
301/2 = 150 + 1
301/3 = 100 + 1
301/4 = 75 + 1
301/5 = 60 + 1
301/6 = 50 + 1
301/7 = 43
If we were not interested in the minimum amount of eggs, you can logically ask the question, "What other values of n will produce other answers?" Well, very quickly, 12 and 19 work. N(n=12) = 60(12) + 1 = 721. Thus, 721/2 = 360 + 1, 721/3 = 240 + 1, 721/4 = 180 + 1, 721/5 = 144 + 1, 721/6 = 120 + 1, and 721/7 = 103. N(n=19) = 60(19) + ! = 1141. Do you see the pattern in the additional values of n, 5, 12, 19,.......? The soluton is rather straight forward when the remainders are constant. If the remainders are all different however, the solution takes on a quite different challenge which we will address later.
An algebraic approach evolves as follows:
1--We seek the smallest number N that meets the requirements specified above.
2--We already know that the number 61 satisfies all the divisions and remainders up through the divisor of 6.
3--What we now seek is N = 7A = 61 + 60n or 7A - 60n = 61
4--Dividing through by the smallest coefficient yields A - 8n - 4n/7 = 8 + 5/7 or (4n + 5)/7 = A - 8n - 8
5--(4n + 5)/7 must be an integer as does (8n + 10)/7
6--Dividing by 7 again yields n + n/7 + 1 + 3/7
7--(n + 3)/7 is also an integer k making n = 7k - 3.
8--For the lowest value of k = 1, n = 4 making N = 61 + 60(4) = 301.
Again, higher values of N are derivable by letting k = 2, 3, 4,...etc. For k = 2, n = 11 making N = 721 and k = 3 leads to n = 18 or N = 1141.
<------------------------------------------------------------------------------------------------------->
A more typical form of the remainder problem is, "What is the smallest number N that leaves remainders of 1, 2, 3, and 4 when divided by 5, 7, 9, and 11 respectively?
This unique class of the problem requires the derivation of a specific number, usually the smallest possible, having specified remainders when divided by a series of numbers. While solvable by a variety of methods, the simplest, and by far the quickest, is by means of the Chinese Remainder Theorem. This theorem makes use of linear congruences, a topic that you might not yet have been exposed to. As this medium is not the place to attempt to educate you on such a broad topic, I must refer you to any good book on number theory for a detailed derivation and explanation of the topic of congruences and the theorem.
The Chinese Remainder Theorem solution can be simplified to the following procedure:
Ni = a1b1k1 + a2b2k2 + a3b3k3 + .......aibiki, the number we seek.
ai = the sequence of remainders
mi = the sequence of divisors
M = the product of the mi's
ki = M/mi
bi = the multiplier required to make b1k1 one greater than a multiple of mi.
Ni/M = x + N/M where N = the remainder is the answer we seek.
(Such problems are solvable when all pairs of the divisors are relatively prime to one another.)
There is also an algebraic method that is adequate for small sets of divisors/remainders but rather cumbersome for large sets. An abreviated version of the method simplifies the process somewhat. In the course of reviewing all the data developed for this problem and developing this article, I came across a few less complicated methods of deriving the answers. I will go through the processes as simply and clearly as I can showing you how the answers can be derived. You can be the judge as to which one you feel more comfortable with. Whatever you do, don't be discouraged. More importantly, have fun with it all.
Let us now consider the originally stated problem of what is the smallest number N that will leave a remainder of 1 when divided by 5, leave a remainder of 2 when divided by 7, leave a remainder of 3 when divided by 9, and leave a remainder of 4 when divided by 11?
Method 1
Given the 4 divisors, mi = 5, 7, 9, and 11 and the 4 corresponding remainders, ai = 1, 2, 3, and 4.
ai = the sequence of remainders
mi = the sequence of divisors
M = the product of the mi's
ki = M/mi where M = m1(m2)m3.......mi, the product of the moduli.
bi = the multiplier required to make b1k1 one greater than a multiple of mi.
N = a1b1k1 + a2b2k2 + a3b3k3 + .......aibiki, the number we seek.
Lets see what this all means and how we use it. For this problem, we have
1--a1 = 1, a2 = 2, a3 = 3, and a4 = 4
2--m1 = 5, m2 = 7, m3 = 9, and m4 = 11
3--M = 5x7x9x11 = 3465
4--k1 = 3465/5 = 693, k2 = 3465/7 = 495, k3 = 3465/9 = 385, and k4 = 3465/11 = 315
5--For b1, what number must 693 be multiplied by to make 693b1 one greater than a multiple of m1 = 5?
....693(1) - 1 = 692 which is not evenly divisible by m1 = 5.
....693(2) - 1 = 1385 which is divisible by 5 making b1 = 2.
....In a similar manner, b2 becomes 3, b3 becomes 4 and b4 becomes 8.
6--Ni = 1(2)693 + 2(3)495 + 3(4)385 + 4(8)315 = 1386 + 2970 + 4620 + 10,080 = 19,056, a solution.
7--Ni/M = x + N/M where N = the remainder.
8--Therefore, 19,056/3465 = 5 + 1731/3465.
9--The remainder, N = 1731, is our answer, the smallest number satisfying the requirements given.
Method 2
N/5 = A + 1/5 or N = 5A + 1
N/7 = B + 2/7 or N = 7B + 2
N/9 = C + 3/9 or N = 9C + 3
N/11 = D + 4/11 or N = 11D + 4
Combining (1) and (2), 5A + 1 = 7B + 2 or 5A - 7B = 1 or B = (5A - 1)/7
By trial and error for the first number only as once the first values of A and B are derived, all subsequent values derive from the fact that the successive differences in the values for A and B derive from the coefficient of B and A respectively. In other words, the next value of A is 10 since 3 plus 7 (the coefficient of B) equals 10 and the next value of B is 7 since 2 + 5 (the coefficient of A) equals 7.
A.....3.....10.....17.....24.....31.....38.....45......52.....59.....66.....73.....80.....87.....94.....101.....108.....115
B.....2......7......12.....17.....22.....27.....32......37.....42.....47.....52.....57.....62.....67.....72........77.......82
A.........................................192.....269.....346 some of the in between numbers left out.
B.........................................137.....192.....247 some of the in between numbers left out.
Combining (2) and (3), C = (7B - 1)/9
By trial and error again:
B.....13.....22.....31.....40.....49.....58.....67.....76.....85.....94.....103.....112.....121.....130.....139.....148
C.....10.....17.....24.....31.....38.....45.....52.....59.....66.....73......80.......87.......94......101.....108.....115
B.....157.....166.....175.....184.....193.....202.....211.....220.....229.....238.....247
C.....122.....129.....136.....143.....150.....157.....164.....171.....178.....185.....192
Combining (3) and (4), D = (9C - 1)/11
By trial and error again:
C.....5.....16.....27.....38.....49.....60.....71.....192
D.....4.....13.....22.....31.....40.....49.....58.....157
Combining (4) and (1), A = (11D + 3)/5
By trial and error again:
D.....2.....7.....12.....17.....22.....27.....32.....37.....42.....47.....52......87.......122....157
A.....5....16....27.....38.....49.....60.....71.....82.....93....104...115.....192.....269.....346
With some of the numbers left out of the table, the first consistent set of values across the four tables are A = 346, B = 247, C = 192 and D = 157 which create the number N = 5(346) + 1 = 7(247) + 2 = 9(192) + 3 = 11(157 + 4 = 1731, the same as derived through the Chinese Remainder Theorem method. It so happens with this particular problem that you have to go out quite far in the tabular data in order to find the first consistent set of values across the data.
Method 2a
N/5 = A + 1/5 or N = 5A + 1 (1)
N/7 = B + 2/7 or N = 7B + 2 (2)
N/9 = C + 3/9 or N = 9C + 3 (3)
N/11 = D + 4/11 or N = 11D + 4 (4)
1--Equating (1) and (2) yields 5A - 7B = 1
2--Dividing through by 5 yields 1A - 1B - 2B/5 = 1/5
3--(2B + 1)/5 must be an integer as does (6B + 3)/5
4--Dividing by 5 again yields B + B/5 + 3/5
5--(B + 3)/5 is also an integer k making B = 5k - 3.
6--Substituting back into (1) yields 5A -- 35k + 21 = 1 or A = 7k - 4.
7--k can be any positive integer from 1 on up yielding
k.....1.......2......3.......4......5.......6.......7.......8.......9.......10....11.....12.....13.....14......15.......16.......17
A.....3.....10.....17.....24.....31.....38.....45......52.....59.....66.....73.....80.....87.....94.....101.....108.....115
B.....2......7......12.....17.....22.....27.....32......37.....42.....47.....52.....57.....62.....67.....72........77.......82
k......................28.....29.....30
A....................192...269...346 (some of the in between numbers left out)
B....................137...19.....247 (some of the in between numbers left out)
8--The same process can be used to derive the subsequent tables of numbers
B.....13.....22.....31.....40.....49.....58.....67.....76.....85.....94.....103.....112.....121.....130.....139.....148
C.....10.....17.....24.....31.....38.....45.....52.....59.....66.....73......80.......87.......94......101.....108.....115
B....................229.....238....247
C....................178.....185....192
..................................and
C.....5.....16.....27.....38.....49.....60.....71.......................192
D.....4.....13.....22.....31.....40.....49.....58.......................157
..................................and
D.....2.....7.....12.....17.....22.....27.....32.....37.....42.....47.....52......................87.......122....157
A.....5....16....27.....38.....49.....60.....71.....82.....93....104...115.....................192.....269.....346
It becomes readily clear that both methods result in the same tabular data and answer with this method merely saving the derivation of the first two values of A and B by trial and error. Once the first two values have been determined, the followon values all differ by the same amount as the first two values.
Method 2b
It is possible to zero in on the correct answer without going through the sets of tabular data searching for a matching set of values. Unfortunately, it requires some extra algebraic work similar to what was done to acquire the tabular data. I'll show you how it works and let you decide which method is the best from your viewpoint.
What is the smallest number that leaves remainders of 1, 2, 3, and 4 when divided by the numbers 5, 7, 9, and 11 respectively?
1--We can express the requirements as N/5 = A + 1, N/7 = B + 2/7, N/9 = C + 3/9, and N/11 = D + 4/11.
2--Multiplying through by 5, 7, 9, and 11 yields N = 5A + 1, N = 7B + 2, N = 9C + 3 and N = 11D + 4.
3--Equating, 5A + 1 = 7B + 2 yields 5A - 7B = 1
4--Dividing through by the lowest coefficient, we get A - B - 2B/5 = 1/5 or (2B + 1)/5 = A - B.
5--(2B + 1)/5 must be an integer as does (6B + 3)/5
6--Dividing by 5 again yields B + B/5 + 3/5
7--(B + 3)/5 is an integer k1 making B = 5k1 - 3.
8--Substituting back into (3) yields 5A - 35k1 + 21 = 1 or A = 7k1 - 4.
9--Equating 7B + 2 = 9C + 3 yields 7B - 9C = 1.
10--Dividing through by 7 we get B - C - 2C/7 = 1/7 or (2C + 1)/7 = B - C.
11--(2C + 1)/7 must be an integer as does (8C + 4)/7.
12--Dividing by 7 again yields C + C/7 + 4/7
13--(C + 4)/7 is an integer k2 making C = 7k2 - 4.
14--Substituting back into (9) yields 7B -63k2 + 35 = 1 or B = 9k2 - 5.
15--Equating 9C + 3 = 11D + 4 yields 9C - 11D = 1
16--Dividing through by 9 yields C - D - 2D/11 = 1/9 or (2D + 1)/9 = C - D
17--(2D + 1)/9 must be an integer as does (10D + 5)/9
18--Dividing by 9 again yields D + D/9 + 5/9
19--(D + 5)/9 is an integer k3 making D = 9k3 - 5
20--Substituting back into (15) yields 9C - 99k3 + 55 = 1 or C = 11k3 - 6
21--Equating 11D + 4 = 5A + 1 yields 5A - 11D = 3
22--Dividing through by 5 yields A - 2D - D/5 = 3/5 or (D + 3)/5 = A - 2D
23--(D + 3)/5 must be an integer k4 making D = 5k4 - 3
24--Substituting back into (21) yields 5A - 55k4 + 33 = 3 or A = 11k4 - 6
25--We now have 8 expressions for A, B, C, and D in terms of k1, k2, k3, and k4.
26--Equating A = 7k1 - 4 = 9k3 - 5 or 9k3 - 7k1 = 1
27--Dividing through by 7 yields k3 + 2k3/7 - k1 = 1/7
28--(2k3 - 1)/7 must be an integer as does (8k3 - 4)/7
29--Dividing by 7 again yields k3 + k3/7 - 4/7
30--(k3 - 4)/7 is an integer m1 making k3 = 7m1 + 4
31--Substituting back into (26) yields 63m1 + 36 - 7k1 = 1 making k1 = 9m1 + 5.
32--Equating B = 5k1 - 3 = 9k2 - 5 or 9k2 - 5k1 = 2
33--Dividing through by 5 yields k2 + 4k2/5 - k1 = 2/5
34--(4k2 - 2)/5 must be an integer as does (16k2 - 8)/5
35--Dividing by 5 again yields 3k2 + k2/5 - 1 - 3/5
36--(k2 - 3)/5 is an integer m2 making k2 = 5m2 + 3
37--Substituting back into (32) yields 45m2 + 27 - 5k1 = 2 or k1 = 9m2 + 5
38--Equating C = 11k3 - 6 = 7k2 - 4 or 11k3 - 7k2 = 2
39--Dividing through by 7 yields k3 + 4k3/7 - k2 = 2/7
40--(4k3 - 2)/7 must be an integer as does (8k3 - 4)/7
41--Dividing by 7 again yields k3 + k3/7 - 7/7
42--(k3 - 4)/7 is an integer m3 makiing k3 = 7m3 + 4
43--Substituting back into (38) yields 77m3 + 44 - 7k2 = 2 or k2 = 11m3 + 6
44--Equating D = 5k4 - 3 = 9k3 - 5 or 9k3 - 5k4 = 2
45--Dividing through by 5 yields k3 + 4k3/5 - k4 = 2/5
46--(4k3 - 2)/5 must be an integer as does (16k3 - 8)/5
47--Dividing by 5 again yields 3k3 + k3/5 - 1 - 3/5
48--(k3 - 3)/5 is an integer m4 making k3 = 5m4 + 3
49--Substituting back into (44) yields 45m4 = 27 - 5k4 = 2 or k4 = 9m4 + 5
50--We now have 8 expressions for k1, k2, k3, and k4 in terms of m1, m2, m3, and m4.
51--Note, we have reduced the initial expressions for N to expressions in A, B, C, and D, then to expressions in k's, and finally to expressions in m's.
52--We need only make one more reduction of 2 expressions for m to an expression in n. (4 divisors and 4 remainders require 4 reductions).
53--Equating k1 = 11m1 + 6 = 9m2 + 5 or 9m2 - 11m1 = 1
54--Dividing through by 9 yields m2 - m1 - 2m1/9 = 1/9
55--(2m1 + =1)/9 must be an integer as does (10m1 + 5)/9
56--Dividing by 9 again yields m1 + m1/9 + 5/9
57--(m1 + 5)/9 is an integer n1 making m1 = 9n1 - 5
58--Substituting back into (53) yields 9m2 - 99m1 + 55 = 1 or m2 = 11n1 - 6
59--The lowest value of n1 will lead us to our minimum value for N.
60--Using either of the expressions for m1 and m2, for n1 = 1, m1 = 4 and m2 = 5.
61--Substituting m1 = 4 back into k1 = 11m1 + 6. yields k1 = 50.
62--Substituting k1 = 50 back into A = 7k1 - 4 yields A = 346.
63--Substituting back into N = 5A + 1 yields N = 1731.
A long time to get there but another path if you don't feel like dealing with tables of data.
Method 3
1--N/5 = A + 1/5 or N = 5A + 1
2--N/7 = B + 2/7 or N = 7B + 2
3--N/9 = C + 3/9 or N = 9C + 3
4--N/11 = D + 4/11 or N = 11D + 4
5--5A + 1 = 11D + 4 or A = (11D + 3)/5
6--7B + 2 = 11D + 4 or B = (11D + 2)/7
7--9C + 3 = 11D + 4 or C = (11D + 1)/9
8--(11D + 3) must be divisible by 5
9--(11D + 2) must be divisible by 7
10--(11D + 1) must be divisible by 9
8--By trial and error for the first value only
....D = 2 for (11D + 3)/5, D = 3 for (11D 21)/7, and D = 4 for (11D = 1).
9--Subsequent values of D derive from the constant difference of the two divisors or 5, 7, and 9.
10--From (11D + 3)/5, D = 2.....7.....12.....17.....22.....27 or D = 5m - 3.
..............(11D + 2)/7, D = 3....10....17.....24.....31.....38 or D = 7n - 4.
..............(11D + 1)/9, D = 4....13....22.....31.....40.....49 or D = 9p - 5
11--Equating 5m - 3 = 9p - 5 we get m = (9p - 2)/5
12--Equating 7n - 4 = 9p - 5 we get n = (9p - 1)/7
13--(9p - 2) must be divisible by 5.
14--(9p - 1) must be divisible by 7.
15--By trial and error for the first value only
.....p = 3 for (9p - 2)/5 and p = 4 for (9p - 1)/7
16--Subsequent values of p derive from the constant difference of the three divisors or 5, 7, and 9.
17--From (9p - 2)/5, p = 3.....8.....13.....18.....23.....28 or p = 5s - 2
.....From (9p - 1)/7, p = 4....11.....18.....25.....32.....39 or p = 7t - 3
18--Equating 5s - 2 = 7t - 3 we get 7t - 5s = 1
19--Dividing through by 5 yields t + 2t/5 - s = 1
20--(2t - 1)/5 must be an integer as does (6t - 3)/5
21--Dividing by 5 again, t + t/5 - 3/5
22--(t - 3)/5 is an integer k making t = 5k + 3
23--Substituting back into (18) yields 35k + 21 - 5s = 1 or s = 7k + 4.
24--For the lowest value of k = 0, s = 4 and t = 3.
25--Substituting back into (17), p = 5(4) - 2 = 7(3) - 3 = 18.
26--Substituting back into (10), D = 9(18) - 5 = 157.
27--Substituing back into (4) gives us N = 11(157) + 4 = 1731.
Method 4
After defining the above methods, I set out to derive a less complicated approach that would be applicable to any set of divisors and remainders. I first addressed the same sequence of divisors but with varying remainders. The early data produced the following:
Divisors........Remainders.......Least N..........Derivation
.....5........................1
.....7........................2......................16..............Observation (See * below)
.....9........................3.....................156.............N = 16 + 4(35)
....11.......................4....................1731............N = 156 + 5(315)
....13.......................5....................5196............N = 1731 + 1(3465)
Divisors........Remainders.......Least N..........Derivation
.....5........................1
.....7........................2......................16..............Observation (See below)
.....9........................4.....................121.............N = 16 + 3(35)
....11.......................7.....................436.............N = 156 + 1(315)
....13......................11..................28256...........N = 1731 + 8(3465)
Divisors........Remainders.......Least N..........Derivation
.....5........................1
.....7........................3......................31..............Observation (See below)
.....9........................6.....................276.............N = 16 + 7(35)
....11......................10....................2166...........N = 156 + 6(315)
....13......................15 (not possible as the remainder is bigger than the divisor)
* - The least N satisfying the requirements for the first 2 sets of numbers can be derived through observation or Method 2 or 2a above.
What does this data represent? The first set of divisors/remainders is the originally given problem with one more divisor/remainder added. The second set retains the same divisors but opens up a gap between the remainders. The third set also retains the same divisors and opens up the remainder gaps even further. Lets examine each set.
The N = 16 represents the least N that when divided by 5 and 7 leaves remainders of 1 and 2 respcetively. The N = 156 represents the least N that when divided by 5, 7, and 9 leaves remainders of 1, 2, and 3 respectively. The N = 1731 represents the least N that when divided by 5, 7, 9, and 11 leaves remainders of 1, 2, 3, and 4 respectively. The N = 5196 represents the least N that when divided by 5, 7, 9, 11, and 13 leaves remainders of 1, 2, 3, 4, and 5 respectively. The least N for the first 3 divisors/remainders is equal to the least N for the first 2 divisors/remainders plus 35n, 35 being the produce of the previous 2 divisors. The least N for the first 4 divisors/remainders is equal to the least N for the first 3 divisors/remainders plus 315n, 315 being the produce of the previous 3 divisors. And finally, the least N for the first 5 divisors/remainders is equal to the least N for the first 4 divisors/remainders plus 3465n, 3465 being the produce of the previous 4 divisors.
The same holds true for the other sets of data where the remainders are not consecutive. As much as I tried, I could not find any relationship between the known parameters and the derivation of "n." What did fall out of the study was that the method of successive reductions used in method 2 and 2a could be applied in finding the appropriate "n" for each desired solution. Lets see what develops with our current problem of what is the smallest number that will leave a remainder of 1 when divided by 5, a remainder of 2 when divided by 7, and a remainder of 3 when divided by 9?
Lets assume that we have already solved for the least N = 16 for the first 2 divisors/remainders. We now seek the least N for the first three divisors/remainders as defined by N/9 = A + 3/9 or N = 9A + 3. From what we just learned, we also know that the least N = 16 + 35n. Equating the two expressions, we get
1--9A + 3 = 16 + 35n or 9A - 35n = 13.
2--Dividing through by 9 yields A - 3n - 8n/9 = 1 + 4/9 or (8n + 4)/9 = 1 - A - 3n
3--(8n + 4)/9 must be an integer as does (64n + 32)/9
4--Dividing by 9 again yields 7n + n/9 + + 5/9
5--(n + 5)/9 is an integer k making n = 9k - 5
6--For k = 1, n = 4
7--Therefore, our least N derives fom N = 16 + 4(35) = 156.
Lets examine the second set of remainders where we ask what is the smallest number that will leave a remainder of 1 when divided by 5, a remainder of 2 when divided by 7, and a remainder of 4 when divided by 9? We already have the N = 156 for the first pair of divisors/remainders. We can now write N/9 = A + 4/9 or N = 9A + 4 which we can immediately equate to N = 16 + 35n.
1--9A + 4 = 16 + 35n or 9A - 35n = 12
2--Dividing by 9 yields A - 3n - 8n/9 = 1 + 3/9 or (8n + 3)/9 = 1 - A - 3n
3--(8n + 3)/9 must be an integer as does (64n + 24)/9
4--Dividing by 9 again yields 7n + n/9 + 2 + 6/9
5--(n + 6)/9 is an integer k making n = 9k - 6.
6--For k = 1, n = 3
7--Therefore, N = 16 + 35(3) = 121.
As long as we are on a roll, lets examine the third set of remainders where we ask what is the smallest number that will leave a remainder of 1 when divided by 5, a remainder of 3 when divided by 7, and a remainder of 6 when divided by 9? By trial and error or method 2 or 2a we alsread have the least N for the first two divisors/remainders of 5, 7 and 1, 3 as N = 31. We can now write N/9 = A + 6/9 or N = 9A + 6 which we can immediately equate to N = 31 + 35n.
1--9A + 6 = 31 + 35n or 9A - 35n = 25.
2--Dividing through by 9 yields A - 3n - 8n/9 = 2 + 7/9 or (8n + 7)/9 = 2 - A - 3n
3--(8n + 7)/9 must be an integer as does (64n + 56)/9
4--Dividing by 9 again yields 7n + n/9 + 5 + 2/9
5--(n + 2)/9 is an integer k making n = 9k - 2
6--For k = 1, n = 7
7--Therefore, N = 31 + 35(7) = 276.
It would appear that this approach is simpler than some of the other methods, at least for a small number of divisors/remainders. The application to 4 and 5 divisors/remainders will be shown later.
As applied to our current problem
From the data presented above, we have already solved for the least N = 156 for the first 3 divisors/remainders. We now seek the least N for the first four divisors/remainders as defined by N/11 = A + 4/9 or N = 9A + 4. From what we just learned, we also know that the least N = 156 + 315n (315 = the product of the first 3 divisors = 5x7x9). Equating the two expressions, we get
1--11A + 4 = 156 + 315n or 11A - 315n = 152.
2--Dividing through by 11 yields A - 28n - 7n/11 = 13 + 9/11 or (7n + 9)/11 = A - 13 - 28n
3--(7n + 9)/11 must be an integer as does (56n + 72)/11
4--Dividing by 11 again yields 5n + n/9 + 6 + 6/9
5--(n + 6)/11 is an integer k making n = 11k - 6
6--For k = 1, n = 5
7--Therefore, our least N derives fom N = 156 + 5(315) = 1731.
Having the least N for the divisors/remainders of 5, 7, 9, 11 and 1, 2, 3, 4, lets apply this method to the divisors/remainders of 5, 7, 9, 11, 13 and 1, 2, 3, 4, 5.
Having N = 1731 for the first four, we can write N/13 = A + 5/13 or N = 13A + 5 which we can immediately equate to N = 1731 + 3465n (3465 = 5x7x9x11).
1--13A + 5 = 1731 + 3465n or 13A - 3465n = 1726
2--Dividing by 13 yields A - 266n - 7n/13 = 132 + 10/13 or (7n + 10)/13 = A - 266n - 132
3--(7n + 10)/13 must be an integer as does (14n + 20)/13
4--Dividing by 13 again yields n + n/13 + 1 + 7/13
5--(n + 7)/13 = k making n = 13k - 7
6--For k = 1, n = 6
7--Therefore, N 1731 + 3465(6) = 22,521.
<----------------------------------------------------------------------------------------------------->
The following are a few derived rules for defining the least N's for varying combinations of divisors/remainders.
Consider the problem of finding the least N that when divided by the consecutive numbers of m through n leaves remainders of (m - 1) through (n - 1) respectively. The answer derives from the simple expression N = [(D1xD2xD3x.........Di) - 1]/2^p, "p" being some value from 0 on up. For instance, for divisors m = 2 and n = 4, N = [(2x3x4) - 1] = 23. For a variety of values of m and n
m....n.....R........N
2.....3....1-2.......5 = [(2x3)-1
2.....4....1-3......23 = [(2x3x4)-1]
2.....5....1-4......59 = [(2x3x4x5) - 1]/2
2.....6....1-5.....179 = [(2x3x4x5x6) - 1)]/4
2.....7....1-6.....1259 = [(2x3x4x5x6x7) - 1]/4
2.....8....1-7.....2519 = [(2x3x4x5x6xx7x8) - 1]/8
2.....9....1-8.....22,679 = [(2x3x4x5x6x7x8x9) - 1]/16
2....10...1-9....113,399 = [(2x3x4x5x6x7x8x9x10) - 1]/32
2....11...1-10..1,247,349 = [(2x3x4x5x6x7x8x9x10x11) - 1]/32
If the remainders are 2 less than the divisors, the general expressin for N becomes N = [(D1xD2xD3x........Di) - 2]/2^n.
If the remainders are 3 less than the divisors, the general expressin for N becomes N = [(D1xD2xD3x........Di) - 3]/2^n.
For consecutive odd divisors and consecutive remainders starting with R1, N = [(D1xD2xD3x.....Di) + (2R1 - D1)]/2 where D1 and R1 are the first divisor and first remainder.
For consecutive odd divisors and consecutive odd or even remainders up to R1 = D1 - 1, N = [D1xD2xD3x......Di] - [D1 - R1].
<------------------------------------------------------------------------------------------------------------>
Up to now we have examined problems with divisors and remainders that were in some kind of order, i.e., consecutive, odd or even, etc. I have not yet found a general rule for solving those variations of the problem where either the divisors or remainders are in no paricular order. Lets examine a few to see how they can be solved, recognizing, of course, that they can be solved by any of the methods presented above.
What is the least number N that leaves remainders of 3, 1, 5, and 7 when divided by 5, 7, 9, and 11 respectively?
I would use the abbreviated Chinese Remainder Theorem approach (Method 1a) or the simplified successive reductions approach (Method 4). Lets see how they lead us to our answer.
Given the 4 divisors, mi = 5, 7, 9, and 11 and the 4 corresponding remainders, ai = 3, 1, 5, and 7.
Method 1a
To refresh your memory:
ai = the sequence of remainders
mi = the sequence of divisors
M = the product of the mi's
ki = M/mi where M = m1(m2)m3.......mi, the product of the moduli.
bi = the multiplier required to make b1k1 one greater than a multiple of mi.
N = a1b1k1 + a2b2k2 + a3b3k3 + .......aibiki, the number we seek.
For this problem, we have
1--a1 = 3, a2 = 1, a3 = 5, and a4 = 7
2--m1 = 5, m2 = 7, m3 = 9, and m4 = 11
3--M = 5x7x9x11 = 3465
4--k1 = 3465/5 = 693, k2 = 3465/7 = 495, k3 = 3465/9 = 385, and k4 = 3465/11 = 315
5--For b1, what number must 693 be multiplied by to make 693b1 one greater than a multiple of m1 = 5?
....693(1) - 1 = 692 which is not evenly divisible by m1 = 5.
....693(2) - 1 = 1385 which is divisible by 5 making b1 = 2.
....In a similar manner, b2 becomes 3, b3 becomes 4 and b4 becomes 8.
6--Ni = 3(2)693 + 1(3)495 + 5(4)385 + 7(8)315 = 4473 + 1485 + 7700 + 17640 = 30,983, a solution.
7--Ni/M = x + N/M where N = the remainder.
8--Therefore, 30,983/3465 85 + 3263/3465.
9--The remainder, N = 3263, is our answer, the smallest number satisfying the requirements given.
Method 4
By inspection or analysis, we can see that the least N for divisors/remainders of 5-7/3-1 is 8.
1--For the divisors of 5-7-9, we can write N = 9A + 5 = 8 + 35n or 9A - 35n = 3
2--Dividing by 9 yields A - 3n - 8n/9 = 3/9 or (8n + 3)/9 = A - 3n
3--(8n + 3)/9 must be an integer sas does (64n + 24)/9
4--Dividing by 9 again yields 7n + n/9 + 2 + 6/9
5--(n + 6)/9 is an integer k making n = 9k - 6.
6--For k = 1, n = 3 making N(5-7-9) = 8 + 35(3) = 113.
7--For the divisors of 5-7-9-11, we can now write N = 11A += 7 = 113 + 315n or 11A - 315n = 106
8--Dividing by 11 yields A - 28n - 7A/11 = 9 + 7/11 or (7n + 7)/11 = A - 28n - 9
9--(7n + 7)/11 must be an integer as does (56n + 56)/11
10--Dividing by 11 again yields 5n + n/11 + 5 + 1/11
11--(n + 1)/11 is an integer k making n = 11k - 1
12--For k = 1, n = 10 making N(5-7-9-11) = 113 + 315(10) = 3263.
Rather simple I would say.
I have endeavored to provide you with a variety of methods for solving typical remainder problems. I leave it up to you to decide which one you feel most comfortable with. There are probably other variations of the problem that I have yet to encounter but I will continue to search for others. As others are discovered and solved, this material will be brought up to date accordingly. I hope you have found it all interesting, educational, and, above all, fun.
