PRMO L6 - Properties of GCD, LCM

ABHAY MAHAJAN
B.Tech. IIT Roorkee

➔ 12+ years teaching experience
➔ Mentored and taught around 20000+ students
➔ Produced 400+ IIT selections
➔ 15+ INMO selections
➔ 2 EGMO Selection
FOR
MATHEMATICS OLYMPIADS
ISI KVPY CMI

WHAT DO YOU GET?
A detailed Number Theory course targeting exams viz. Topics to be covered:

PRMO | RMO | INMO | KVPY | ISI | CMI
★ Base Systems
A chance to learn beyond school curriculum in Mathematics ★ Perfect Squares
★ Congruence
Focus on laying a strong foundation and concept
★ Diophantine Equations
building in important Number Theory topics
★ Chinese Remainder
Theorem
Learning with India’s Top Mathematics experts
★ GCD
★ Fermat and Wilson
Daily session assignments Theorem
ABMPRO
WHAT DO YOU GET?
Target exams like

PRMO | RMO | INMO | KVPY | ISI
A chance to learn beyond school curriculum in Mathematics
Strengthen your foundation and concept

building in Geometry
Learning with India’s Top Math Teachers
Daily session assignments for practice
A short course of 36 sessions to save your time & energy

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
GCD and LCM
★ 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.
Coprime Numbers
● Any two consecutive integers are coprime.

● Further, 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) = k then
a = kp, b =kr
where p, r are coprime
4. If GCD(a, b) = 1 then
GCD(a + b, ab) = 1
5. GCD(GCD(m, n), p) = GCD(m, GCD(n, p));
Q. For two positive integers, the LCM is 225
and HCF is 15. There
A. is exactly one such pair
B. are exactly two such pairs
C. are exactly three such pairs
D. are exactly four such pairs

Q. For two positive integers, the LCM is 225
and HCF is 15. There
A. is exactly one such pair
B. are exactly two such pairs
C. are exactly three such pairs
D. are exactly four such pairs

Q. For positive x and y, the LCM is 225 and
HCF is 15. There
Solution: Let numbers be 15a and 15b
Then 15ab = 225

⇒ ab = 15
Either a = 15, b =1
Or a = 3, b = 5
Hence (x, y) = (225, 15) or (45, 75)
Q. Find the GCD of the numbers
2n + 13 and n + 7.
Q. Find the GCD of the numbers
2n + 13 and n + 7.
Solution:
We have gcd(2n + 13, n + 7) = gcd (n + 7, n + 6)

= gcd (n + 6, 1)
=1
Q. Three numbers which are coprime to each other are
such that the product of first two is 551 and that of the
last two is 1073. The sum of the three numbers is
A. 75
B. 81
C. 85
D. 89
A. 75
B. 81
C. 85
D. 89
Solution:
Since the numbers are coprime, 1 is the common factor.

Also, given two products have middle number in common.
So, the middle number = HCF of 551 and 1073 = 29
First number = (551/29) = 19
Third number = (1073/29) = 37
So, required sum = 19 + 29 + 37 = 85
JBMO 2001
Q. Find the greatest common divisor of the numbers
An = 23n + 36n+2 + 56n+2
When n = 0,1,...,1999
Solution:
We have
A0 = 1 + 9 + 25 = 35 = 5.7.
Using congruence mod 5, it follows that
An≡ 23n + 36n+2 ≡ 23n + 93n+1 ≡ 23n + (-1)3n+1 (mod 5)
For n = 1, A1 ≡ 9 ≠ 0 (mod 5), hence 5 is not common divisor
On the other hand,
An = 8n + 9.93n + 25.253n
≡ 1 + 2 .23n + 4 . 43n
≡ 1 + 2 . 8n + 4 . 64n
≡ 1 + 2 . 1n + 4 . 1n
≡ 0 (mod 7)
therefore 7 divides An, for all integers n ≥ 0
Consequently, the greatest common divisor of the number A0, A1,.....A1999 is equal to 7.
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
Q.
a.b +63 =20.lcm(a, b) +12.gcd(a, b)
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
Q.
a.b +63 =20.lcm(a, b) +12.gcd(a, b)
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
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.
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𝛂 = 𝛽.
FOR
MATHEMATICS OLYMPIADS
ISI KVPY CMI

WHAT DO YOU GET?
A detailed Number Theory course targeting exams viz. Topics to be covered:

PRMO | RMO | INMO | KVPY | ISI | CMI
★ Base Systems
A chance to learn beyond school curriculum in Mathematics ★ Perfect Squares
★ Congruence
Focus on laying a strong foundation and concept
★ Diophantine Equations
building in important Number Theory topics
★ Chinese Remainder
Theorem
Learning with India’s Top Mathematics experts
★ GCD
★ Fermat and Wilson
Daily session assignments Theorem
ABMPRO
WHAT DO YOU GET?
Target exams like

PRMO | RMO | INMO | KVPY | ISI
A chance to learn beyond school curriculum in Mathematics
Strengthen your foundation and concept

building in Geometry
Learning with India’s Top Math Teachers
Daily session assignments for practice
A short course of 36 sessions to save your time & energy

Pre-RMO Level
Basics
If you liked the session, then

PRMO L6 - Properties of GCD, LCM

Uploaded by

Copyright:

Available Formats

PRMO L6 - Properties of GCD, LCM

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

PRMO L6 - Properties of GCD, LCM

Uploaded by

Copyright:

Available Formats

ABHAY MAHAJAN

B.Tech. IIT Roorkee

ISI KVPY CMI

A detailed Number Theory course targeting exams viz. Topics to be covered:

Target exams like

A chance to learn beyond school curriculum in Mathematics

Strengthen your foundation and concept

Learning with India’s Top Math Teachers

Daily session assignments for practice

A short course of 36 sessions to save your time & energy

★ Greatest Common Divisor:

★ Least Common Multiple:

● Any two consecutive integers are coprime.

A. is exactly one such pair

B. are exactly two such pairs

C. are exactly three such pairs

D. are exactly four such pairs

A. is exactly one such pair

B. are exactly two such pairs

C. are exactly three such pairs

D. are exactly four such pairs

Solution: Let numbers be 15a and 15b

Then 15ab = 225

We have gcd(2n + 13, n + 7) = gcd (n + 7, n + 6)

Since the numbers are coprime, 1 is the common factor.

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

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

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

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

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.

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.

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.

ISI KVPY CMI

A detailed Number Theory course targeting exams viz. Topics to be covered:

Target exams like

A chance to learn beyond school curriculum in Mathematics

Strengthen your foundation and concept

Learning with India’s Top Math Teachers

Daily session assignments for practice

A short course of 36 sessions to save your time & energy

You might also like