Scribd Logo
Upload

Welcome to Scribd!

  • 322 views

    IOQM 2029 (Properties of GCD, LCM)

    Uploaded by

    Ritvik Nehra
    The document provides information about Abhay Mahajan, including that he has over 13 years of teaching experience, has mentored over 20,000 students, and has helped produce over 400 selections for IIT and other top institutions. It also lists his achievements in producing selections for other competitive exams like INMO and EGMO.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    IOQM 2029 (Properties of GCD, LCM)

    Uploaded by

    Ritvik Nehra
    322 views57 pages
    The document provides information about Abhay Mahajan, including that he has over 13 years of teaching experience, has mentored over 20,000 students, and has helped produce over 400 selections for IIT and other top institutions. It also lists his achievements in producing selections for other competitive exams like INMO and EGMO.

    Original Description:

    Vos

    Original Title

    IOQM 2029(Properties of GCD, LCM)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides information about Abhay Mahajan, including that he has over 13 years of teaching experience, has mentored over 20,000 students, and has helped produce over 400 selections for IIT and other top institutions. It also lists his achievements in producing selections for other competitive exams like INMO and EGMO.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    322 views57 pages

    IOQM 2029 (Properties of GCD, LCM)

    Uploaded by

    Ritvik Nehra
    The document provides information about Abhay Mahajan, including that he has over 13 years of teaching experience, has mentored over 20,000 students, and has helped produce over 400 selections for IIT and other top institutions. It also lists his achievements in producing selections for other competitive exams like INMO and EGMO.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 57

    ABHAY MAHAJAN

    B.Tech. IIT Roorkee


    ➔ 13+ years teaching experience
    ➔ Mentored and taught around 20000+ students
    ➔ Produced 400+ IIT selections
    ➔ 25+ INMO selections
    ➔ 2 EGMO Selection
    CONGRATULATIONS
    Aharshi Roy has qualified
    BMO-2 with distinction,which
    leads to the IMO training camp in
    the UK.

    This training camp is equivalent


    to IMOTC India.
    Properties of
    GCD, LCM
    GCD and LCM

    ★ Greatest Common Divisor:


    G.C.D. or gcd(x, y) of two natural numbers is the greatest natural
    number which divides them both.
    Example: gcd(18, 24) = 6

    ★ Least Common Multiple:


    L.C.M. or lcm(x, y) of two natural numbers is the least natural number which
    is divisible by both of them.
    Example: lcm(18, 24) = 72.
    Coprime Numbers

    COPRIME NUMBERS:
    Two natural numbers are called relatively prime or coprime
    if they have no common divisors greater than 1 i.e. gcd(x, y) = 1.
    Example: 9 & 16 are coprime integers, while 6 & 15 are not.

    ● Any two consecutive integers are coprime.


    ● Any two consecutive odd integers are coprime.
    Properties:

    1. LCM(a, b) x GCD(a, b) = ab
    2. GCD(a, b) = GCD(a + bk, b)
    (i) GCD(a, b) = GCD(a-b, b)
    (ii) GCD(n, n + 1) = 1
    Properties:

    3. If GCD(a, b) = d then
    a = dx, b =dy where x, y are coprime
    LCM (a, b) = d x y

    4. If GCD(a, b) = 1 then
    GCD(a + b, ab) = 1
    Q. The sum of two positive integers is 52 and their LCM
    is 168. Find the numbers.
    Q. The sum of two positive integers is 52 and their LCM
    is 168. Find the numbers.

    Answer: Let the positive integers be a and b and a ≤ b.

    Let d = (a, b) so that a = dm, b = dn and (m, n) = 1.


    Thus (i) a + b = d(m+ n) = 52 = 4 × 13 and (ii) I.c.m. of a,b =
    dmn = 168 = 4 × 2 × 7 × 3.
    But ((m + n)d, mnd) = d, since (m, n) = 1.
    Hence by (i) and (ii), d = 4. So m + n = 13 and mn = 42.
    Hence, m = 6,n = 7 and a = dm = 24, b = dn = 28.
    AMC 10, 2018
    How many ordered pairs (a, b) of positive integers
    Q.
    satisfy the equation
    a.b +63 =20.lcm(a, b) +12.gcd(a, b)
    where gcd(a,b) denotes the greatest common
    divisor of a and b, and lcm(a, b) denotes their least
    common multiple?
    AMC 10, 2018
    How many ordered pairs (a, b) of positive integers
    Q.
    satisfy the equation
    a.b +63 =20.lcm(a, b) +12.gcd(a, b)
    where gcd(a,b) denotes the greatest common
    divisor of a and b, and lcm(a, b) denotes their least
    common multiple?

    Solution:
    Let x = lcm (a,b) and y = gcd(a,b). Therefore, a.b. = lcm (a,b). gcd (a,b) = x.y.
    Thus, the equation becomes
    x.y + 63 = 20x +12y
    x.y - 20x - 12y + 63 = 0
    Using Simon’s Favorite Trick, we rewrite this equation as
    (x-12) (y-20) – 240 + 63 = 0
    (x-12) (y-20) = 177
    AMC 10, 2018
    How many ordered pairs (a, b) of positive integers
    Q.
    satisfy the equation
    a.b +63 =20.lcm(a, b) +12.gcd(a, b)
    where gcd(a,b) denotes the greatest common
    divisor of a and b, and lcm(a, b) denotes their least
    common multiple?
    Solution:

    Since 177 = 3.59 and x > y, we have x - 12 = 59 and


    y - 20 = 3, or x - 12 = 177 and y – 20 = 1. This gives us the
    solutions (71,23) and (189,21) Since the GCD must be a divisor
    of the LCM, the first pair does not work. Assume a > b. We must
    a = 21 . 9 and b = 21, and we could then have a < b, so there 2
    solutions.
    PRMO 2019

    Q. How many ordered pairs (a, b) of positive integers


    with a < b and 100 ≤ a,b ≤ 1000 satisfy
    gcd (a,b) : lcm (a,b) = 1 : 495 ?
    PRMO 2019

    Q. How many ordered pairs (a, b) of positive integers


    with a < b and 100 ≤ a,b ≤ 1000 satisfy
    gcd (a,b) : lcm (a,b) = 1 : 495 ?
    Solution:
    ab = (gcd)2.32.5.11

    32 5.11 12,13…..18 (100 ≤ a,b ≤ 1000)


    5 32.11 no value (100 ≤ a,b ≤ 1000)
    11 32.5 10,11….22 (100 ≤ a,b ≤ 1000)
    1 32.5.11 no values (100 ≤ a,b ≤ 1000)
    so 7 + 13 = 20 values
    IOQM 2022

    Q. Let m, n be natural numbers such that m + 3n -


    5 = 2 LCM(m, n) - 11 GCD(m, n). Find the
    maximum possible value of m + n.
    IOQM 2022

    Q. Find the number of ordered pairs (a, b) such


    that a, b ∊ {10, 11, …., 29, 30} and GCD (a, b) +
    LCM (a, b) = a + b
    AIME 1985

    Q. The numbers in the sequence 101,104,109,116,... are of the form an = 100 + n2,

    where n = 1,2,3,.... For each n, let dn be the greatest common divisor of an and an+1.

    FInd the maximum value of dn as n ranges through the positive integers.


    AIME 1985

    Q. The numbers in the sequence 101,104,109,116,... are of the form an = 100 + n2,

    where n = 1,2,3,.... For each n, let dn be the greatest common divisor of an and an+1.

    FInd the maximum value of dn as n ranges through the positive integers.


    Solution:
    If (x,y) denotes the greatest common divisor of x and y. Then we have dn = (an, an+1) = (100 +
    n2 , 100 + n2 + 2n + 1). Now assuming that dn divides 100 + n2, it must divide 2n + 1. If it is
    going to divide the entire expression 100 + n2 + 2n + 1.
    Thus the equation turns into dn = (100 + n2, 2n + 1). Now note that since 2n + 1 is odd for
    integral n, we can multiple the left integer, 100 + n2, by a power of two without affecting the
    affecting the greatest common divisor. SInce the n2 term is quite restrictive, let’s multiply by 4
    so that we can get a (2n + 1)2 in there.
    So dn = (4n2 + 400, 2n+1) = ((2n+1)2 – 4n + 399, 2n + 1) = (– 4n + 399, 2n+1). It simplified the
    way we wanted it to ! Now using similar techniques we can write
    dn = (-2(2n+1) + 401, 2n+1) = (401, 2n+1). Thus dn must divide 401 for every single n. This
    means the largest possible value of dn is 401, and we see that it can be achieved when
    n = 200.
    Q. Let [r, s] denote the least common multiple of
    positive integers r and s. Find the number ordered
    triples (a, b, c) of positive integers for which [a, b] =
    1000, [b, c] = 2000, and [c, a] =2000
    Q. Let [r, s] denote the least common multiple of
    positive integers r and s. Find the number ordered
    triples (a, b, c) of positive integers for which [a, b] =
    1000, [b, c] = 2000, and [c, a] =2000

    Answer: [a, b] = 23 53, [b, c] = 24 53, and [c, a] =24 53


    70 As a and b cannot have 24, therefore c contain 24.
    CASE 1. For c = 245n, 0 ≤ n ≤ 2
    (I) a = 2m 53, 0 ≤ m ≤ 2 & b = 23 53
    (II) a = 23 53 & b = a = 2m 53, 0 ≤ m ≤ 3
    CASE 2. For c = 2453
    (I) a = 2m5n, 0 ≤ m & n ≤ 2 & b = 23 53
    (II) a = 23 53 & b = 2m5n, 0 ≤ m & n ≤ 3
    (III) If a = 235n, 0 ≤ n ≤ 2 & b = 2m 53, 0 ≤ m ≤ 3
    Q. Let [r, s] denote the least common multiple of
    positive integers r and s. Find the number ordered
    triples (a, b, c) of positive integers for which [a, b] =
    1000, [b, c] = 2000, and [c, a] =2000

    Answer: (IV) If a = 2m 53, 0 ≤ m ≤ 2 & b = 235n, 0 ≤ n ≤ 3


    70 21+ 9 + 16 + 12 + 12 = 70
    M2
    Let a = 2m5n, b = 2p5q, c = 2r5s
    ATQ. max.(m, p) = max.(n, q) = max.(s, q) = max.(n, s) = 3 and
    max.(p, r) = max.(m, r) = 4
    From above its clear that r = 4.
    Either m = 3 ⇒ p = 0,1,2,3 or p = 3 ⇒ m = 0,1,2
    Q. Let [r, s] denote the least common multiple of
    positive integers r and s. Find the number ordered
    triples (a, b, c) of positive integers for which [a, b] =
    1000, [b, c] = 2000, and [c, a] =2000

    Answer: Either n = q = 3 ⇒ s = 0,1,2,3


    70 or s = q = 3 ⇒ n = 0,1,2
    or s = n = 3 ⇒ q = 0,1,2
    Total 10 combinations.
    Total cases are 7⨯10 = 70
    HOMEWORK QUESTIONS

    SOLUTIONS ATTACHED
    Q. Find the least possible values of a + b, where a and b
    are positive integers such that 11 divides a + 13b and
    13 divides a + 11b
    Q. Find the least possible values of a + b, where a and b
    are positive integers such that 11 divides a + 13b and
    13 divides a + 11b

    Solution:
    Q. The product of two positive integers is 9984 and the
    greatest common factor of those integers equals
    that difference between them. What are the two
    integers?
    Q. The product of two positive integers is 9984 and the
    greatest common factor of those integers equals
    that difference between them. What are the two
    integers?

    Answer: 104, 96

    SOLUTION DISCUSSED IN JUNIOR YT SERIES


    USAMO 1972

    Q. The symbols (a,b,....,g) and [a,b,.....,g] denote the

    greatest common divisor and least common

    multiple, respectively, of the positive integers

    a,b,....,g. For example (3,16,18) = 3 and [6,15] = 30.

    Prove that
    Solution:

    As all of the values in the given equation are positive, we can invert it to get an
    equivalent equation :

    We will now prove that both sides are equal, and that they are integers.
    Consider an arbitrary prime p. Let p𝛂, p𝛽, pℽ be the greatest power of p that divide a,b,
    and c. WLOG let 𝛂 ≤ 𝛽 ≤ ℽ.
    We can now, for each of the expression in our equation, easily determine the largest
    power of p that divides it. In this way we will find that the largest power of p that divides
    the left hand is 𝛽 + ℽ + ℽ – 2ℽ = 𝛽, and the largest power of p that divides the right
    hand side is 𝛂+ 𝛽 + 𝛂 - 2𝛂 = 𝛽.
    IOQM
    PRIME
    2023
    Grade 8 to 12

    Start Date : 01-04-2023


    IOQM PRIME 2023
    Highlights :

    ★ 80+ Live Lectures

    ★ 10 Part Tests

    ★ 5 Full Tests

    ★ Telegram Doubt Solving

    ★ Assignment Video Solutions

    ★ Tests Video Solutions


    IOQM Prime 2023 Batch:

    ❖ 80 Lects and 15 Tests


    ❖ Extra sessions for Basics
    ❖ Telegram Doubt Solving
    ❖ Assignments with Video Solutions Schedule
    ❖ Till IOQM 2023 and beyond
    ❖ Starting from April 1
    ❖ 4 days in a week (MWThF)
    ❖ 3:00 PM-4:30 PM
    IOQM Level

    Basics
    Benefits of Mathematics Olympiad Preparation

    1. Chance to Represent India.

    1. Pre-RMO/INMO Merit Certificates.

    1. Strong Foundation for Competitive Exams like JEE/NEET/KVPY

    1. Confidence to do 'Not Seen Before' Problems.

    1. Improve your Thinking level.


    PRIME
    JUNIORS
    2023
    For Grade 7 & 8 Students

    Start Date : 01-04-2023


    PRIME JUNIORS 2023
    Highlights :

    ★ 40+ Live Lectures

    ★ 10 Part Tests

    ★ 5 Full Tests

    ★ Telegram Doubt Solving

    ★ Assignment Video Solutions

    ★ Tests Video Solutions


    Prime Juniors 2023 Batch:

    ❖ 40 Lects and 15 Tests


    ❖ Telegram Doubt Solving
    ❖ Assignments with Video
    Solutions
    ❖ Till NMTC,IOQM 2023 and Schedule
    beyond
    ❖ Starting from April 1
    ❖ 2 days in a week (Tue, Sat)
    ❖ 3:00 PM-4:30 PM
    Benefits of Prime Juniors- 2023

    1. Strong Foundation in Mathematics Concepts

    1. Confidence to do 'Not Seen Before' Problems.

    1. Cracking Exams like NMTC (Sub Junior) , IOQM (if eligible) and later
    JEE/NEET/Senior Olympiads.

    1. Improve your Thinking level.

    1. Building confidence and networking.


    Let’s Bring
    GOLD
    For
    INDIA

    You might also like