Math IOQM

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. ------------------------------ Homework multiple choice: 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 ...

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