Math IOQM

 If gcd(a,n) = 1, then: for some positive integer 'k' a^k = 1 mod n Why? Why is it certain that for some k we will get a^k = 1 mod n? WLOG, let there be i > j s.t. a^i = a^j mod n. There will be such i,j for sure because there are infinitely many powers but remainders have only 'n' possible values. => a^i - a^j = c.n (0 mod n) a^j ( a^(i-j) - 1) = c.n Since a,n are coprime => n divides a^(i-j) - 1 => we found a power of k s.t. a^k = 1 mod 'n'. Now, Multiplicative order of 'a' modulo 'n' is the smallest 'k' s.t. a^k = 1 mod 'n'. => if a^m = 1 mod n then k | m Why? Let m = xk + y by division algorithm. So 0 <= y < k a^(xk + y) = 1 mod n = a^xk.a^y = a^y = 1 mod n But y < k and we had said that k was the smallest integer for which a^(something) = 1. Hence proved by contradiction.

 Q1. S1. Cross multiply and simplify to get: 9 (10^3013 - 10^2013) > 0 H.P. Q2. S2. Consider only 'a' side. Call it A. 1/A = 1 + a^n/(1 + a + .. a^(n-1)) = 1 + 1/[1/a + 1/a^2 ... 1/a^(n)] Assume 1/A > 1/B We will figure out whether it's true. =>  1/[1/a + .. 1/a^n] > 1/[1/b + .. 1/b^n] =>  [1/b + .. 1/b^n] > [1/a + .. 1/a^n] This is clearly true since a > b. So the original assumption was correct. => 1/A > 1/B => A < B. Q3. a,b,c are real numbers s.t. a >= b >= c. Prove or disprove: a^2 + ac + c^2 >= 3b(a-b+c) S3. Make it a quadratic in b by moving RHS to LHS. And then show D <= 0 So it will be always >= 0 So it will be proved(not disproved).

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 =...