Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
If you need to make the numbers smaller, you can use the Chinese remainder theorem and the fact that 174 = 2*3*29. (Although that might be more work in the end than just using 174.) You can also factor 20 = 2*10, and 4 = 2*2. Shouldn't be all that hard...
By the way, if you really have to do everything on paper, you can see this thread (post #7) for a description of fast modular exponentiation.
Edit: Upon further reflection, using the Chinese remainder theorem definitely results in less work. Mod 2, we see that from left to right we have an even minus an odd plus an even minus an odd, resulting in an even, so it is congruent to 0 (mod 2). Mod 3, the first two terms are both 2^22 (mod 3) and so together are 0 (mod 3), and the next term is simply 1^33 (mod 3) which is 1 (mod 3), so we see that the expression is congruent to 0 (mod 3). Now all we have to do is show that the expression is congruent to 0 (mod 29) and we are done. Working mod 29 should be more manageable on paper than 174. For 4^33 you can use Fermat's little theorem to get that 4^33 = 4^28*4^5 is congruent to 4^5 (mod 29).
Moderator edit: This post was moved from a thread created by a duplicate post. Unfortunately I misread the time stamps on both threads, which is why this post preceeds the original post (which is post #2 below). Apologies for any confusion.