Find the remainder when 1!+2!+...+299!+300! is divided by 21
a) Find the last two digits(units and tens digit) in 1829^(1829)
b) Find the units digit in 23^(7777)
To find large powers modulo some r, you can repeatedly square and/or multply numbers and reduce it modulo r at each step. E.g. if we do all coputations Mod 10 in the following, we can write:
1829 = -1
The 1829 th power of both sides is thus:
1829^1829 = (-1)^1829 = -1
Therefore the last digit of 1829^1829 is 9.
You can compute this Mod 100 using the Chinese Remainder Theorem, by ecaluating it separately Mod 25 and
Mod 4. Mod 4 you have:
1829 = 1, so
1829^1829 = 1
Mod 25 you have:
1829 = 4
Now 4^5 = 2^10 = 1024 = -1
So, 4^10 = 1 and thus
4^1829 = 4^9 = 4^(-1)
4*6 = 24 = -1, so the inverse of 4 is -6 = 19
We thus have that:
1829^1829 = 1 Mod 4
1829^1829 = -6 Mod 25
We can then write down the answer Mod 100 as follows. If we denote the inverse of x mod y is denoted as
[x^(-1)]_y, we can write down the solution as:
1 * 25 * [25^(-1)]_4 +
(-6) * 4 * [4^(-1)]_25
Modulo 25 the first term is zero as it is multiple of 25, ad the second term is -6 as the 4 and the inverse of 4 mod 25 cancel. Modulo 4 the last term is zero as that isnow a multiple of 4 while the first term is 1 as 25 times the inverse of 25 mod 4 now cancel.
We have:
1 * 25 * [25^(-1)]_4 = 25
(-6) * 4 * [4^(-1)]_25 = (-6)*4*(-6) = 24*6 = 44
Note that in these computations we can reduce Mod 100.
So, 1829^1829 Mod 100 = 25 + 44 = 69
23^(7777) Mod 10 =
3^7777 Mod 10
Mod 10 we have:
3^2 = 9 = -1 --->
3^4 = 1
7776 is a multiple of 4, so
3^7777 = 3
The last digit of 23^7777 is thus 3.
To find the remainder when the sum 1! + 2! + ... + 299! + 300! is divided by 21, we need to compute the sum and then find the remainder.
First, let's calculate the factorials of each number from 1 to 300:
1! = 1
2! = 2
3! = 6
4! = 24
...
299! = 29844592
300! = 300!
To simplify the calculation, we can observe that 21 divides evenly into any number greater than or equal to 21. Therefore, for any 21 consecutive numbers, the sum of their factorials will be a multiple of 21.
Since we have 300 numbers, we can group them into 14 sets of 21 numbers. Each set will contribute a multiple of 21 to the sum.
So, if we ignore the remainder while calculating the sum of factorials, we can simplify the calculation by removing all the multiples of 21:
1! + 2! + ... + 23! + 24! + 25! + ... + 45! + 46! + ... + 299! + 300!
The sum of factorials within each group of 21 numbers is a multiple of 21, so we are left with:
24! + 25! + ... + 45!
Now we can calculate the sum of these factorials:
sum = 24! + 25! + ... + 45!
= 620448401733239439360000 + 884176199373970195454361600000 + ... + 265827157478844876804362581890621647976960000000
= 620448401733239439360000 + (21 * some number) + (21 * some number) + ... + (21 * some number)
= 620448401733239439360000 + 21 * (some number + some number + ... + some number)
= 620448401733239439360000 + 21 * (multiple of 21)
Since 21 * (multiple of 21) will always be a multiple of 21, we can ignore that term when considering the remainder.
Therefore, the remainder when the sum of 1! + 2! + ... + 299! + 300! is divided by 21 is given by the remainder of:
620448401733239439360000 divided by 21
We can calculate this using modular arithmetic:
remainder = 620448401733239439360000 % 21 = 18
Hence, the remainder is 18.