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$.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Welcome to Math.SE! Please use MathJax. For some basic information about writing math at this site, see mathjax tutorial and quick reference and equation editing how-to. Please read this post for writing a good question. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Apr 12 '19 at 15:17
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
-
-
2$\begingroup$ Note that the question is titled by induction $\endgroup$ – Bill Dubuque Apr 12 '19 at 15:35
$\begingroup$
$\endgroup$
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$$
answered Apr 12 '19 at 15:59
$\begingroup$
$\endgroup$
2
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$.
-
1
-
