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

Let the number have 'k' digits. So the number is: d_k.10^k + d_(k-1).10^(k-1) ... d_0.10^0 Take mod 9. Any power of 10 mod 9 = 1 so the result is: d_k + d_(k-1) ... d_0 which is sum of its digits. So any 2 integers which have same digits will have same remainder upon division by 9.

Q. Determine the smallest prime that does not divide any five-digit number whose digits are in a strictly increasing order. Solution: 2 doesn't work: 12346 3,5 don't work: 12345 7 doesn't work: 12348 (since 348-12 = 336 div by 7) 11 => abcde => a-b + c-d + e a-b <= -1 c-d <= -1 5<=e <= 9 Max sum = 7 Total sum can never be <= 0 because e + a + c > b + d always. Why? Because e > d c>b. So sum can never be 0 or multiple of 11. 11 is the answer. For finding the min value, also see: a + (c-b) + (e-d) 1     1           1 So min value is 3 Q. Suppose for some positive integers ( r ) and ( s ), the number ( 2^r ) is obtained by permuting the digits of the number ( 2^s ) in decimal expansion. Prove that ( r = s ). Solution: Since both the number have same number of digits('d') and same sum of digits, we use those properties. Sum of digits is same =>  2^r = 2^s mod 9 Why? Proof here. WLOG r >= s 2^r = 2^s mod 9 ...

Question: 3x + 7y = 100 x,y are positive integers. How many pairs of x,y are possible? Solution: Given that x,y >= 1. So 7y < 100 y < 100/7 y <= 14 So 1 <= y <= 14. Now 3x = 100 - 7y If you put all the values of y one by one you see that RHS becomes divisible by 3 for y = 1,4,7,10,13. So answer is 5 such pairs are there. But why did we choose y for iterating and not x? Let's do it with x. 3x < 100 => x <= 33 So we would have to iterate 33 times and check for divisibility by 7 each time. So it is wiser to go for y. We can make the solution much simpler using modulo arithmetic . 3x = 100 - 7y Do modulo by 3 on both sides. 3x % 3 = (100 - 7y) %3 0 = 100 % 3 - 7y %3   %3 0 = 1 - (7 %3) (y%3) %3 0 = 1- 1.y % 3 y = 1 % 3 Since y goes from 1 to 14, there are 5 values which leave the remainder 1 when divided by 3.

One can easily prove that (a + b) % k = ( (a % k) + (b % k) ) % k, where % is the remainder operator. To prove that assume a = pk +q, b = mk + n. And try to equate LHS and RHS. Similarly, (a - b) % k = ( (a % k) - (b % k) ) % k And (ab) % k = ( (a % k) * (b % k) ) % k Ex 1: 6 mod 7 = -1 mod 7 This is a useful trick for exams. If remainder is 1 less than divisor it can be rewritten as -1. Since -1 + 7 mod 7 = 6 Similarly  13 mod 7 = -1 17 mod 9 = -1 Ex 2: For a non-zero 'a', a mod (a + 1) is -1. Same argument as above. Ex 3: Extending Ex 2, a^2 mod (a+1) = 1 Since a^2 mod (a+1) = -1 * -1 = 1 Ex 4: Prove that for any positive integer n: 1) n.(n+1).(2n+1) is divisible by 6. Either n or (n+1) is even. So it's divisible by 2. Now 3 cases for proving divisibility by 3: a) n mod 3 = 0, then it's div by 3. b) n mod 3 = 1 then (2n + 1) mod 3 = 2 + 1 = 0 mod 3, hence div by 3. c) n mod 3 = 2 then (n + 1) mod 3 = 0, H.P. 2) (2n - 1). n. (2n + 1) is divisible by 3. Similar to above...