1

Show that the natural number $a$ with base ten representation ($r_{k}$$r_{k-1}$. . . $r_{1}$$r_{0}$)$_{10}$ is a multiple of 4 if and only if the number ($r_{1}$$r_{0}$)$_{10}$, consisting of the rightmost 2 digits of $a$, is a multiple of 4,that is show 4|$a$ = ($r_{k}$$r_{k-1}$. . . $r_{1}$$r_{0}$)$_{10}$ $\iff$ 4|($r_{1}$$r_{0}$)$_{10}$.

I have no idea where to begin.

Potato
  • 40,171
Mark
  • 335

1 Answers1

5

HINT:

$$\begin{align*} (r_kr_{k-1}\ldots r_1r_0)_{10}&=100(r_k\ldots r_2)_{10}+(r_1r_0)_{10}\\ &=4\cdot25(r_k\ldots r_2)_{10}+(r_1r_0)_{10} \end{align*}$$

Brian M. Scott
  • 616,228
  • So am I supposed to break 100 into a prime decomposition? Or do I show examples of natural numbers with base 10 reps as multiples of 4? – Mark Nov 18 '13 at 01:44
  • @Mark: You don’t have break anything up more than I already did. All of the necessary algebra has already been done in the hint. Further HINT: If $a=b+c$, where $a,b$, and $c$ are integers, and two of $a,b$, and $c$ are multiples of $4$, what can you say about the third? – Brian M. Scott Nov 18 '13 at 01:48
  • what do you mean by the third? – Mark Nov 18 '13 at 01:51
  • @Mark: The third of the three numbers $a,b$, and $c$. – Brian M. Scott Nov 18 '13 at 01:52
  • that the third are multiples of 4 as well? – Mark Nov 18 '13 at 01:53
  • @Mark: Exactly. Do you see why, and how to use this and the hint to prove the result that you want? – Brian M. Scott Nov 18 '13 at 01:53
  • Not exactly. Would you be able to explain that a bit more? – Mark Nov 18 '13 at 01:54
  • @Mark: If $a=4m$ and $b=4n$, then $c=a+b=4m+4n=4(m+n)$. If $a=4m$ and $c=4n$, then $b=c-a=4n-4m=4(n-m)$. If $b=4m$ and $c=4n$, then $a=c-b=4n-4m=4(n-m)$. In every case in which two of the three numbers are multiples of $4$, so is the third. The hint says that $n=4m+k$, where $n$ and $k$ are ... ? – Brian M. Scott Nov 18 '13 at 01:57
  • Ok I understand that for all cases of a,b,c, they are multiples of 4. But how does that relate to the first hint you gave me? I just don't see how they relate. – Mark Nov 18 '13 at 02:03
  • @Mark: The hint says that three numbers $n,m$, and $k$ are related in the following way: $n=4m+k$. What $n,m$, and $k$ am I talking about here? – Brian M. Scott Nov 18 '13 at 02:04
  • I'm not really sure. I'm confused on where you got $m$. I apologize, to you it might be simplistic to understand. It's not quite easy when you're trying to comprehend this for the first time. – Mark Nov 18 '13 at 02:08
  • @Mark: Oops; I should make that $n=4m+\ell$ to avoid a clash with the already-defined $k$. Look at the form of the equation in the hint: $$(r_k\ldots r_1){10}=4\cdot25(r_k\ldots r_2){10}+(r_1r_0)_{10};.$$ Match that up with the form $n=4m+\ell$. Which entity in the displayed equation matches each of $n,m$, and $\ell$? – Brian M. Scott Nov 18 '13 at 02:12
  • I know that $n$ is ($r_{k}$ . . . $r_{1}$)${10}$, m is 25($r{k}$. . . $r_{2})$${10}$ and $l$ is ($r{1}$$r_{0}$)$_{10}$. – Mark Nov 18 '13 at 02:17
  • @Mark: Then you’re practically there. Certainly $4m$ is a multiple of $4$. If $n$ is also a multiple of $4$, then ... what? Alternatively, if $\ell$ is also a multiple of $4$, then ... what? – Brian M. Scott Nov 18 '13 at 02:19
  • Ok let me see if I understand this correctly. We know that 4m is a multiple of 4 (since you broke it down to 4 x 25). If n is also a multiple of 4 then m and l are multiples of 4. If l is a multiple of 4, then n and 4m are multiples of 4. – Mark Nov 18 '13 at 02:27
  • @Mark: Not quite. If $n$ is a multiple of $4$, then $n$ and $4m$ are multiples of $4$, so $\ell=n-4m$ is a multiple of $4$. If $\ell$ is a multiple of $4$, then $\ell$ and $4m$ are multiples of $4$, so $n=4m+\ell$ is a multiple of $4$. Thus, $n$ is a multiple of $4$ if and only if $\ell$ is a multiple of $4$. – Brian M. Scott Nov 18 '13 at 02:32
  • Oh ok. I got it. Thanks for your patience. – Mark Nov 18 '13 at 02:33
  • @Mark: You’re welcome. – Brian M. Scott Nov 18 '13 at 02:36