Math IOQM

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.

 newton's method

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

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)

Q1. Prove that, for a, b, c ∈ ℝ⁺, a/b + b/c + c/a ≥ (a + b + c)² / (ab + bc + ca). S1. We will use Titu's lemma to prove it. First let's prove Titu's using C-S. C-S says for any real numbers: (a1b1 + a2b2 ... anbn)^2 <= (a1^2+ a2^2 .. an^2).(b1^2+b2^2...bn^2) Let's use p1 = a1/sqrt(b1)... with addl. constraint that b1,b2.. are positive reals. q1 = sqrt(b1)... It becomes: (p1 + p2 .. pn)^2 <= (p1^2/q1 ..)(q1+q2...qn) => (p1+p2..pn)^2/(q1+q2..qn) <= p1^2/q1 + p2^2/q2... This is Titu's lemma. Now, for the given question. Make LHS like this: a^2/ab + b^2/bc + c^2/ac In Titu's lemma, let's use: p1 = a, p2 = b, p3 = c q1 = ab, q2 = bc, q3 = ac So it becomes: (a+b+c)^2/(ab+bc+ca)<= a^2/ab + b^2/bc + c^2/ac H.P. Q2. If P1, P2, ..., P2014 be an arbitrary rearrangement of 1, 2, ..., 2014. Prove that 1/(P1 + P2) + 1/(P2 + P3) + ... + 1/(P2013 + P2014) > 2013/2016. S2. We will use Titu's lemma here again. Which is: a1^2/b1 + a2^2/b2 ... a2013^2/b...

 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.