# Thread: mod proof by induction uses transitivity

1. ## mod proof by induction uses transitivity

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.

2. Originally Posted by pberardi
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.
Hi pberardi.

Modulo congruence is indeed a transitive relation. Suppose $\displaystyle a\equiv b\pmod n$ and $\displaystyle b\equiv c\pmod n.$ Then $\displaystyle a=b+rn$ and $\displaystyle b=c+sn$ for some integers $\displaystyle r,s.$ Hence $\displaystyle a=c+sn+rn=c+(r+s)n\equiv c\pmod n.$

In your problem, $\displaystyle 8^{n+1}\equiv8\pmod7$ and $\displaystyle 8\equiv1\pmod7$ imply $\displaystyle 8^{n+1}\equiv1\pmod7.$

3. 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.

4. Hello, pberardi!

Prove that, for each natural number $\displaystyle n\!:\;\;8^n \equiv 1\text{ (mod 7)}$

Show $\displaystyle S(1)$ is true: .$\displaystyle 8 \equiv 1 \text{ (mod 7)}$ or $\displaystyle 8 - 1 \:=\: 7k$ ... trivial

Assume $\displaystyle S(k)$ is true: .$\displaystyle 8^k \equiv 1\text{ (mod 7)}$

Show that: .$\displaystyle 8^{k+1} \equiv 1\text{ (mod 7)}$

Multiply by 8: .$\displaystyle 8\cdot8^n \:\equiv \:8\text{ (mod 7)}$

Since $\displaystyle 8 \equiv 1\text{ (mod 7)}$, we have: .$\displaystyle 8^{k+1} \equiv 1 \text{ (mod 7)}$

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: .$\displaystyle x \:=\:3^2 \:=\:9$

We must write something like:

. . $\displaystyle \begin{array}{ccc}\text{Statement} & & \text{Reason} \\ \hline x \:=\:3^2 & & \text{previous steps} \\ 3^2 \:=\:9 & & \text{arithmetic fact} \\ \therefore\;x = 9\quad & & \text{transitive property} \end{array}$