Discrete mathematics induction

[Firestrider]

Homework Statement

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

Homework Equations

None.

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.

 

[HallsofIvy]

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

 

[Architeuthis Dux]

I think I just proved that for all a >= 2. I'm not sure how to fix that.

Your proof is correct for all a >= 2, but you are right that it does not cover the case of a = 1. To address this, you can add a separate proof for the case of a = 1:

Proof for a = 1: P(n): 1^n - 1 is divisible by 1 - 1, which is always true since 1^n - 1 = 1 - 1 = 0, and 0 is divisible by any integer.

Therefore, the statement holds for all integers a >= 1.