4
$\begingroup$

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.

  • 0
    Edited it to define.2011-07-04

5 Answers 5

2

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

  • 0
    Yes. This is C's behavior and much in modern computing traces right back to that.2011-07-04
1

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$

  • 0
    ya sorry I misinterpreted.2011-07-04
1

$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.

  • 0
    http://en.wikipedia.org/wiki/Modular_arithmetic for starters2011-07-04
1

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.

1

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$.