The following attached image is the problem I need help on. Thank you so much.
Prove that $a\mod m=a-\left[\frac am\right]m$ where $$[x]=\max\left\{y\in \Bbb Z, y\leq x\right\}$$
Asked
Active
Viewed 542 times
1
Kevin Long
- 5,159
Abbi Wilson
- 11
-
1You should include your attempts on the question – John Doe Oct 03 '17 at 18:13
-
2You say (three times!) that you need an answer. I say you that we have an urgent need of your attempts ... – Jean Marie Oct 03 '17 at 18:15
-
1Doesn't this look like a rewriting of the Euclidean division algorithm? – Michael McGovern Oct 03 '17 at 18:17
-
Here's a starting point- how do you define $a=b \mod m$? In number theory, we say $a\equiv b(\mod m)$ if $m$ divides $a-b$, so what you have written would be easy to show. How is it defined in your class? – Kevin Long Oct 03 '17 at 18:54
1 Answers
1
This is how I would prove it with words and a minimal amount of algebra: We know that $a \ mod \ m$ gives the remainder of $\frac{a}{m}$. If we look at the decimals of $\frac{a}{m}$, it's how many times $m$ can't fit inside of $a$. E.g. we have $a = 16, m = 5$, then $\frac{16}{5} = 3.2$. here we can see that the decimal part of $3.2$, i.e. $0.2$, is how many times the $5$ can't fit inside of $16$ after the division (or in other words the remainder).
Because these two are equal we can say that $$a \ mod \ m = \Big\{\frac{a}{m}\Big\}m \tag{1}$$ Here $\{\frac{a}{m}\}$ is the decimal part of $\frac{a}{m}$.
It's quite easy to see that $$\{\frac{a}{m}\} = \frac{a}{m} - \left \lfloor \frac{a}{m} \right \rfloor \tag{2}$$
I.e. the decimal part of a fraction, is the same as the entire fraction, after you've removed the integer part of the fraction. E.g. $\{\frac{16}{5}\} = 0.2 = \frac{16}{5} - \left \lfloor \frac{16}{5} \right \rfloor = 3.2 - 3$.
Substitute these simple observations into each other, i.e. $(2)$ into $(1)$ to get: $$a \ mod \ m = \Big(\frac{a}{m} - \left \lfloor \frac{a}{m} \right \rfloor\Big)m$$
$$a \ mod \ m = a - \left \lfloor \frac{a}{m} \right \rfloor m$$
And we're done.
Note: the floor function is the same as the max function that you defined.
Sam Anderson
- 698