-1
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

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.

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

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$$

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ This is not induction. $\endgroup$ – Shubham Johri Apr 12 '19 at 15:53
  • $\begingroup$ This is complete induction. $\endgroup$ – lhf Apr 12 '19 at 16:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.