A question

What is the remainder when 17^19 is divided by 9

We will use ^ for "raise to the power" through out.

Now by long didvision it will take some time and really it is hopeless.

Let us try this by modulo arithmetic.


Let us translate this in a equation


17^19 = something (mod 9)

Now this something and 17^19 leave same remainder on division by 9 so we try to find this something in lowest term possible.
As if we find this something we will also know what remainder 17^19 leaves on division by 9


Now let us get going

Let us say we start with 17

now 17 = x (mod 9)

Now x can take lots of values but we try to find the lowest one

we find that 17 = 8 (mod 9) .............................we wil need this later so let me mark this as (equation 1)

as 17 leaves 8 when divided 9

so we have 17=8 (mod 9)

Now let us try to find 17^2 = y (mod 9)

Now here the trick starts

i turns out you can write 17*17 =y (mod 9)

Now in modulo arithmetic you can substitute each of the 17 with a number that is equal to it.

Now we found 8=17 so we write it as
We merely write 8 for each 17

8*8 =y (mod 9)
64=y (mod 9)
now we know 64 = 1 (mod 9)
divide 64 by 9 and you get remainder 1 that's why.


Now we odn't need to go nay further

let s return to original equation 17^19 = something (mod 9)

Now 17^19 is just a row of 17's nineteen times.

Now we found 17=8 (mod 9)
and 17^2=1 (mod 9)
this means 17^4 =1 (mod 9) as 17^4=(17^2)*(17^2)
and we can substitute 1 for each of 17^2 .....right
Infact for any power of 2 we can have 17^(power of 2) =1 (mod 9) ....convince yourselves

Now try to substitute these two values in the original equation.

note that we can write 17^19 as (17^16)*(17^3)=(17^16)(17^2)(17)=(1)(1)(8)=8

So we have 17^19=8 (mod 9)

and 8 is the required remainder.


try to follow each step you can do it very quicly if you get the hang of it.





Let us see what I did once again.

17^(19)= some number (mod 9)
we try to RHS as small as possible
we found 17= 8 (mod 9)
17^2 =17*17 =8*8 (mod 9)
8*8 =64 =1 (mod 9)
so 17^2 =1 (mod 9)

Note that this mod 9 is really not necessary if it is understood what modulo we are working with so you can drop it.


similarly 17^4 =(17^2)*(17^2) =1*1 =1 (mod 9)

similarly 17^8=(17^4)(17^4)=1*1=1 (mod 9)

similarly 17^16 =1 (mod 9) and so on

17^19 =17^ 16 * 17^2 * 17 =1* 1 * 8 =8 (mod 9)


try some examples from printouts I gave you.

Now let us go to some more rules

I will state only two of them for now

if we have a=b (mod x)
and c=d (mod x)

then ac=bd (mod x) i,e you can multiply

and a+c=b+d (mod x) i,e you can add


for division you need to follow one rule i,e divisor must be relatively prime to the modulo


so a=b (mod x)=> a/k =b/k (mod x) provided k doesn't divide x.I will explain this why this happens.


Got it.


Now I can explain why we are able to substitute numbers by there equivalents.


say 17=8 (mod 9) ....1

17=8 (mod 9) ....2

So we can multiply these two identical equations to get 17*17 =8*8 (mod 9)

So when we have 17*17 we can always substitute it by 8*8 as both are equal

Similarly if you have 17+17 you can always substitute it by 8+8


So final conclusion you can substitute any number connected by multiplication or addition operators.


Got it...