Problem:
Let N denote the number of ordered triples of positive integers (a,b,c) such that a,b,cβ€36 and a3+b3+c3 is a multiple of 37. Find the remainder when N is divided by 1000.
Solution:
We have the following claims.
Claim 1. If a3+b3+c3 is divisible by 9, then either a,b, and c are all divisible by 3, or they all leave distinct residues modulo 3.
Proof. Note that cubes modulo 9 are 0,1,β1,0,1,β1,0,1,β1. For three cubes to add up to 0(mod9), they need to either be (0,0,0) or one of the six permutations of (0,1,β1). The first case corresponds to a,b, and c all being divisible by 3, and the second case corresponds to them all leaving distinct residues mod 3.
Claim 2. For every residue 0β€r<3n+1 satisfying rβ‘1(mod9), there is exactly one solution to the equation:
x3β‘r(mod3n+1)β
in the range 0β€x<3nβ1.
Proof. We will show the equivalent statement that the set {13,43,β¦,(3nβ2)3} of size 3nβ1 reduces down to {1,10,19,β¦,3n+1β8} after taking mod 3n+1.
Note that for every xβ‘1(mod3), we have x3β‘1(mod9). Therefore, this is equivalent to not having any repeats i.e. the statement that:
x3ξ β‘y3(mod3n+1)β
for any xξ =y where x,yβ{1,4,β¦,3nβ2}.
To see this, we will apply Lifting the Exponent Lemma. Note that since x,yβ‘1(mod3), we have 3β£xβy and 3β€x and 3β€y. Hence:
Ξ½3β(x3βy3)=Ξ½3β(xβy)+Ξ½3β(3)=Ξ½3β(xβy)+1β
Since 1β€x,yβ€3nβ2, we have β£xβyβ£<3n and so Ξ½3β(xβy)β€nβ1. Hence Ξ½3β(x3βy3)β€n, and so it is impossible for x3β‘y3(mod3n+1), as desired. This completes the proof of the claim.
Claim 3. There are 6β
9nβ1 ordered pairs of positive integers (a,b,c) with a,b,cβ€3n and 3n+1β£a3+b3+c3 such that a,b, and c leave distinct residues mod 3.
Proof. There are 3!=6 ways to assign the residues to the variables a,b, and c. Assume WLOG that aβ‘0(mod3),bβ‘1(mod3), and cβ‘2(mod3). Then, there are 3nβ1 choices for a and 3nβ1 choices for c. Finally, we must choose b such that bβ‘1(mod3) and:
b3β‘β(a3+c3)(mod3n+1)β
The idea is that for every possible choice of the ordered pair (a,b), there is exactly one possibility for c. This is because a3β‘0(mod9) and c3β‘β1(mod9), so β(a3+c3)β‘1(mod9). Therefore, the condition is equivalent to b3β‘r(mod3n+1) for some residue rβ‘1(mod9), which always has exactly one solution by Claim 2.
Hence, there are 6 ways to assign the order of the residues, 3nβ1 ways to choose a,3nβ1 ways to choose c, and 1 way to choose b (after choosing the other two variables). This yields a total of 6β
9nβ1 possibilities, as desired.
We are now ready to tackle the real problem. We break into two cases, as per Claim 1.
Case 1. a,b, and c have distinct residues mod 3.
In this case, there are 6Γ95=2β
311 possibilities, as per Claim 3.
Case 2. All of a,b, and c are divisible by 3.
In this case, we can write a=3a1β,b=3b1β, and c=3c1β. Our new problem is determining triples a1β,b1β,c1ββ€35 such that a13β+a23β+a33β is a multiple of 34. To do this, note that:
(x+33)3β‘x3+3β
33+3β
36+39β‘x3(mod34)β
by the Binomial Theorem and so we can find the number of triples with a1β,b1β,c1ββ€33 such that 34β£a13β+b13β+c13β, and then multiply by (3335β)3=729 at the end.
To tackle this, we can again split into two cases, as per Claim 1.
Case 2a. a1β,b1β, and c1β have distinct residues mod 3.
In this case, there are 6Γ92=486 possibilities, as per Claim 3.
Case 2b. All of a1β,b1β, and c1β are divisible by 3.
In this case, we can write a1β=3a2β,b1β=3b2β, and c1β=3c2β. We wish to determine the number of triples a2β,b2β,c2ββ€9 such that a23β+b23β+c23β is a multiple of 3. Note that this is equivalent to 3β£a2β+b2β+c2β since x3β‘x(mod3) for all x. Hence, we can pick a2β in 9 ways, then pick b2β in 9 ways, and then pick c2β in 3 ways (since its residue mod 3 is fixed). This yields 9β
9β
3=243 possibilities for this case.
Overall, in Case 2, we can see that we have 486+243=729 triples with a1β,b1β,c1ββ€33. As mentioned earlier, we extend this to 729β
729=312 triples satisfying a1β,b1β,c1ββ€35 and 34β£a13β+b13β+c13β.
Therefore, the the answer to the overall problem is:
2β
311+312=5β
311β‘735β(mod1000)β
since we can sum the results from Case 1 and Case 2, as desired.
Remark
Define Snβ to be the number of triples of positive integers (a,b,c) satisfying a,b,cβ€3n and 3n+1β£a3+b3+c3. Then, using Claim 3, we can show that:
Snβ=729β
Snβ3β+6β
9nβ1β
for all n>3, using a similar casework solution. Some small values of S are listed below:
S1βS2βS3βS4βS5βS6ββ=7=81=729=729β
7+6β
93=9477=729β
81+6β
94=5β
39=729β
729+6β
95=5β
311β
Note that the problem was asking for the value of S6β.
The problems on this page are the property of the MAA's American Mathematics Competitions