I need to see why this proof works. I have most of it I think but can someone clear me up here?
Prove that for each natural number n, 8^n = 1 mod 7
By induction show 1 is true
8 = 1 (mod 7) or 8 - 1 = 7k trivial
assume n is true there for 8^n = 1 (mod 7)
Show 8^(n+1) = 1 mod 7
multiply by 8
8*8^(n) = 8 (mod 7)
8^(n+1) = 8 (mod 7)
Now this is where I get confused. My TA said that now 8^(n+1) = 1 mod 7 because of a transitivity property. Could someone help me see this please? Is there another way of doing this that perhaps I can see it better? Thank you.
Ok thanks now that you put it that way I see it.
I think my trouble was that I was looking at it this way:
8^n = 1 mod 7 and
8^(n+1) = 8 mod 7 so
8^n = 8 mod 7
this does not help one bit.
But if I just switch them to
8^(n+1) = 8 mod 7
8^n = 1 mod 7
8^(n+1) = 1 mod 7
then your formula works fine. Thank you for showing me that.
Prove that, for each natural number
Show is true: . or ... trivial
Assume is true: .
Show that: .
Multiply by 8: .
Since , we have: .
Your demonstration is absolutely correct!
As The Abstrationist explained, you used the Transitive Property
. . though you probably didn't realize it.
Perhaps your course insists on a justification for every step?
If so, we cannot write: .
We must write something like: