Number System Practice Gym by Anubhav Sehgal (NMIMS, Mumbai)  Part 8

When a natural number M is divided by 4 and 7, it gives remainder 3 and 2 respectively. Even when another natural number N is divided by 4 and 7, it also gives remainder 3 and 2 respectively. There is no other number in between M and N exhibiting these properties. P is a natural number that gives the same remainder after dividing each of M and N. How many values of P are possible?
4a + 3 = 7b + 2 M = 23 + 28x
Similarly, N = 23 + 28y
Now remainder of M or N with any number P would be same for the constant term 23. It will vary depending on value of the variable term 28x or 28y.
Since, it is given that the remainder is same for both M and N, this is possible only when P is factor of 28 and remainder becomes independent of x and y.
So P = {1, 2, 4, 7, 14, 28 } = 6 valuesFind the remainder when [102010! / (51005!^2)] is divided by 101.
This is an application of a new concept called Lucas theorem.
Lucas theorem is usually used to find remainders when large binomial coefficients are involved.
If you note here, 102010! / 51005!^2 is nothing but C (102010, 51005) only.
It is applicable only for taking remainder with primes.
Consider C (x, y) mod p where x = a1 * p^n + a2 * p^(n – 1) + … + an and y = b1 * p^n + b2 * p^(n  1) + … + bn
Then, C (x, y) mod p = C (a1, b1) * C (a2, b2) * .. * C (an, bn)
Here,
102010 = 10 * 101^2 + 0 * 101 + 0
51005 = 5 * 101^2 + 0 * 101 + 0
C (102010, 51005) mod 101 = C (10,5) = 252If f (x) = x^3 + x^2 + 2x – 1 is divided by (x + 2) gives remainder r and quotient q (x). Then, find the value of q (2) + r.
Remainder when f (x) is divided by (x – a) = f (a).
r = f (2) = 8 + 4 – 4 – 1 = 9
q (x) = x^2 – x + 4 => q (2) = 4 – 2 + 4 = 6
q (2) + r = 3Find remainder when 987987987… (123 digits) is divided by 1001.
1001 = 10^3 + 1
So, we may for triplets from right to left and take alternative signs + and –ve moving from right to left.
123 digits means 41 triplets of three digits 987 each.
When we take alternating sums from right to left, we will get,
[(987 – 987) + (987 – 987) + … 20 such brackets] + 987 mod 1001 = 987.Find the smallest whole number that when divided by 5, 7, 9 and 11 gives remainders of 1, 2, 3 and 4 respectively.
Note here that 5 – 1 is not equal to 7 – 2 is not equal to 9 – 3 is not equal to 11 – 4.
So you cannot apply LCM (5, 7, 9, 11) – N where N is the constant difference.
N = 5a + 1
N = 7b + 2
N = 9c + 3
N = 11d + 4Multiply each by 2 so that remainders also count by a gap of 2 like the divisors are doing.
2N = 5(2a) + 2
2N = 7(2b) + 4
2N = 9(2c) + 6
2N = 11(2d) + 8Now divisors and remainders share a common difference of 3. Designating them as new variables
M = 5l + 2 = 7m + 4 = 9n + 6 = 11o + 8
Least M = LCM (5, 7, 9, 11) – 3
Least N = [LCM (5, 7, 9, 11) – 3]/2 = 1731 since M = 2N.Seeing the procedure you can now directly solve such questions in one line.
Take LCM of divisors. Subtract the would be common remainder after you have figured out the number to multiply with to make the count of divisors and remainders of the same step.
[Here Count of divisors was of 2 : 5, 7, 9, 11 and remainders was of 1. So we multiplied by 2/1 = 2]Another example : Divisors are 5,8,11 ; Remainders are 3,5,7. Multiplier = 3/2. See common remainder and then, Answer : [LCM(5,8,11) – 0.5]/(3/2) = 440 – 0.5/ (1.5) = 439.5/1.5 = 879/3 = 293
NOTE : General form of number will be = Smallest number + k * LCM(Divisors). You may be asked to find the kth smallest number or some other variant. So you may add multiples of LCM to the smallest number to get the required answer.
Find the remainder when 3^45 is divided by 125.
The usual and the longer approach
3^5 = 243. 243 mod 125 = 118 or 7
3^45 mod 125 = (7)^9 mod 125
Now, 7^4 mod 125 = 2401 mod 125 = 26 [ You basically try to break it into powers which leave a smaller remainder with our divisor to make our calculations manageable. That’s why we didn’t take 7^2 =49, 7^3 = 343.]
(7)^4 * (7)^4 * (7) mod 125
= 26 * 26 * 7 mod 125
= 676 * 7 mod 125
= 51 * 7 mod 125
= 357 mod 125
= 18 or 107.Smart approach [Will come from practice only]
Your first instinct here could have been to use Euler. But when you notice E(125) = 100 and you are not getting near that power with multiples of 45, you decided to drop the idea. Some reverse engineering is being done here so note carefully the approach.
3^45 mod 125 is to be found
128 mod 125 = 3.
So can we write 3^45 mod 125 = 128^45 mod 125? Sure we can but who thinks of going the other way round.
What this does for us?
128 = 2^7 thankfully and we get,
3^45 mod 125
= (2^7)^45 mod 125
= 2^315 mod 125
= 2^15 mod 125
= 2^7 * 2^7 * 2 mod 125
= 3 * 3 * 2 = 18.
That simple by just going the other way round. A little out of the box thinkingFind the remainder when 2^2014 + 7 * 5^4020 is divided by 23.
E(23) = 22
2014 mod 22 = 12
4020 mod 22 = 16
2^12 + 7 * 5^16 mod 23
64 * 64 + 7 * 25^8 mod 23
5 * 5 + 7 * 2^8 mod 23
25 + 7 * 256 mod 23
= 25 + 21 mod 23
= 0Find the remainder when 77777 … 70 times is divided by 37
We know that a digit or set of digits repeated (p – 1) times is divisible by p.
77777 … 36k times mod 37 = 0
Writing our number in extended form, (77777 … 70 times) * 10^2 + 77 mod 37 = 0
[This is nothing but 77777… 72 times ]
100r + 3 mod 37 = 0
26r mod 37 = 34
If you find difficulty in solving such equations for r, write it as the following and solve it like we do for a Chinese remainder theorem problem.
26r mod 37 = 34
=> 26r = 37k + 34
=> r = (26k + 26 + 11k + 8)/26
r = k + (11k + 8)/26
Find value of k such that (11k + 8)/26 is an integer.
Inside bracket values are 8, 19, 30, 41, [52]. Stop here as value is divisible by 26.
k = 4, => r = 4 + 52/26 = 6.Find the remainder when 25^25^25 is divided by 9.
25 and 9 are coprime.
E(9) = 9 * (1 – 1/3) = 6
25^25 mod 6
= 1^25 mod 6 = 1.
So we have, 25^1 mod 9 = 7.(18^2000 + 12^2000 – 5^2000  1) mod 221
(18^2000 – 5^2000) + (12^2000 – 1^2000) = B1 + B2
B1 and B2 both are divisible by 13 as (a^n – b^n) is divisible by (a – b) and (a + b) when n is even.
Also, (18^2000 – 1^2000) + (12^2000 – 5^2000) = B1 + B2
B1 and B2 both are divisible by 17 as (a^n – b^n) is divisible by (a – b) and (a + b) when n is even.
So the expression is divisible by 13 * 17 = 221.
Remainder will be zero.