Title 3. Number theory.pdf ✅

NUMBER THEORY RMO 37 PACE IIT & MEDICAL: Mumbai /Delhi & NCR / Lucknow / Goa / Akola / Kolkata / Patna / Nashik / Pune / Nagpur / Kanpur / Bokaro / Dubai 2 DIVISIBILITY For an integer m and a nonzero integer n, we say that m is divisible by n or n divides m if there is an integer k such that m = kn; that is, m n is an integer. We denote this by n|m. If m is divisible by n, then m is called a multiple of n; and n is called a divisor (or factor) of m. Because 0 = 0 · n, it follows that n|0 for all integers n. For a fixed integer n, the multiples of m are 0, ±n, ±2n, .... Hence it is not difficult to see that there is a multiple of n among every n consecutive integers. If m is not divisible by n, then we write n | m. (Note that 0 | m for all nonzero integers m, since m = 0 = k · 0 for all integers k.) For a prime p we say that pk fully divides n and write pk ||n if k is the greatest positive integer such that pk |n. Properties Let x, y, and z be integers. We have the following basic properties: (a) x|x (reflexivity property); (b) If x|y and y|z, then x|z (transitivity property); (c) If x|y and y  0, then |x|  |y|; (d) If x|y and x|z, then x|y + z for any integers  and ; ie if x|y, then, x|y for any integers  . (e) If x|y and x|y ± z, then x|z; (f) If x|y and y|x, then |x| = |y|; ie, x = ±y (g) If x|y and y  0, then y | y x ; (h) For z  0, x|y if and only if xz|yz. (i) All the divisors of y appear in pairs, namely, x and y x (observe that x  y x if y is not a perfect square). Hence the number of divisors of n are odd iff n is a perfect square. Applications 2 1. Prove that (n+1)! + 1 has no prime factor less than n. Does this mean that (n + 1)! + 1 is prime  n N? 2. Find least positive value of a + b where a, b are positive integers such that11|a + 13b and 13|a + 11b 3. Find the number of pairs of natural numbers (m, n) such that (a) m 0 1 n   (b) gcd (m, n) = 1 (c) mn = 25! (RMO 1994) 4. Find all 6 digit natural numbers 1 2 3 4 5 6 a , a , a , a , a , a using digits 1, 2, 3, 4, 5, 6 such that for each k = 1, ..., 6 we have 1 2 k k | a , a ...a (RMO) 5. (i) Consider two positive integers a and b a b such that 2000 | a b . What is the least value of product ab. (ii) Consider two positive integers a and b such that b a 2000 a b . What is the least value of product ab. 3. PARITY The set of integers, denoted by Z, can be partitioned into two subsets, the set of odd integers and the set of even integers: {±1, ±3, ±5, ...} and {0, ±2, ±4, ...}, respectively. Although the concepts of odd and even integers appear straight-forward, they come handy in tackling various number-theoretic problems.
NUMBER THEORY RMO 38 PACE IIT & MEDICAL: Mumbai /Delhi & NCR / Lucknow / Goa / Akola / Kolkata / Patna / Nashik / Pune / Nagpur / Kanpur / Bokaro / Dubai Properties  An odd number is of the form 2k + 1,or 2k − 1 for some integer k;  An even number is of the form 2m, for some integer m;  The sum of two odd numbers is an even number;  The sum of two even numbers is an even number;  The sum of an odd and an even number is an odd number;  The product of two odd numbers is an odd number;  The product of integers is even if and only if at least one of its factors is even.  For any integers a, b the parity of a + b and a − b is the same.  The product of two consecutive integers is always even.  One of the two consecutive even numbers is divisible by 4. The product of two consecutive even integers is always divisible by 8. Applications 3 1. Let n be an integer greater than 1. Prove that (a) 2n is the sum of two odd consecutive integers; (b) 3n is the sum of three consecutive integers. 2. Let k be an even number. Is it possible to write 1 as the sum of the reciprocals of k odd integers? 3. [HMMT 2004] Zach has chosen five numbers from the set 1, 2, 3, 4, 5, 6, 7. If he told Claudia what the product of the chosen numbers was, that would not be enough information for Claudia to figure out whether the sum of the chosen numbers was even or odd. What is the product of the chosen number. 4. MODULAR ARITHMETIC Let a, b, and m be integers, with m  0. We say that a and b are congruent modulo m if m divides a − b. We denote this by a b (mod m). The relation “ ” on the set Z of integers is called the congruence relation. If m does not divide a − b, then we say that integers a and b are not congruent modulo m and we write a  b (mod m). Properties  a  a (mod m) (reflexivity).  If a  b (mod m) and b  c (mod m), then a  c (mod m) (transitivity).  If a  b (mod m), then b  a (mod m).  If a  b (mod m) and c  d (mod m), then a + c b + d (mod m) and a − c  b − d (mod m)  If a  b (mod m), then for any integer k, ka  kb(mod m).  If a  b (mod m) and c  d (mod m), then ac  bd (mod m).  In general, if ai  bi (mod m), i = 1, ... , k, then a1 ... ak  b1 ... bk (mod m).  In particular, if a  b (mod m), then for any positive integer k, ak  b k (mod m).  We have a  b (mod mi), i = 1, ...,k, if and only if a  b (mod lcm(m1, ...,mk)).  In particular, if m1, ...,mk are pair wise relatively prime, then a  b (mod mi), i = 1, ..., k, if and only if a  b (mod m1... mk ).  If a  b (mod m) and d|a, d|b and gcd(d, m) = 1, then a b d d  (mod m)  If a  b (mod m) and d|a, d|b and gcd(d, m) = k, then a b d d  (mod m k )
NUMBER THEORY RMO 39 PACE IIT & MEDICAL: Mumbai /Delhi & NCR / Lucknow / Goa / Akola / Kolkata / Patna / Nashik / Pune / Nagpur / Kanpur / Bokaro / Dubai Some useful facts  x 2  0, 1(mod 3)  0, 1(mod 4)  0,±1(mod 5) 0, 1, 3, 4 (mod 6)  0, 1, 2, 4(mod 7)  0, 1, 4, (mod 8) 0, 1, 4, 7(mod 9)  x 3  0, ±1(mod 3)  0, ±1(mod 4)  0, ±1, ±2(mod 5) 0, ±1, ±2, 3(mod 6)  0, ±1(mod7)  0, ±1,±3(mod 8) 0, ±1(mod 9)  x 4  0, 1(mod 3)  0, 1(mod 4)  0, 1, (mod 5) 0, 1, 4(mod 6)  0, 1, 2, 4, (mod7)  0, 1(mod 8) 0, 1, 4, 7(mod 9)  x 3  x (mod 6)  x 5  x (mod 5)  x 4  1, 0(mod16) Applications 4 1. Find the remainder when 1989 · 1990 · 1991+19923 is divided by 7. 2. Find the reminder when 9123456789 is divided by 8. 3. Find the reminder when 7123456789 is divided by 8. 4. Prove that 255 + 1 is divisible by 11 5. Find the reminder when 7101 is divided by 25. 6. Find the reminder when 4976 is divided by 13. 7. Determine the last 2 digits of the number 7999 8. Determine the last two digits of the number 7 7 7 5. DECIMAL REPRESENTATION AND DIVISIBILITY TESTS Let n n 1 n n 1 0 n n 1 0 a a ...a a .10 a .10 .... a        be the decimal representation of the number n n 1 0 a a ....a     n n 1 0 n n 1 0 a a ...a a a .... a mod 3          n n 1 0 n n 1 0 a a ...a a a ....a mod 9         n n 1 0 1 0 1 0 1 0 a a ...a a a 10a a 2a a mod 4          n n 1 0 2 1 0 2 1 0 2 1 0 a a ...a a a a 100a 10a a 4a 2a a mod 8            k n n 1 0 k 1 1 0 a a ...a a ...a a mod 2         n n n 1 0 0 1 2 3 n a a ...a a a a a ... 1 a mod11        (alternating sum)  n n 1 0 5 4 3 5 4 3 2 1 0 a a ....a .... a a a a a a a a a      (mod 7 or 11 or 13)  n n 1 0 5 4 3 5 4 3 2 1 0 a a ...a ... a a a a a a a a a      (mod 27 or 37) Applications 5 1. State and prove the divisibility tests for n 2 and n 5 2. The integer n is the smallest positive multiple of 15 such that every digit of n is either 0 or 8. Find n. 3. Let N a a ...a , M a 4a 4a . ... 4a       n n 1 0 0 1 2 n  then, prove that 6 | N iff 6| M