Math IOQM

Q1 . Compute the sum of all positive integers (n) for which lcm(1,2...n) can be written as the product of 10 distinct pairwise coprime positive integers , each less than or equal to (n). S1. For e.g. consider a smaller problem where we need to find 4 distinct pairwise coprime factors. For n = 5,  LCM(1,2,3,4,5) = 60. 60 = 1.2^2.3^1.5^1 So the factors are 1,3,4,5 Each pair is co prime. Each factor is less than 60. So we need first 9 primes and 1 or first 10 primes to solve this. 2,3,5,7, 11,13,17,19 23,29 are the first 10 primes. LCM(1,2... 23) = 1. 2^4. 3^2. 5^2. 7. 11. 13. 17. 19. 23 We can see the 10 factors each pairwise co prime and <= 23 Same will happen for 24,25,26,27,28. For 29,30 we will remove 1 to get exactly 10 factors. That's the last. From 31 we will have at least 11 such factors. Answer = 23 + 24... 30 = 212 Q2. S2.

Q1) (a,b,c) are real numbers such that a+b+c=0 a^2+b^2+c^2=1 Show that a^2b^2c^2 <= 1/54. S1) Let's construct a cubic equation with roots a,b,c. (a+b+c)^2 = 1 + 2(ab+bc+ca) => ab + bc + ca = -1/2 x^3 -x/2 - r = 0 where r = abc Since all 3 roots are real, the product of values of function at critical points(maxima,minima) should be <= 0. Find critical points, derivative = 3x^2 - 1/2 = 0 => x = -+1/sqrt(6) f(1/rt(6)) = 1/6.rt(6) - 1/2.rt(6) - r = 1/3.rt(6) - r f(-1/rt(6) = -1/3.rt(6) - r multiply: r^2 - 1/54 <= 0 H.P. Q2. P2) If 1/x + 1/y + 1/z = 1 for x,y,z > 0 pr. th. (x-1)(y-1)(z-1) >= 8 S2. let a = 1/x and similarly others. a + b + c = 1 x-1 = 1/a - 1 = (1-a)/a = (b+c)/a b+c >= 2.rt(bc) So expr. becomes: (b+c)(c+a)(a+b)/abc>= 8.abc/abc = 8 H.P.

  Homework(proofs): Q1. S1. n = 1 => (2k+1)^(2^1) = 4k^2 + 4k + 1 = 4k(k+1) + 1 = 8p + 1 = 1 mod 2^3(since k(k+1) is even) So works for n = 1 Assume (2k+1)^(2^n) = 1 mod 2^(2^(n+2)) _____[1] and using this prove for n+1: (2k+1)^(2^(n+1)) = 1 mod 2^(2^(n+3)) LHS = (2k+1)^(2^n.2^1) = [(2k+1)^(2^n)]^2 = [2^(n+2).m + 1]^2 using [1] = 1 + 2.m.2^(n+2) + m^2.[2^(n+2)]^2 = 1 + m.2^(n+3) + m^2.2^(2n+4) If you take mod 2^(n+3), it's clearly 1. H.P. Q2. Call a natural number n convenient, if n^2 + 1 is divisible by 1000001 . Prove that among the numbers   1,2,…,1000000, there are evenly many "convenient" numbers. S2. So essentially we need to find some sort of complement for each 'n' satisfying this. If we can show that for each 'n' satisfying this, there is another number satisfying this, we are done. Simplest 'complement' here is -n but that's negative. So let's think circular and try N-n where N = 1000,001 (N-n)^2 +1 = N^2 + n^2 - 2N.n + 1 = n^2...

 Homework multiple choice: (done) Q1. True/False For a polynomial f(x) with integer coefficients and integers a,b,l  we have a = b mod l => f(a) = f(b) mod l? S1. True Q2. The 2-digit integers from 19 to 92 are written consecutively to form the integer  N = 192021⋯9192. Suppose that 3^k is the highest power of 3 that is a factor of N. What is k? S2. Method 1: Since 10^m = 1 mod 9 for any m => 192021⋯9192 = 19 + 20 .. 92 mod 9 = 74/2[19 + 92] = 37*111 mod 3 = 0  mod 9 = 1 * 3 = 3 So k = 1. Method 2: Sum of digits =  (2+3+4+5+6+7+8)*10 + (1+2... 9)*7 + sum_digits(19 + 90 + 91 + 92) = 35*10 + 45*7 + 40 Doing mod 3 gives 2 + 0 + 1 = 0 mod 3 Doing mod 9 gives 8 + 0 + 4 = 3 mod 9 So 3 divides it but 9 doesn't. k = 1 = answer. Q3. Remainder of 3^89*7^86 mod 17? S3. Method 1: = 21^86*27 21 mod 17 = 4 21^2 mod 17 = 16 = -1 (-1)^43 = -1 => -1*27 = -27 mod 17 = -10 mod 17 = 7 mod 17 Method 2: 3^4 = 81 = -4 m 17 3^8 = 16 m 17 = -1 3^89 = 3^88.3 = (-1)^11.3 mod 17 =...

double derivative for concavity check. single derivative for slope(rate of change check). Rolle's theorem: f(a) = f(b) => for some c in (a,b) f'(c) = 0 Mean value theorem, for some c, f'(c) = (f(b) - f(a)/(b-a)

Q1. The position of an object is given by s(t) = sin⁡(3t) − 2t + 4. Determine where in the interval [0,3] the object is moving to the right and moving to the left. Given arccos(2/3) = 0.841 radians. and 2.pie = 6.283 radians. S1. s'(t) = 3cos(3t) - 2 First find critical points: 3cos(3t) - 2 = 0 => cos(3t) = 2/3 => Since cos(3t) is positive, there are 2 solutions (1st and 4th quadrant). 3t = acos(2/3) + 2.pie.k = 0.841 + 2.pie.k and 3t = [2.pie - acos(2/3)] + 2.pie.k = 5.442 + 2.pie.k How many valid solutions are there for 3t in [0,9] since t in [0,3]. Apart from the 2 above, there is only 1 more when 3t = .841 + 6.283 = 7.124 So these 3 are our critical points. Let's evaluate at each of them. Case 1: 3t between [0,.841) s'(0) = 1 => +ive => moving right Case 2: 3t between (.841, 5.442), try 3t = 3(t = 1) => 3cos(3t) - 2 = 3cos3 - 2 cos3 is close to cos(3.14), i.e. -1 so value is negative, moving left. Case 3: 3t between (5.442,7.124), try 3t = 6.283 = 2.pi =...

remainders/residues/residue classes Q1. If a = b mod m and c = d mod m, then: Prove that: (1) a +- c = b +- d mod m (2) ac = bd mod m (3) ax + cy = bx + dy mod m Q2. if a = b mod m, pr. th. a^n = b^n mod m. Q3. If a = b mod m then a = b mod d if d | m. Q4.  Remainder of 13^73 + 14^3 mod 11. Q5. Pr. th. ax = ay mod m iff x = y mod (m/gcd(a,m)) S5. m = k.q1, a = k.q2 where k = gcd(a,m) m/k = q1 x = y mod q1 => ax = ay mod q1 => ax = ay mod m since q1| m. ----------------------------------------------------------------

Day 1: Q1. The repeating decimals x = 0.ababab... and y = 0.abcabc.... satisfy x + y = 33/37 Find the 3 digit number abc. S1. (10a+b)(1/100 + 1/10000...) = (10a+b)/100[1/1-1/100] = (10a + b)/99 (100a + 10b +c)(1/1000 + 1/1000,000....) = (100a+10b+c)/999 (10a + b)/99 + (100a+10b+c)/999 = 33/37 => 999(10a+b) + (100a+10b+c).99 = 33.99.999/37 = 27.33.99 => 111(10a+b) + (100a+10b+c).11 = 99^2 = 9801 => 2210a + 221b + 11c = 9801______[1] => a <= 4 2210*4 = 8840 => 221b + 11c = 961 b = 4 => 11c = 961 - 884 = 77 => c = 7 abc = 447 Also in [1] if we take mod 11 then: 2210a + 221b = 0 mod 11 221(-a +b) = 0 mod 11 => a = b mod 11 Since a,b are single digit => a = b 221a.11 + 11c = 9801 => 221a + c = 891 a = 4 => c = 7 Q2. Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. S2. Let's do step by step. Subset size: 3 => There are 10 ways. Total: 10 Size: 4 => 10 ways to pick 4...

Q1. if p | ab then either p divides a or p divides b. 'p' is a prime. S1. Case 1: p | a: done Case 2: p doesn't divide a: gcd(a,p) = 1 => au + pv = 1 Multiply by 'b': bau + bpv = b p divides both terms on LHS => p | RHS => p | b H.P. Corollary: If p | a1a2....an then p divides some ai. Q2. Theorem: A composite number has at least one prime divisor. Prove this. S2. A set of all its +ve divisors except 1 and itself. Let (S) be the set. As the no. must have some other divisors than 1 & itself, then (S) is non-empty and S is subset of N(natural numbers). So by well ordering property (S) has a least element (l). If (l) is a prime then we are done. But if (l) is not a prime then there exists d | l (d divides l). C is the composite number we are talking about. d | l and l | C => d | C => d is in S and d < l which is a contradiction. Q3. find all possible values of 'p' s.t. (p) and (p^2 + 8) both are prime. S3. Case 1: p mod 3 = 0 => p can ...

 Q1. What is parametrization of line passing through (2,0) and (0,1)

Q1. 100 in base 10 needs to be converted to base 2,3,4,5,6,7,8,9. S2. Base 9: 100 = 81 + 18 + 1 = 121 Base 8: 100 = 64 + 4.8 + 4 = 144 Base 7: 100 = 98 + 2 = 202 Base 6: 100 = 72 + 24 + 4 = 244 Base 5: 100 = 25*4 = 400 Base 4: 100 = 64.1 + 16.2 + 4 = 1210 Base 3: 100 = 3^4.1 + 3^2.2 + 1 = 10201 Base 2: 100 = 2^6.1 + 2^5 + 2^2.1 = 1100100  Q2. S2. Let's try. Last digit is 1. Then 5+4 = 9 but it says 2. So it is not base 10. Looks like base 7. And since there is enough gap in the beginning of the first number, 2 numbers will fit there. Answer: 23451 + 15642. Q3. Let n be a positive integer and d be a digit such that the value of the numeral 32d ​ in base n equals 263, and the value of the numeral 324 ​ in base n equals the value of the numeral 11d1 in base six. What is n+d? S3. 3n^2 + 2n + d = 263 3n^2 + 2n + 4 = 216 + 36 + 6d + 1 Solving for d we get d = 2 And solving for n we get n = 9 and another non integer. Answer n + d = 11 Q4. Using the digits 1,2,3,4,5,6,7, and 9 , form ...

Q1. If x^n + y^n is a prime number for some x,y > 1 then n is necessarily: Options: Power of 2, Multiple of 4, Multiple of 3, Odd S1. Answer: Power of 2. Proof by contradiction: Assume that n has an odd factor k > 1. n = m.k x^n + y^n = (x^m)^k + (y^m)^k A^k + B^k = (A+B)(A^k-1 -A^k-2.B ....+ B^k-1) for odd 'k'. Here A = x^m and B = y^m x,y > 1 m>=1 => A+B >= 4 And the other factor is also more than 1 since A^k + B^k > A + B since k > 1. So A^k + B^k is not a prime. So n can't have any odd factor. So n has to be power of 2. H.P. For e.g. n = 2 x = 2, y = 3 4 + 9 = 13 Q2. A natural number has last digit 8 in base 16 representation. What will be the remainder, when it is divided by 8 , in decimal system S2. 0 Q3. If a prime can be written as sum of two perfect square, then the remainder when it is divided by 8 cannot be S3. Any square upon division by 8 will leave 0,1,4 as remainders. So adding 2 of them can only give 0,1,2,4,5 as remainders. And if th...

 Q1. Prove that for every positive integer (n), the number [ 3^{3^n}+1 ] is the product of at least (2n+1) (not necessarily distinct) primes. S1. Prove by induction. Q2. Prove that for every positive integer (n), there exists an (n)-digit number divisible by (5^n) whose all digits are odd. S2. Proof by induction: Let's assume it holds true for k  Now we construct 5 (n+1) digit numbers using A: All 5 of them leave different remainders modulo 5 so at least one of them will leave 0 and that would give us divisibility by 5^(n+1). Why will all be different modulo 5? Let's try to prove by contradiction: 2^n + a = 3.2^n + a mod 5 => 2.2^n = 0 mod 5 false. And each time you do this you will get some even number = 0 mod 5. Which is false. H.P. Q3. Let n be a positive integer. Let 0 < a1 < a2 ... an be real numbers. Prove that at least {n+1}C{2}) of the sums +-a1 +-a2 ... +-an are distinct. S3. First we will show that this problem maps to another simpler problem. And then solve...

Q1. Show that (1 - 1/2^2)(1 - 1/3^2)....(1 - 1/(n+1)^2) = n+2/2n+2 S1. Easy to show via induction. Other way via telescopic cancellations: Kth term is (k^2 - 1)/k^2 = (k-1)(k+1)/k^2 = (k-1)/k.(k+1)/k Now separate out k-1/k and k+1/k terms and multiply: 2-1/2 * 3-1/3 * 4-1/4 .... n/n+1 = 1/n+1 2+1/2 * 3+1/3 ... n+2/n+1 = n+2/2 Hence proved. Q2. Show that: S2. Short method: r*nCr = n*(n-1)C(r-1) and take sigma simply. Longer method:  2^(n-1) = (n-1)C0 + (n-1)C1... (n-1)C(n-1) (n-1)Ck *n = nCk*(n-k) How? n * (n-1)!/k!(n-1-k)! = n! /k!(n-k-1)! But (n-k-1)! = (n-k)!/(n-k) So n * (n-1)!/k!(n-1-k)! = (n-k)n! /k!(n-k)! = nCk*(n-k) So n*2^(n-1) = n *2^(n-1) = n*[(n-1)C0 + (n-1)C1... (n-1)C(n-2)+ (n-1)C(n-1)] = nC0 * (n-0) + nC1*(n-1) ... nC(n-2)*(2)+ nC(n-1)*(1) It can be rewritten as: = nCn*n + nC1 * (n-1) ... nC2 * 2 + nC1 * 1 = (r = 1 to n)Sigma(r*nCr) = (r = 0 to n)Sigma(r*nCr) Hence proved. Q3. S3. Quite simple. Let the given sum be S. 3S = 1.3^2 + 2.3^3... n.3^(n+1) S-3S = 3 + 3^2 ......