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.

  • 1
    $(a \mod c) + (b \mod c) = ((a+b) \mod c)$2011-07-04
  • 0
    Are you adding or subtracting?2011-07-04
  • 1
    sorry I am subtracting. Edited.2011-07-04
  • 3
    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}$2011-07-04
  • 0
    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.2011-07-04
  • 0
    Sorry about that. I'm having a grumpy day. Props to the OP for using $\%$ as opposed to 'mod' :-)2011-07-04
  • 0
    @Jyrki Lahtonen sorry for that. I've been programming since I was 8. It sure has affected my thinking some way. Next time I'll definitely use `mod`. Thanks for the pointer.2011-07-04
  • 0
    Since this is a Mathematics site and not a programmer one, for those who are not familiar with the % notation, it would help if you define it.2011-07-04
  • 0
    Edited it to define.2011-07-04

5 Answers 5

2

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

  • 2
    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.2011-07-04
  • 0
    ^Even the windows calculator does the same..2011-07-04
  • 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
    @mihsathe : yes $(-3) \mod 5 = 2$ (because $-3 = 5 \times (-1) + 2$). Isn't it what I wrote ?2011-07-04
  • 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
    I do not understand congruences. Can you suggest me some sources?2011-07-04
  • 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$.