Math IOQM

PHP1: n holes, n+1 pigeons, at least 1 hole with > 1 pigeons. PHP2: n holes, nk+1 pigeons, at least 1 hole with > k pigeons. Q1. Pr. th. If there are 5 points inside a unit square, then the distance between at least any two points is less than 1/sqrt(2). A1. Divide in 4 smaller squares => at least 2 will be inside one square. Max distance inside that square is 1/sqrt(2). Q2. There are 14 sock pairs in a basket. How many you need to pick to be sure that you have 1 pair at least. A2. 15. PHP3: If mean of n +ive integers is k then at least 1 of them is >= k and at least 1 of them is <= k. Proof: If a1 = a2 = ... an = k then H.P. If a1 <= a2 <= a3 ... <= an then if a_i > k => a_j < k H.P. Q3. Suppose numbers from 1 through 20 are placed in some order around a circle. Prove that i) The sum of some three consecutive numbers must be at least 32. ii) The sum of some four consecutive numbers must be at least 42. Let the triplets be (a1,a2,a3) (a2,a3,a4) ... (a20...

1. How many ways to distribute 10 different balls into 3 different bags such that none of the bags is empty? S1. Distinct objects/distinct buckets => PIE(Principle of Inclusion Exclusion) Step 1: Total cases: 3^10 since each ball can go into any of the bags. Step 2: Subtract those cases where one bag is empty: 3C1 to choose one bag. And now each ball has 2 options: 2^10. So total 3*2^10 cases need to be subtracted to account for one empty bucket. In step 2 consider what happens in detail: When we made one bucket empty, 10 balls have to go into 2 buckets: 2^10. This also includes the cases when all the balls go to one bucket. So considering empty bucket1 also considers the cases where bucket 1 and 2 are both empty. Similarly when we consider bucket2 as empty we are also considering the case where both bucket 1 and 2 are empty. Essentially we are double subtracting the cases where 2 buckets are empty. So we need to add them back. 3C2 to choose 2 buckets to remain empty. Now each ball ...

 If an odd prime number leaves remainder of 1 when divided by 4 then it can be expressed as sum of two integer squares and those 2 integers will be unique for this prime. Examples:  17 = 16 + 1 29 = 25 + 5 41 = 25 + 16 1013 = 22^2 + 23^2

Theorem: If a1x1 + a2x2 + .... an.xn = K then this Diophantine equation has a solution if d | K where d = gcd(a1,a2...an). We can note the similarities with Bezout's lemma here. Practice: Which of these Diophantine equations have integer solutions? 1. 21x + 15y = 17 2. 7x + 17y = 27 Theorem: If ax + by = c and d | c, where d = gcd(a,b), then this Diophantine equation has infinitely many solutions, and the solutions are of the form x = x0 + (b/d).k, y = y0 - (a/d).k, where k is integer and (x_0, y_0) are particular solutions of (ax + by = c); and x0, y0 are integers.

  [ABC] = a.c.sin(B)/2 [ABC] = [ABE] + [EBC] [ABE] = x.c.sin(B/2)/2 [EBC] = a.x.sin(B/2)/2 x = ac.sin(B)/sin(B/2).(a+c) x = ac/(a+c) * 2cos(B/2) BE = 2ac.cos(B/2)/(a+c)

 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.

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

 for a,b positive integers if ab+ 1 = k^2 i.e. perfect square then if we use c = a + b + 2k then bc + 1 and ac + 1 will also be perfect squares.

 x^2 - Dy^2 = 1 has infinitely many integer solutions (x,y) if D is a positive non-square integer. Trivial solution: (1,0) Fundamental solution: smallest positive values of x,y both of which are non-zero.

Prove that: If x divides y, then (a^x - 1) divides (a^y - 1) where a,x,y are positive integers and a > 1. Proof: We know that a^x - 1 can be written as (a - 1)(1 + a + a^2 ... a^(x-1)) Let y = kx Then a^y - 1 = a^(kx) - 1 = (a^x)^k - 1 Let u = a^x then a^y - 1 = u^k - 1 = (u - 1)(1 + u + u^2 ... u^(k-1)) = (a^x - 1)(...) H.P. The result above can be used to prove that: gcd(a^m - 1, a^n - 1) = a^(gcd(m,n)) - 1 Proof: Let gcd(m,n) = g Then using Bezout's identity, there exist x,y such that mx + ny = g => a^g = a^mx.a^ny____________[1] Also, since g divides m and n a^g - 1 divides a^m - 1 and a^n - 1 So a^g -1 is a common divisor. Now we need to prove that it is greatest common divisor. Let gcd(a^m - 1, a^n - 1) = D Then a^m - 1 mod D = 0 => a^m = 1 mod D and a^n = 1 mod D => (a^m)^x = 1 mod D and (a^n)^y = 1 mod D => a^g = 1 mod D using [1] => D divides (a^g -1) So D divides (a^g -1) which is a common divisor of (a^m - 1) and (a^n - 1) while D is their gcd. GCD can ...

A good video here .  How do you find 'x' s.t. x = 3 mod 11 x = 4 mod 7 x = 1 mod 5 First check that 5,7,11 are pairwise co-prime. Done. Then we write 'x' as sum of 3 numbers in a way that 2 of them disappear when taking mod by any of 5,7,11 So x = a.7.11 + b.5.11 + c.5.7 If I do x mod 5, I will get a.7.11 mod 5 and rest 2 numbers will disappear. Same for 7 and 11. But the question is are we really allowed to write 'x' like this? Yes. Let's see why. So x mod 11 = c.7.5 And given x = 3 mod 11. => 3 = 35c mod 11 Since gcd(35,11) =1 which is necessary to apply CRT, using Bezout's lemma: there will be some s,t s.t. 35s + 11t = 1 Take mod 11 35s = 1 mod 11 Now multiply by 3 on both sides 3.35.s = 3 mod 11 =>  there exists a number(here 3s) which upon multiplication with 35 gives 3 mod 11. So we are guaranteed a solution. So essentially if 2 numbers a,b are co prime then for every possible remainder r = 0,1... a-1 there will exist an 'x' s.t. x.b ...

 

  THE MONOMIAL LEMMA So f(x) = 1 + x^n = 1001 = 1 + 10^n => n = 3 => f(20) = 1 + 20^3