Thread: remainder

Find the remainder when 111203 is divided by 13

Hey franios.

You can do this quickly on a computer but do you have to do this using specific techniques?

yes i believe we have to do it using mods

Do you know how to do long division with regular numbers?

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).