49n+16n-1 is divisible by 64
Answers
OK, I'm assuming anyone reading this will be familiar with the concept a mod b... If you're not, a mod b is the remainder you'd get dividing a by b. I'm going to use = for "congruent to" here...
What this boils down to proving is that:
49^n + 16n = 1 mod 64
Let's start with the easy stuff...
Power of 49 49^n mod 64
0 1
1 49
2 33
3 17
4 1
WELL! Now, THAT simplifies things a lot, doesn't it? The index of 49 mod 64 is merely 4...
Thus, for all n, let n = a mod 4. Then, we can say that
49^n = 49^a mod 64.
OK, now all we have to do is get this 16 n thing in there...
When you do that, you get:
49^n mod 64 49^ n + 16n mod 64
1 1
49 49 + 16 = 65
33 33 + 32 = 65
17 17 + 48 = 65
1 1 + 64 = 65
In all of these cases, subtract 1 and you get 64...
Now, a more formal proof is possible, but I'm not sure how much number theory you've got, so I'm taking the easy, somewhat sleazy, computationally based proof...