Why Does Expanding (13-8)^99 Not Yield the Same Remainder as 5^99 Modulo 13?

  • Thread starter Thread starter tellmesomething
  • Start date Start date
  • Tags Tags
    Binomial theorem
AI Thread Summary
Expanding (13-8)^99 does not yield the same remainder as 5^99 modulo 13 because it leads to a different interpretation of the problem, specifically focusing on the term (-8)^99. The correct approach involves recognizing that 5 is congruent to -8 modulo 13, which simplifies calculations. When using the Binomial theorem, only the last term remains relevant for finding the remainder, as all other terms are multiples of 13. The remainder is ultimately determined to be 8, as derived from the calculations involving powers of 5 modulo 13. Understanding the relationship between negative remainders and their positive counterparts is crucial in these calculations.
tellmesomething
Messages
436
Reaction score
66
Homework Statement
What is the remainder when 5^99 is divided by 13?
Relevant Equations
!!
The book solution is to first take one 5 out
5(5^98)= 5(25^49)=5(26-1)^49
And then when we expand it using Binomial theorem we get a number which isnt a multiple of 13, we get -5 as the remainder. But since remainders have to be positive we add 13 to it (this i generalised by dividing numbers with divisors which generate a negative remainder and then added the divisor to get the "correct remainder", i dont know exactly why this works)

But can i not write 5^99 as (13-8)^99 and expand it and expect the same answer? After expanding it the only number which doesnt have a multiple of 13 in it is the last term which is = (-8)^99 which is very far from the remainder, why's that?
 
Physics news on Phys.org
It appears that you have replaced the question "What is the remainder when 5^99 is divided by 13?" by the question "What is the remainder when (-8)^99 is divided by 13?"
 
Hill said:
It appears that you have replaced the question "What is the remainder when 5^99 is divided by 13?" by the question "What is the remainder when (-8)^99 is divided by 13?
Can you explain what you mean by that all im saying is im getting -8^99 as the remainder when im writing 5^99 in the form of (13-8) ^99? Do you mean i should also check if (-8)^99 is divisible by 13 or not? By perhaps expanding it as -1*8*(64)^49=-1*8*(65-1)^49 ah i think i finally get 8 here as the remainder.
 
tellmesomething said:
Can you explain what you mean by that all im saying is im getting -8^99 as the remainder when im writing 5^99 in the form of (13-8) ^99? Do you mean i should also check if (-8)^99 is divisible by 13 or not? By perhaps expanding it as -1*8*(64)^49=-1*8*(65-1)^49 ah i think i finally get 8 here as the remainder.
Note that ##5 = -8## modulo 13.

A quicker way is to note that ##5^2 = -1## modulo 13. Hence ##5^{98} = (-1)^{49} = -1## modulo 13. Hence ##5^{99} = -5 =8## modulo 13.
 
tellmesomething said:
all im saying is im getting 8^99 as the remainder
8^99 is not a remainder. Remainder should be smaller than a divisor, but 8^99 is certainly greater than 13. You're not getting 8^99 as a remainder - you're getting it as a term to be divided.
 
##(a+b)^n=\sum_{i=0}^n c_i a^i b^{n-i}##
if a is divisible by 13, the only term that one needs to look at is bn. All of the other terms are divisible by 13 with zero remainder because they are multiples of a.
You need b=±1 for bn to be trivial to calculate.
if 5bn=5, the remainder is 5
if 5bn=-5 you ”divided” by 13 one too many times so you need to add one 13 back to get a remainder of 8. When you dealing with remainders, you are essential subtracting 13 from the original number multiple times. If you get a negative number, you have subtracted too many.
 
Last edited:
Notice ##8^2=64=65-1## And ##65=13(5)##. Thus ##8^4, 8^8,..8^{4k}##=...
 
  • Like
Likes Khi Choy Xichdu
There is a neat algorithm to calculate this. It's called "square & multiply". Here is a link to a video that explains it:"".
This is how I would apply the algorithm on your specific question:
##99 = 1100011_2##
start with ##5^1 \equiv 5## | 51
##5^2 \equiv 12## | 510

##12 * 5 \equiv 8## | 511

##8^2 \equiv 12## | 5110

##12^2 \equiv 1## | 51100

##1^2 \equiv 1## | 511000

##1^2 \equiv 1## | 5110000

##1*5 \equiv 5## | 5110001

##5^2 \equiv 12## | 51100010

##12*5 \equiv 8## | 51100011
I omitted the "mod 13" above just for simplicity but all the above equations should have mod 13 in them.

Therefore the answer to your question "What is the remainder when 599 is divided by 13?"

Is equivalent to: 599 ##mod13 \equiv 8##
 
Back
Top