# Exercise on number theory / by induction [closed]

For every integer number $$n$$, prove that $$10^n$$ and $$10^r$$ leave the same remainder when divided by $$7$$, where $$r$$ is the remainder of $$n$$ when divided by $$6$$.

## 3 Answers

Write $$n = 6m + r$$ for some integer $$m$$. Then $$10^n = 10^{6m + r} = (10^6)^m \cdot 10^r \equiv 10^r \pmod{7},$$ where the last equality comes from the fact that $$10^6 \equiv 1 \pmod{7}.$$ This can be either calculated directly or proved via Fermat's little theorem.

• yes , that's right thanks a lot . – Bedoor .s Apr 12 '19 at 15:27
• Note that the question is titled by induction – Bill Dubuque Apr 12 '19 at 15:35

Clearly the statement is true for $$n=1$$. Now, assume for some $$k\in\Bbb N$$ that $$10^k$$ leaves the same remainder as $$10^r$$ when divided by $$7$$, where $$k=6q+r,~0\le r<6$$.$$10^{k+1}=10(10^k)\equiv10(10^r)=10^{r+1}\mod7$$If $$r+1<6$$, then $$k+1$$ divided by $$6$$ yields $$r+1$$ as the remainder, so we are done. If $$r+1=6,k+1$$ divided by $$6$$ yields remainder $$0$$, that is, $$k+1=6m,m\in\Bbb N$$. Thus,$$10^{k+1}=10^{6m}=(10^6)^m\equiv1=10^0\mod 7$$

Using (complete) induction:

If $$n < 6$$, there is nothing to prove.

If $$n \ge 6$$, write $$n=6+m$$ and get $$10^n = 10^{6+m} = 10^6 \cdot 10^m \equiv 10^m \bmod{7}$$, because $$10^6 \equiv 3^6 \equiv 1 \bmod{7}$$.

Since $$m < n$$, we have $$10^m \equiv 10^r \bmod{7}$$ by induction, where $$r$$ is the remainder of $$m$$ mod $$6$$.

Finally, note that $$n \equiv m \bmod 6$$ and so $$r$$ is the remainder of $$n$$ mod $$6$$.

• This is not induction. – Shubham Johri Apr 12 '19 at 15:53
• This is complete induction. – lhf Apr 12 '19 at 16:56