Posts

practice problems pending CRT homework

Image
Q1. Let n be the least positive integer greater than 1000 for which gcd(63,n+120) = 21 and gcd(n+63,120) = 60. What is the sum of digits of n? S1. First wrong attempt: n = 21p - 120 = 60q - 63 => q = (7p - 19)/20 p = 17 works between p = 1 to 20. So p = 17 mod 20. p = 17,37,57,77,97... 21p - 120 >= 1000 => p>=880/21 => p = 57 => q = 19 n = 21*57-120 = 1077 sum_digits(n) = 15 Why is this wrong? gcd(63, 1077 + 120) = 63 not 21. gcd(63, n + 120) = 21 means that gcd(63/21,(n+120)/21) = 1 gcd(3,p) = 1 => p can't be a multiple of 3 but we chose 57. Similarly: gcd(n+63,120) = 60 => gcd((n+63)/60,2) = 1 => gcd(q,2) = 1 => q is odd. So coming back to: q = (7p - 19)/20 for p = 77, q = (77*7 - 19)/20 = 26 but q has to be odd. for p = 97, q = (97*7 - 19)/20 = (630 + 49 - 19)/20 = 660/20 = 33. It works. So, n = 60*33 - 63 = 1980 - 63 = 1917 sum_digits(n) = 18 Q2. Prove that 10^(3n+1) cannot be represented as a sum of 2 cubes(integers). S2. Typically when dealing wi...
Post a Comment
Read more

practice problems

Image
Q1. S1. First do angle chasing and get all angles. Now apply Sine rule in AMC. AC/sin(150) = MC/sin(7) sin(150) = sin(180-150) = sin(30) = 1/2 => AC = MC/2sin(7)___[1] In BMC: BC/sin(M) = MC/sin(97-M) BC = AC and sin(97-M) = sin(90 + 7 - M) = cos(7-M) = cos(M-7) => AC = MC.sin(M)/cos(M-7)  ____[2] Using [1] and [2]: 1/2sin(7) = sin(M)/cos(M-7) => 2sin(7)sin(M) = cos(M-7) = cosMcos7 + sinMsin7 sin7sinM = cos7cosM tan7 = cotM = tan(90-M) => M = 83 = answer Q2. S2. Isosceles triangle, altitude bisects the base. x^2 = h^2 + 225 y^2 = h^2 + 36 (x+y)(x-y) = 189 = 3^3*7 189 = 189 * 1 = 63 * 3 = 21 * 9 = 7 * 27 case 1: x+y = 189, x-y=1 => 2x = 190 => x = 95, y=94 => AD = CD = 95, perimeter = 190 + 30 = 220 case 2: x+y = 63, x-y=3 => 2x = 66 => x = 33, y=30 => AD = CD = 33, perimeter = 66 + 30 = 96 case 3: x+y = 21, x-y=9 => 2x = 30 => x = 15, y=6 => AD = CD = 15, invalid since AC = 30 case 4: x+y = 27, x-y=7 => 2x = 34 => x = 17, y=10 => AD =...
Post a Comment
Read more

practice problems pending concept class

Q1. Is there a solution to 5x = 3 mod 11? Yes. Why? Since 5,11 are co-prime we can always find 'x' s.t. 5.x = r mod 11 for all 'r' from 0 to 10. Q2. Simple way to solve x = 1 mod 3 x = 2 mod 5 x = 3k + 1 3k + 1 = 2 mod 5 3k = 1 mod 5 => k = 2 mod 5 => k = 5t + 2 => x = 3(5t + 2) + 1 = 15t + 7 = 7 mod 15 Similarly x = 0 mod 8 x = 59 mod 125 125p + 59 = 0 mod 8 5p + 3 = 0 mod 8 5p = 5 mod 8 p = 1 mod 8 So x = 125*1 + 59 = 184
Post a Comment
Read more

Euler's totient theorem(Euler-Fermat theorem)

Let phi(n) = totient function, i.e. number of integers upto 'n' which are co-prime to it. Then: a^(phi(n)) = 1 mod 'n' if 'a' and 'n' are co-prime. You can see the similarity with Fermat's little theorem: a^(p-1) = 1 mod 'p' where 'p' is a prime and 'a','p' are co-prime. As we know all integers upto 'p' are co-prime to it.
Post a Comment
Read more

calculus pending Newton's method

 newton's method
Post a Comment
Read more

practice problems

Q1. Does there exist an integer x satisfying the following conditions? 10x = 1 mod 21 5x = 2 mod 6 4x = 1 mod 7 S1. No. Why? [1] =>  10x = 1 mod 21 => 10x = 1 mod 3 and 10x = 1 mod 7 => x = 1 mod 3 and 3x = 1 mod 7 => 36x = 12 mod 7 => x = 5 mod 7 So we have x = 1 mod 3 and x = 5 mod 7 [2] =>  5x = 2 mod 6 => 5x = 6k + 2 => 5x = 2 mod 3 => 2x = 2 mod 3 => 4x = 4 mod 3 => x = 1 mod 3 And 5x = 0 mod 2 => x = 0 mod 2 So we have x = 1 mod 3 x = 5 mod 7 x = 0 mod 2 [3] => 4x = 1 mod 7 => 8x = 2 mod 7 => x = 2 mod 7 Which is a contradiction to existing solutions. Q2. For how many n between 1 and 2520 do we have n^3 = 1 mod 2520? S2. 2520 = 2^3 * 3^2 * 5 * 7 So n^3 = 1 mod 8 => n = 1 mod 8 n^3 = 1 mod 9 => n = 1,4,7 mod 9 n^3 = 1 mod 5 => n = 1 mod 5 n^3 = 1 mod 7 => n = 1,2,4 mod 7 For each of those options there is a unique solution (using CRT) between 1 and 2520. So total 9 valid solutions. Q3. Find positive integers a,b,c ...
Post a Comment
Read more

practice problems pending

Image
Q1) If (a, b, c) are positive real numbers, prove the inequality ab^3 + bc^3 + ca^3 >= abc(a+b+c). S1. Divide by abc: LHS = b^2/c + c^2/a + a^2/b Use Titu's lemma >= (a+b+c)^2/(a+b+c) = a+b+c H.P. Q2)  Assume x,y,z >= 0 S2) Using power mean inequality: [(x^3+y^3+z^3)/3]^(1/3) >= [(x^2+y^2+z^2)/3]^(1/2) Take a cube: = (8/3)^(1/2) = 16.rt(2)/3.rt(3) Then cancel out 3. But power mean inequality requires x,y,z to be non-negative. We have assumed that but the question didn't give that. H.P. Q3) If w^3 + x^3 + y^3 + z^3 = 10, find the minimum value of w^4 + x^4 + y^4 + z^4 S3) Again apply power mean inequality to get 5^(4/3).2^(2/3)
Post a Comment
Read more