Verified answer

If you think of seven to its early powers you will see the mod: (remainder when divided by 6)

7/6 has R:1

49/6 has R:1

343/6 has R:1 and

2401/6 has R:1

7 to any power in mod 6 has a remainder of 1

Since 7 is 6 with a remainder of 1 we can treat 7^1000 mod 6 as 1^1000 mod 6 which is 1 divided by 6 which of course has remainder 1.

Similarly for 6^1001 mod 7, if we divide the early powers of 6 by 7 we see the pattern in the remainders.

6/7 has remainder 6

36/7 has remainder 1

216/7 has remainder 6

1296/7 has remainder 1

We see that 6 to an odd power divided by 7 has remainder 6

and 6 to an even power divided by 7 has remainder 1

so 6^1001 mod 7 being an odd power will have a remainder of 6.

We could say that 6 in mod 7 is -1

so -1^1001 mod7 = -1 mod 7....and since 7-1=6 the answer is 6.

In short

7^1000 mod 6 = 1^1000 mod 6 = 1 mod6 = 1

6^1001 mod 7 = (-1)^1001 mod 7 = -1 mod 7 = 7-1 = 6

The remainder of the products equals the remainder of the product of the remainders.

Examples

6 mod 5 = 1

8 mod 5 = 3

(6*8) mod 5 = (1*3) mod 5 = 3

11 mod 7 = 4

11*11 mod 7 = (4*4) mod 7 = 2

Now lets try the first one:

7 mod 6 = 1

7^1000 mod 6 = 1^1000 mod 6 = 1

The second one is more difficult:

6 mod 7 = 6

The above law results in the same expression.

6^1001 = 6^1001 mod 6

Let's write 6^1001 a different way:

6^1001 = (6^1000)*6 = (36^500)*6 mod 6

36 mod 7 = 1

36^500 mod 7 = 1^500 mod 7 = 1

(36^500)*6 = (1*6) mod 7 = 6

7^1000 mod 6 = 1^1000 mod 6 = 1.

6^1001 mod 7 =(-1)^1001 mod 7 = -1 = 6.

7^1000 mod 6 is 7 mod 6 done a 1000 times or 1 * 1000 =1

and so forth.