number theory
posted by john on .
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.