# finding remainder by dividing a sum

Suppose I am dividing 4^30-2^50 by 5.

I do understand that 4^30 will get converted to 2^60

I could also find the series of remainders for 2^x. It comes out to be 2 4 3 1

By that, I could find (4^30) % 5 = 1 and (2^50) % 5 = 4. But how do I find the combined mod?

i.e. [(4^30)-(2^50)] % 5 = ? Thank you.

P.S. Please note that by %, I mean mod operator.

-
$(a \mod c) + (b \mod c) = ((a+b) \mod c)$ – Aryabhata Jul 4 '11 at 14:27
Are you adding or subtracting? – Mark Bennet Jul 4 '11 at 14:27
sorry I am subtracting. Edited. – mihsathe Jul 4 '11 at 14:28
You might want to note a useful trick for these kinds of calculations - observe that $4 \equiv -1$ $mod5$ It is therefore easier to compute $(-1)^{30} \equiv 4^{30}$ and $2^{50} = 4^{25} \equiv (-1)^{25}$ – Mark Bennet Jul 4 '11 at 14:34
I really don't get it. What is the reason programmers want to use the remainder operation, when a congruence is so much easier? Problems like this one disappear. I could understand it, if programs gave comparable answers in a fixed range. But many processors and/or languages specify this funny behavior with negative numbers, so you don't get that fixed range of values anyway. – Jyrki Lahtonen Jul 4 '11 at 14:43

$$(a + b)\%n = (a\%n + b\%n)\%n.$$

-
Watch out for the bad behavior of % in most computing languages. In Python, (-7)%5 gives you -2, when it seems more plausible to me to give 3. – ncmathsadist Jul 4 '11 at 14:30
^Even the windows calculator does the same.. – mihsathe Jul 4 '11 at 17:09
Yes. This is C's behavior and much in modern computing traces right back to that. – ncmathsadist Jul 4 '11 at 17:13

The remainder of a sum is (the remainder of) the sum of the remainders (the same goes for differences, and products). That means

$$(4^{30}-2^{50}) \mod 5 = (1-4) \mod 5 = 2$$

-
@mihsathe : yes $(-3) \mod 5 = 2$ (because $-3 = 5 \times (-1) + 2$). Isn't it what I wrote ? – Joel Cohen Jul 4 '11 at 14:36
ya sorry I misinterpreted. – mihsathe Jul 4 '11 at 14:36

$4^{30}\equiv 1$ and $2^{50}\equiv 4$, so $4^{30}-2^{50}\equiv 1-4\equiv2.$ All the congruences are $\pmod {5}$, so pointless to write it down.

-
I do not understand congruences. Can you suggest me some sources? – mihsathe Jul 4 '11 at 14:58
en.wikipedia.org/wiki/Modular_arithmetic for starters – Jyrki Lahtonen Jul 4 '11 at 16:12

HINT $\$ Specialize $\rm\ a = A\:\%\:m,\ \ b = B\:\%\:m\ \$ in the $\:$ Congruence Sum Rule

$$\rm\:A\equiv\: a\:,\ B\equiv\: b\ \ \Rightarrow\ \ A+B\equiv\: a+b\ \ (mod\ m)\ \ \Rightarrow\ \ (A+B)\:\%\:m\ =\ (a+b)\:\%\:m$$

i.e. if two equivalence classes coincide, then so too do their canonical representative elements.

-

If $a\equiv b\pmod m$ and $c\equiv d\pmod m$, then $a\pm c\equiv b\pm d\pmod m$.

Since $4^{2k+1}\equiv 4\pmod 5$ and $4^{2k}\equiv 1\pmod 5$, $4^{30}=4^{2\cdot 15}\equiv 1\pmod 5$.

Also, $2^{4k}\equiv 1\pmod 5$, $2^{4k+1}\equiv 2\pmod 5$, $2^{4k+2}\equiv 4\pmod 5$ and $2^{4k+3}\equiv 3\pmod 5$. Hence $2^{50}=2^{4\cdot 12+2}\equiv 4\pmod 5$.

Then $4^{30}-2^{50}\equiv 1-4\pmod 5\equiv -3\pmod 5$. But, since $-3\equiv 2\pmod 5$, we have $4^{30}-2^{50}\equiv 2\pmod 5$.

-