Number Theory and problem solving

I'll try to take you through the steps of solving a basic number theory problem:

Find the smallest positive integer whose cube ends in 888.


How do we begin? And keep in mind that this is a non-calculator question, although you should be expected to be able to pump out some basic arithmetic without one.

Perhaps we can start by looking at an easier problem: whats the smallest integer whose cube ends in 8? Hopefully it didn't take you more than a few seconds to see that it's 2. Next you should ask yourself, does this mean that any integer whose cube ends in 8 has to end in 2? No other single digit cubed ends in 8 (you can check). Also, the unit digit in a multiplication will only be affected by the unit digit of the factors. So this should mean that it has to end in 2.

Now lets work our way up - whats the smallest integer whose cube ends in 88? At first this seems a lot harder, but we can use what we already figured out to make it easier. Realize that the units and tens digit will only be affected by the units and tens digit of the products. So technically, we should be able to actually do out the multiplication of cubing "x2", where x is our unknown digit. You'll have to keep track of the tens digits while adding by considering them mod 10 only. I'll try to draw it out as best as I can here:

x 2
* x 2
------------
2x 4
2x
------------
4x 4
x 2
-------------
8x 8
4x
-------------
12x 8

Now our problem is just, what is the smallest digit x such that 12x is congruent to 8 mod 10. Which is just 4. So the smallest integer cubed who ends in 88 is 42.

Now lets try applying this method to 888. We can't assume that the tens digit is 4, but we can assume that the ones digit is still 2. I won't draw out everything here, but letting the number be x y 2 yields:

(12x + 6y^2) (12 y) (8)

This time, when we find a number for y, we can't just take it mod 10- we'll have to consider what is carried over and add it to the left.

Let's deal with y first. If y is 4 or 9, then 12y is congruent to 8 mod 10. Lets try 4 first:

(12x + 6*16) (48) (8)
(12x + 6*16 + 4) (8) (8)
(12x + 100) (8) (8)

So the smallest x such that 12x + 100 is 8 mod 10 is 4. That yields 442 as a possible number. However, trying out 9 might yield a smaller hundreds digit, so lets try it.

(12x + 6*81) (108) (8)
(12x + 486 +10)(8) (8)

(12x + 496) (8) (8)

So the smallest x such that 496 is 8 mod 10 is 1, yielding 192. Certainly much smaller than 442. Can we say for sure that these are the smallest possible numbers? We showed that any number whose cube ends in 888 must end in these numbers. We also explored the different cases, and picked the smallest from each, so there are no other possibilities for a smaller number. Our final answer is thus 192.

Keep in mind that this isn't the only way to do this. We could also have analyzed the expansion of (100a + 10b + 2)^3. Personally, I preferred the previous method because I'm not exceptional at expanding anything past binomials, but it would be good practice. In fact, I'll try it later tonight.

If anybody happens to be reading this, heres a problem for you - Find the smallest positive integer whose cube ends in 69. And do it WITHOUT brute forcing! (Hint, expand it, and take it mod 100).

By the way, it really isn't worth "memorizing" this trick. The most important thing is being able to solve it on your own, without having seen a very similar problem. That doesn't mean you shouldn't try to relate to elementary problems or other ones that you HAVE memorized, though!

What I'm trying to say is, that if you had never seen a problem like this, and after looking at it for a minute, you thought "eh, this is too hard, whatever." then you're NOT TRYING HARD ENOUGH. Here's a prime example: If you've ever looked at the USAMTS problems, they're hard. Maybe not quite USAMO level, or if you don't look at each one for more than an hour, depending on its difficulty, you probably won't solve it. I have a friend, who is very smart and good at math, and I asked him to try USAMTS this year. His response was:

"Nah, I looked at the problems last night and I couldn't get any, so it's probably too hard for me."

I'm going to try to convince him again, but a key part of problem solving is to not back down from a problem. You have to take the time to explore, play around with, and change the problem until you have a good idea of what is going on, before you can actually solve it. Just because you don't see the solution right away doesn't mean it's not there.