Divisibility and Remainder

[tellmesomething]

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?

 

[Hill]

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?"

 

[tellmesomething]

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.

 

[PeroK]

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.

 

[Hill]

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.

 

[Frabjous]

$(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 bⁿ. All of the other terms are divisible by 13 with zero remainder because they are multiples of a.
You need b=±1 for bⁿ to be trivial to calculate.
if 5bⁿ=5, the remainder is 5
if 5bⁿ=-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.

 

[WWGD]

Notice $8^2=64=65-1$ And $65=13(5)$. Thus $8^4, 8^8,..8^{4k}$=...

 

[GLD223]

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$ | 5¹
$5^2 \equiv 12$ | 5¹⁰

$12 * 5 \equiv 8$ | 5¹¹

$8^2 \equiv 12$ | 5¹¹⁰

$12^2 \equiv 1$ | 5¹¹⁰⁰

$1^2 \equiv 1$ | 5¹¹⁰⁰⁰

$1^2 \equiv 1$ | 5¹¹⁰⁰⁰⁰

$1*5 \equiv 5$ | 5¹¹⁰⁰⁰¹

$5^2 \equiv 12$ | 5^1100010

$12*5 \equiv 8$ | 5^1100011
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 5⁹⁹ is divided by 13?"

Is equivalent to: 5⁹⁹ $mod13 \equiv 8$