Division without remainder?

Question

Prove that if 13^2n - 1 is divided without remainder by 168

Answer 1

Claim: 13^(2n) - 1 is divisible by 168 for all natural numbers n.

We need to prove this by induction.

Base case: Let n = 1. Then 13^(2n) - 1 = 13^2 - 1 = 169 - 1,
which is equal to 168, and 168 is obviously divisible by 168.

Induction hypothesis: Assume the formula holds true for up to some value k. That is, assume that

13^(2k) - 1 is divisible by 168.

{We want to prove that 13^[2(k + 1)] - 1 is divisible by 168}.

But, what does 13^[2(k + 1)] - 1 equal to?

If we expand the stuff in the exponent,

13^[2(k + 1)] - 1 = 13^(2k + 2) - 1

What I'm going to do now is decompose 13^(2k + 2) as
13^(2k) * 13^2.

= [13^(2k)] [13^2] - 1

Now, smack in the middle between the expression and -1, I'm going to add "zero" by subtracting [13^(2k)] and then adding [13^(2k)]

= [13^(2k)] [13^2] - [13^(2k)] + [13^(2k)] - 1

At this point, I'm going to factor the first two terms, and the last two terms

= [13^(2k)] (13^2 - 1) + [13^(2k)] - 1

Simplifying the 13^2 - 1, we get 169 - 1, or 168.

= { [13^(2k)] (168) } + { 13^(2k) - 1 }

Now, take a look at these two portions:

13^(2k) - 1 is divisible by 168, because of our induction hypothesis.

13^(2k) (168) is OBVIOUSLY divisible by 168.

Therefore, their sum is divisible by 168, and it follows that

13^[2(k + 1)] - 1 is divisible by 168.

Therefore, the formula holds true for n = k + 1.

Thus, by the Principal of Mathematical Induction,

13^(2n) - 1 is divisible by 168 for all natural numbers n.

Answer 2

This is equal to
169^n - 1
= (169 - 1) (169^(n-1) + 169^(n-2) ... + 169² + 169 + 1), difference of powers.

Look at the first factor.

Answer 3

Try multiplying 1 + x + x^2 + x^3 + x4 +x^5 by (x-1). It might give you a hint.