Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
$(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
1  
sorry I am subtracting. Edited. –  mihsathe Jul 4 '11 at 14:28
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}$ –  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
show 5 more comments

5 Answers

up vote 2 down vote accepted

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

share|improve this answer
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. –  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
add comment

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

share|improve this answer
    
@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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.