Number System Practice Gym by Anubhav Sehgal  Part 7

Find (7^21 + 7^22 + 7^23 + 7^24) mod 25.
7^21(1 + 7 + 49 + 343) mod 25
(7^21 * 400) mod 25
0 since 400 is divisible by 25.
[N = N1 * N2*…, then N mod x = N1 mod x * N2 mod x * … i.e. Remainders are multiplicative]Find 17! mod 23.
We know that (p – 2)! Mod p = 1 for any prime p.
21! Mod 23 =1
21 * 20 * 19 * 18 * 17! Mod 23 = 1
(2) * (3) * (4) * (5) * 17! Mod 23 = 1
[21 mod 23 = 21 or 2; In general, k mod n = k or (k – n) when k < n]
120 * 17! Mod 23 = 1
5r mod 23 = 1
r = 14 as 70 mod 23 = 1.When a natural number is divided by 4 and 7, it gives remainder 3 and 2 respectively. What is the remainder obtained when same natural number is divided by 11?
N = 4a + 3 = 7b + 2
Let us first find the general form of such a number using Chinese remainder theorem
4a + 3 = 7b + 2
4a = 7b – 1
a = 4b/4 + (3b – 1)/4
a = b + (3b – 1)/4
Pick the value of b for which (3b – 1)/4 is an integer.
b = 3 => a = 3 + 2 = 5
Number in general form = Value at any particular a, b + k*LCM (Coefficients of a, b) where k is any integer.
N = 23 + 28k
N mod 11 = (23 + 28k) mod 11 = (1 + 6k) mod 11 = can’t be determined uniquely as it would depend on value of k.Find the remainder when 1^1995 + 2^1995 +....+ 1996^1995 is divided by 1997.
Rearranging the terms,
(1^1995 + 1996^1995) + (2^1995 + 1995^1995) + …. + (998^1995 + 999^1995) mod 1997
(a^n + b^n) mod (a + b) = 0 when n is odd.
Each of the brackets is divisible by 1997 and hence the overall remainder is zero.10^x mod 13 = 1 and 1 < = x < = 100. How many values of x satisfy the given equation?
We know that 1001 = 7 * 11 * 13
=> 10^3 mod 13 = 1
=> 10^6 mod 13 = 1
Now this cycle will repeat for every multiple of 6.
So, x = 6, 12, 18, 24, … , 96 => 16 values.
NOTE: Do not use Euler directly in such questions. Euler states that x ^ E (p) mod p = 1 but it doesn’t tell you that it is the least number for which cycle will repeat. Here E(13) = 12. But as you can see cycle starts repeating for every 6 only instead of every 12. If you use Euler directly, then you must check for each factor of Euler number to be sure if Euler is the least cycle repeat size.Find 123234345456567678789 mod 37.
10^3 mod 37 = 1.
So, we may form triplets and find individual remainders, adding them to give the overall remainder.
123 mod 37 = 12, 234 mod 37 = 12, .. , 789 mod 37 = 12
12 * 7 mod 37 = 84 mod 37 = 10 or 27Find 10111213141516171819 mod 33.
10^2 mod 33 = 1.
So, we may for pairs and find individual remainders, adding them all to give the overall remainder.
(10 + 11 + 12 + … + 19) mod 33
(10 + 155  20) mod 33 = 145
mod 33 = 13 or 20Find (13^3 + 14^3 + ... + 34^3) mod 35.
[34 * 35/2]^2 – [12 * 13/2]^2 mod 35
[35 * 17]^2 – [6 * 13]^2 mod 35 [Sum of first n cubes = [n(n + 1)/2]^2 ]
0 – 78^2 mod 35
0 – 8^2 mod 35
64 mod 35 = 29 or 6Find C (58, 29) mod 29.
C (2n, n) = C (n, 0)^2 + C (n, 1)^2 + … + C (n, n)^2
C (58, 29) = C (29, 0)^2 + ….. + C (29, 29)^2
Except the first and last terms, all terms will be divisible by 29. Hence the remainder will be:
C (29, 0)^2 + C (29, 29)^2 mod 29 = 1 + 1 mod 29 = 2Find 24^1202 mod 1446
1446 = 2 * 3 * 241
When we cancel out some common term from dividend and divisor, we need to multiply it back in the end.
24^1202 = (2^3 * 3)^1202 = 2^3606 * 3^1202
2^3605 * 3^1202 mod 3*241Use Chinese remainder theorem now,
N = 2^3605 * 3^1202 N mod 3 = 0
E(241) = 240
N mod 241 = 2^3605 * 3^1202 mod 241 = (2^5 * (2^240)^15) * (3^2 * (3^240)^5) mod 241
[Taking out powers in multiple of Euler number, as they would leave remainder as 1 with 241.]
N mod 241 = 2^5 * 3^2 mod 241 = 47
3a = 241b + 47
a = (240b + 45)/3 + (b + 2)/3
a = 80b + 15 + (b + 2)/3
b = 1, a = 96
Remainder = 288
Final remainder = 288*2 = 576 [ Remember we needed to multiply the 2 canceled out earlier back]Alternate approach
We know that for a prime p, N^(p – 1) mod p = 1 ; By extension of Euler theorem which is also called Fermat’s remainder theorem. That is to say, Cyclicity of obtaining remainder 1 is E (p).
Extending that logic, 1446 = 2 * 3 * 241
Cyclicity of 1446 = LCM (E (2), E (3), E (241)) = LCM (1, 2, 240) = 240
24^1202 mod 1446 = (24^240)^5 * 24^2 mod 1446 = 1 * 576 mod 1446 = 576

awesome work sir......