# Discrete mathematics induction

1. Nov 11, 2008

### Firestrider

1. The problem statement, all variables and given/known data

Prove that for all integers a >= 1, a^n - 1 is divisible by a - 1 for all n >= 1.

2. Relevant equations

None.

3. The attempt at a solution

Proof - Let P(n): a^n - 1 is divisible by a - 1, then

P(1): a^1 - 1 is divisible by a - 1 is TRUE since a^1 - 1 = a - 1, and a - 1 = (1)(a - 1)

Suppose that P(k): a^k - 1 is divisible by a - 1 is TRUE. Then, there exists an integer q such that a^k - 1 = (a - 1)q or a^k = (a-1)q + 1

Now consider a^(k+1) - 1 = a(a^k) - 1
= a((a - 1)q + 1) - 1
= (a)(a - 1)q + a - 1
= (a - 1)aq + (a - 1)
= (a - 1)(aq + 1)

Thus, a^(k+1) - 1 is divisible by a - 1 whenever a^k - 1 is divisible by a - 1. Therefore, a^n - 1 is divisible by a -1 for all n >= 1.

The problem I'm having is I don't think I proved that for all a >= 1.

2. Nov 11, 2008

### HallsofIvy

No, there is no requirement that a- 1 be greater than 0 so there is no requirement that a be greater than 1.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook