How do i find remainders ..(maths) ?

Question

How do i find remainders of numbers to big powers .

eg . 2^1993

(two to the power of one thousand and ninety three )

and then when i divide that by something like 7 ?

or ..

27^1001 divided by 13

or 38^101 divided by 13 ?

thanks :)

Answer 1

yeas

just use mod

Answer 2

You use what is called modular arithmetic.

It is based on the fact that in such calculations

the remainders cycle through a pattern.

Also  m^n (mod k)  [ remainder when m^n is divided by k]

is the same as (m mod k)^n [ remainder when m itself is divided by k,

raised to the power n ].  We'll use that below.

2^1993 (mod 7)

You take the first few powers and reduce them (mod 7)

until they start repeating.

2^0 = 1 (mod 7)

2^1 = 2 (mod 7)

2^2 = 4 (mod 7)

2^3 = 8 = 1 (mod 7)

2^4 = 16 = 2 (mod 7)

2^5 = 32 = 4 (mod 7)

We're in luck: it repeated very quickly.

Every third power will have remainder of 1 (mod 7).

(We could see that as soon as 1 popped up again.)

Now we look at remainder of 1993 when divided by 3

(since remainders mod 7 repeate every THREE times).

1993 = 3 * 664 + 1, so we look at remainder of 2^1,

which is 2, so 2^1993 will have remainder 2 when divided by 7.

You can check this out for lower powers.

For example, 2^9 = 512.

512 = 7 * 73 + ... ta da ... 1 (since 9 is a multiple of 3).

2^10 = 1024 = 7 * 146 + ... 2

2^11 = 2048 = 7 * 292 + .... 4

Same cycle of 3 different remainders.

The other problems are even simpler:

27^any power ...

27 = 2 * 13 + 1

27 = 1 (mod 13), so it is the same as 1^any power = 1 (mod 13).

38^101

38 (mod 13) is 12 or more conveniently -1.

The powers of -1 are: -1, 1, -1, 1, -1, 1, ... etc.

Since 101 is odd, the remainder will be -1 or rather 12.

=