Modulo: Calculate really large numbers without a calculator

Question

working on a task: "Recall that $a \equiv b~[n]$ means that there exists an integer $k$ suck that $b = a + k \cdot n$. Are the following claims true or false?

5.a) $3 \equiv 5~[10]$

5.b) $4 \equiv 44~[10]$

5.c) $298709869876987655 \equiv 809809775~[10]$

I have done 5.a) and 5.b), I think. What I have done is pretty easy: $5 = 3 + 10 \cdot k$, and I set $k$ alone and got $k = (2/10)$, which means the claim is false.

I did the same for 5.b) which gave $k = 4$, which gives the claim is true. But this is a bit hard in 5.c) cause of the large number. Is there a better way to do this or to simplify the task?
And if this is wrong, please show me what I am suppose to do xD Thanks! :D

NOTE: I am suppose to do this without a calculater!

Even without a calculator, it is extremely easy to find the remainder of 298709869876987655 divided by 10 ... — hmakholm left over Monica, Jun 09 '16 at 11:49
This is simple modular arithmetic. And for $n=10$ it is extremely easy: Just compare the last decimal digit. — gammatester, Jun 09 '16 at 11:49
As I already said: Look at the last decimal digits. Claim a) is false because $3\ne 5,$ but b) and c) are true because in b) both numbers end with $4$ and in c) both numbers end with $5$. — gammatester, Jun 09 '16 at 12:05
Okey, thanks! Another question, if n for example have been n = 7, it would have been much harder, right? — Christian Iversen, Jun 09 '16 at 12:08
It would be harder, it actually is long division with remainder and for $n=3..9$ you should have learned this at school (and it is not much harder and doable without a calculator). — gammatester, Jun 09 '16 at 12:20
Yeah, I should have learned it at school, but I didn't, that's why I came here. Could u maybe tell me how I am suppose to do it if n = 1...9 ? — Christian Iversen, Jun 09 '16 at 12:40
Please read this tutorial on how to typeset mathematics on this site. — N. F. Taussig, Jun 09 '16 at 13:37

score 1 · Answer 1 · answered Jun 09 '16 at 13:45

For 5c it has already been mentioned in the comments. But let me try to provide a bit of detail.

Two numbers $n$ and $m$ are equal modulo $5$ when $5$ divides their difference. For example (in your notation) $3 \equiv 13\; [10]$ because $10$ divides $13 - 3 = 10$.

Another example if $15 = -25\; [10]$ because $15 - (-25) = 40$ is divisible by $10$.

In general then, if you have a number $n$ that where the last digit is $5$, then $n = 10m +5$ for some integer $m$. Let now $n'$ be another number where the last digit is a $5$. Then there is an integer $m'$ such that $n' = 10m' + 5$. Now look at their difference $$ n - n' = (10m + 5) = (10m' + 5) = 10(m+m') $$ This is clearly divisible by $10$ and so $n \equiv n'\; [10]$.

So since both numbers in your question (5c) have last digit $5$, they are equal modulo $5$.

score 1 · Answer 2 · answered Jun 09 '16 at 15:12

Recall that $a \equiv b \pmod n$ if $a$ and $b$ give the same remainder upon dividing by $n$. For example, if you divide each of $12$ and $77$ by $5$, the remainder is $2$ in both cases. Hence, $12 \equiv 77 \pmod 5$. Another way to say this is that $a \equiv b \pmod n$ iff $a-b$ is a multiple of $n$. In the example just given, $12-77$ is a multiple of $5$.

In the special case $n=10$, observe that $a \pmod {10}$ is just the units digit of $a$. For example, if you divide $12768$ by $10$, the remainder is the units digit $8$. Hence, $12768 \equiv 8 \pmod {10}$. It should now be clear that 5a) is false, 5b) is true and 5c) is true.

Modulo: Calculate really large numbers without a calculator

2 Answers2