Find the remainder when 111203 is divided by 13
this is how i do such things: i get a calculator and check 111203/13 = 8554.0769230769230769230769230769
i don't care about the decimal part, i only want the integer part. this tells me that:
111203 = (111203) - (8554)(13) (mod 13).
now (8554)(13) = 111202, and 111203 - 11202 = 1, so:
11203 = 1 (mod 13)
if you don't have access to a calculator while doing this, you can do it this way:
111203 < 13000 = 13*10000 and
111203 > 1300 = 13*1000.
so let's find the largest "n" with 13*n*1000 < 111203.
we guess 5 first: 13*5000 = 65000, so n is at least 5
we guess 7 or 8, next: let's guess 7: 13*7000 = 91000, so n is at least 7
let's say we not sure if it's 7,8,or 9, and we guess 8: 13*8000 = 104000, so n is at least 8.
now we know n is 8 or 9, let's check 9: 13*9000 = 117000, so 9 is too big. thus n = 8.
so 111203 = 111203 - 104000 (mod 13) that is:
11203 = 7203 (mod 13) <--7203 is a LOT smaller than 11203.
we do the same thing as before, except now we're looking for 13*n*100 < 7203.
6500 < 7203, so n is at least 5.
9100 > 7203, so n is at most 6.
7800 > 7203, so n = 5.
so 111203 = 7203 = 7203 - 6500 = 703 (mod 13) <---703 is again a LOT smaller than 7203.
again, looking for an n with 13*n*10 < 703
650 < 703
780 > 703, so n = 5.
so 111203 = 7203 = 703 = 703 - 650 = 53 (mod 13) <--again, this is getting nice and small.
now by inspection, we see: 13*4 = 52 < 53 < 65 = 13*5, so:
53 = 53 - 52 = 1 (mod 13), and since 0 ≤ 1 < 13, we are done.
this is just like long division, but we only "keep the remainders" (once we find the n's, we discard them, because we don't need them anymore).