1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 1, 2012 #1
    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.


    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. jcsd
  3. May 1, 2012 #2


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook