Good Set of Problems in Number Theory (Solved)

Credits  Rajendra Rajput
What is the least multiple of 7, which when divided by 2, 3, 4, 5 and 6 leaves the remainders 1, 2, 3, 4 and 5 respectively?
N/2 = 1 or 1
N/3 = 2 or 1
N/4 = 3 or 1
N/5 = 4 or 1
N/6 = 5 or 1
you can see that 1 is constant
Formula to find number
N = LCM of (2,3,4,5,6) k + constant
N = 60k 1Now
60k1 / 7 should be divisible
To find K lets simplify it more and make remainder 0
4k1/7
Now obviously k should be 2 to make it perfectly divisible
4 (2)1/7
= 0 remWe Found K = 2
Put it in that number
N = 60k  1
N = 60 (2)  1
N = 119What is the remainder when (2^100+3^100+4^100 5^100) is divided by 7?
2^100 + 3^100 + 4^100 + 5^100/7
= (2^3)^33 * 2 + (3^3)^33 * 3 + (4^3)^33 * 3 + (5^3)^33 * 3 / 7
= 2 * 8^33 + 3 * 27^33 + 4 * 64^33 + 5 * 125^33 / 7
= 2 * 1^33 + 3 * 1^33 + 4 * 1^33 + 5 * 1^33 / 7
= 2 * 1 + 3 * 1 + 4 * 1 + 5 * 1 / 7
= 2  3 + 4 5 / 7
= 2/7
= 72
= 5 remainderIf a number is divided by 14 and the remainder is 5, then if the same number is divided by 7, what is the remainder?
N/14 = 5 remainder
N could be 19, 33, 47,....
Least number is 19
So 19/7 = 5 remainderOr
N = 14k + 5
Now
N/7
14k+5/7
0*k+5/7
5/7
5 remainderFind the remainder when 17^53 is divided by 27
Euler of 27 = 18
So Euler says
17^18/27 = 1 remainder
17^36/27 = 1
.
Similarly 17^54/27 = 1
17^53 * 17 /27 = 1
R * 17 = 27k+1
R = 27k+1/17
Let K be any number which perfectly divides the equation
R = 27 (5)+1/17
R = 8 remainderFind the remainder when 5^100000 is divided by 196
5^100000/196
= 5^100000/ 4*49Lets divide it separately
5^100000/4
= 1^100000/4
= 1 remainder5^100000/49
Euler of 49 = 49 (1  1/7) = 49 (6/7) = 42
Euler says
5^42/49 = 1 remainder
5^84/49 = also 1Same way
5^100002/49 = 1
5^100000 * 5^2/49 = 1
R*25 = 49k+1
R = 49k+1/25
Let k be any lesser value which perfectly divides the equation
Let k be 1
R = 50/25 = 2 remainderSo our answer is that number which leaves remainder 1 when divided by 4 & remainder 2 when divided by 49
Apply Chinese remainder theorem and get your answerAnswer is 149
Find the remainder when 2017^22 is divided by 23
Fermat thereom says that
When a and p are coprime to each other
a^(p1)/p = 1 remainder
Where, p is a prime number
Here 23 is prime
So
2017^22/23
= 1 remainderWhat is the unit digit of 123^4567! * 765^4321?
123^4567! * 765^4321
We have to find unit digit so we are concerned of unit digit only
3^4567! * 5^4321
(3^4)^(4567!/4) * 5^4321
(xxxx1)^(4567!/4) * 5^4321
[ Note : 1^n = 1 unit and 5^n = 5 unit]
1^(4567!/4) * 5^4321
= 1 * 5
= 5 unit digitWhat is the remainder when (49^15  1) is divided by 14?
49^15  1/14
= (7^2)^15  1/14
= 7^30  1/14
[ Note : 7^n/14 = 7 remainder ]
= 71/14
= 6/14
= 6 remainderWhat is the remainder when 2000^2001 is divided by 26?
2000^2001/26
24^2001/26
26 = 13*2Divide separately
24^2001/13
2^2001/13
2 * 2^2000/13
2 * (2^6)^333 * 2^2/13
8 * 64^333/13
8 * 1^333/13
(1 ^odd =  1 )
8*1/13
8/13
8 remainder24^2001/2
= 0 remainderSo our answer is that number which leaves remainder 8 when divided by 12 & remainder 0 when divided by 2
N/13 = 8
N could be 8, 21, 29,...N/ 2 = 0
N could be 0,2,4,6,8,...The very first number common in both term is 8
So final remainder is 8
Answer 8
Or
24^2001/26
2^2001/26
Eulee of 26 is 12
(2^12)^166 * 2^9/26
1 * 2^9/26
512/26
18/26
2618
8 remainderWhen 3n is divided by 7, the remainder is 4. what is the remainder when 2n is divided by 7?
3n/7 = 4
3N could be 4, 11, 18..
First multiple of 3 here is 18
3n = 18
N = 6Now
2n/7
= 2 (6)/7
= 12/7
= 5 remainderFind the remainder when 1^5 + 2^5 + 3^5 +.......+ 100^5 is divided by 4
Every even no. here is perfectly divisible by 4
Our question shorts to
1^5 +3^5 +5^5 +.....+99^5/4Euler of 4 = 2^2
4 (1  1/2) = 4 (1/2) = 2
so euler says
a^2/4 = 0 rem
a^4/4 = 0 rem
.
Where "a" and 4 are coprime to each otherOur question again shorts to
1+3+5+....99/4
Sum of odd natural number/4
= n^2/4
[ Where N is the term, Here N is 50th term ]
= 50^2/4
= 2500/4
= 0 remainderWhat is the remainder of 10! + 1111111…99times when divided by 1331?
10! + 11111....(99 times)/1331
Find remainder separately
10!/1331
= 494 remainder > (1)1111.... (99 times)/1331
I found this pattern for every odd N > 3
Remainder of [10(n1/2)^2 + (n1/2)(n3/2)]/121 * 11 + 1
So if question is
11111/1331 here N is 5
R of [10 (51/2)^2+(2)(1)]/121 *11 +1
= R of [10 (2^2)+2]/121 *11+1
= [42] 11+1 = 463If 1111111/1331
N is 7
= R of [10 (3^2)+(3)(2)]/121 * 11+1
= [96]11 +1 = 1057Similarly in this question
N is 99
= R of [10 (49^2)+(49)(48)]/121 * 11+1
= R of [10 (2401)+2352]/121 *11+1
= R of [10 (102)+53]/121 *11+1
= R of [1073/121] * 11+1
= [105] 11+1
= 1156 remainder >(2)So now merge it again
10! + 111... (99 times)/1331
= 494 + 1156/1331
= 1650/1331
= 319 > final remainderAnswer is 319
What will be the remainder when(1234567890123456789)^24 is divided by 6561?
Remainder of Ka/Kb
= K * rem of (a/b)(1234567890123456789)^24/6561
= (9K)^24 / 9^4
= (9^24 * K^24) / 9^4
= 9^4 * rem of (9^20 * K^24 / 0)
= 9^4 * 0
= 0 remainderHow many numbers between 100 and 200 (including both 100 and 200), are not divisible by any of these numbers: 2, 3 and 5?
Euler of 2 * 3 * 5
= (1 1/2)(1  1/3)(1  1/5)
= (1/2)(2/3)(4/5)
= 4/15Number not divisible :
Between 1100
100 (4/15)
= 26Between 1195
= 195 (4/15)
= 52So from 1195
5226 = 26Between 196200 only 2 number is not divisible I.e 197 & 199
Total number
= 26+2
= 28 <  answerWhat is the greatest 4 digit no when divided by 10,11,15 & 22 leaves 3,4,8 & 15 as remainders respectively?
N/10 = 3 or 7
N/11 = 4 or 7
N/15 = 8 or 7
N/22 = 15 or 7
Format is
Lcm of ( 10,11,15,22 ) k + constant
= 330k7
If we put k as 1 then we will get least no.
=330 (1)7
= 323 is the least no. Which satisfy above condition
But we want highest 4 digit no.
So hit and trial method
Let k be 30
= 330 (30)7
= 9893
But if we take k as 31 it will give 5 digit no. But we want highest 4 digit no.
So ans is 9893What is the remainder if 13571357… (upto 1000 digits) is divided by 101?
1357/101 = 44 remainder
13571357/101 = 44 * 2 = 88 remainder
135713571357/101 = 44 * 3 = 132/101 = 31 remainder
so make block of 4 number I.e (1357)
It will give 44 as remainder
Here 1000/4 = 250 such blocks
So 44 * 250/101
= 44 * 48/101
= 92 remainderWhat is the remainder when 987987987… (123 digits) is divided by 1001?
987987987.... (123digit)/1001
Remember
987987/1001 = 0 remainder
Because
987987/1001 can be written as
987*1001/1001 = 0 remainder
So 987987 I.e make a block of 6 digit and that will perfectly divided by 1001
Here 123/6 = 20 such block but remain 3 digit I.e 987
So our question shorts to
987/1001
= 987 remainderIf the LCM of two natural numbers is 300, how many sets of A and B are possible?
Lcm (a, b) = 300 = 2^2 * 3* 5^2
Let us think from the perspective of each prime.
First of all, both ‘a’ and ‘b’ must be factors of 2^2
So we have 3 possibilities of both ‘a’ and ‘b’. Hence 3^2 possibilities.
But from these possibilities we must remove those cases where ‘a’ and ‘b’ are neither 2^2. This will happen when both ‘a’ and ‘b’ are factors of 2^1.
So that 2^2 cases must be removed.
So we have (3^2  2^2) cases where lcm will be 2^2Similarly for 3^1 case
We will have (2^2  1^2)Similarly for 5^2 case
We will have (3^2  2^2)Total ordered cases
= (3^2  2^2)(2^2  1^2)(3^2  2^2)
= 5 * 3 * 5
= 75 casesIn order to convert to unordered solution, we must first understand that except for the case (300,300) all cases have been counted twice.
So, the number of unordered solutions will be (75+1)/2
= 38 casesIn a list of 200 numbers, each number after the first is 4 more than the number that comes before it. What is the difference between the first and the last number on the list?
T1 = a
T2 = a+4
T3 = a+8
T4 = a+12
.
.
If you observe clearly you will see difference from 1st term follows:
Difference = (Tn 1) 4
= (2001) 4
= 796What is the remainder when 47^37^27 is divided by 11?
47^37^27/11
Euler of prime P is (P1)
Euler of 11 is 10
Power/euler
37^27/10
= 7^27/10
= (7^2)^13 * 7/10
= 49^13 * 7/10
= (1)^13 * 7/10
[ Note : 1^odd = 1 ]
= 1 * 7/10
= 7/10
= 107
= 3 remainderOur question shorts to
47^3/11
= 3^3/11
= 27/11
= 5 > final remainderLast two digit of 21^50  8?
21^50  8
Last two digit of (a1)^xxb
= last digit of (a * b) 1
= last digit of (2 * 0) 1
= xxxx01
= 01 > last two digit of 21^50
Now
Last two digit of 21^50  8
= xxx01  8
= 93