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

  • #1
tellmesomething
263
24
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
  • #2
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?"
 
  • Like
Likes scottdave
  • #3
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.
 
  • #4
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.
 
  • Love
Likes Delta2
  • #5
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.
 
  • #6
##(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:
  • #7
Notice ##8^2=64=65-1## And ##65=13(5)##. Thus ##8^4, 8^8,..8^{4k}##=...
 
  • Like
Likes Khi Choy Xichdu
  • #8
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##
 

Similar threads

Replies
5
Views
2K
Replies
11
Views
698
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Math Proof Training and Practice
Replies
25
Views
2K
  • Math Proof Training and Practice
2
Replies
51
Views
8K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Math Proof Training and Practice
2
Replies
67
Views
8K
  • Math Proof Training and Practice
3
Replies
77
Views
12K
Back
Top