# Homework Help: Hrm Congruence Proofs. Don't remember the rules

1. May 1, 2012

### 1MileCrash

Hrm... Congruence Proofs. Don't remember the "rules"

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

Take equals sign as congruence or equals based on context, please. Itex does not work in Opera.

Prove that for all n, 8^n = 1 (mod 7)

2. Relevant equations

3. The attempt at a solution

This will be a proof by induction.

Consider the case where n = 1.

Since 8^1 = 8, and 8 - 1 = 7, which is divisible by 7, we see that 8 = 1 (mod 7).

Now, assume that this theorem holds for some k in the natural numbers.

Then,

8^k = [1]

(8)8^k = [8][1]
8^(k+1) = [1][1] (since we know that 8 = 1(mod 7))
8^(k+1) = [1]

Thus, 8^k+1 = 1 (mod 7)

Therefore, the theorem holds for all n.

Been a while... sorry if it's really terrible.

2. May 1, 2012

### Staff: Mentor

Re: Hrm... Congruence Proofs. Don't remember the "rules"

Your logic is sound, but the work could be cleaned up in places. For example, you switch from 1 (mod 7) near the beginning to the [1] equivalence class. It would be better if you were consistent.

Also, what you wrote as 8^k+1 needs to be written as 8^(k + 1). This seems to have been a momentary lapse, as you wrote it correctly in the preceding work.

You might already know this, but 8^k+1 would be interpreted to mean 8k + 1, which isn't what you want.