Tag: GCD

Categories
Math Olympiad PRMO USA Math Olympiad

Ordered Pairs | PRMO-2019 | Problem 18

Try this beautiful problem from PRMO, 2019, Problem 18 based on Ordered Pairs.

Orderd Pairs | PRMO | Problem-18

How many ordered pairs \((a, b)\) of positive integers with \(a < b\) and \(100 \leq a\), \(b \leq 1000\) satisfy \(gcd (a, b) : lcm (a, b) = 1 : 495\) ?

  • $20$
  • $91$
  • $13$
  • \(23\)

Key Concepts

Number theory

Orderd Pair

LCM

Check the Answer

Answer:\(20\)

PRMO-2019, Problem 18

Pre College Mathematics

Try with Hints

At first we assume that \( a = xp\)
\(b = xq\)
where \(p\) & \(q\) are co-prime

Therefore ,

\(\frac{gcd(a,b)}{LCM(a ,b)} =\frac{495}{1}\)

\(\Rightarrow pq=495\)
Can you now finish the problem ……….

Therefore we can say that

\(pq = 5 \times 9 \times 11\)
\(p < q\)

when \( 5 < 99\) (for \(x = 20, a = 100, b = 1980 > 100\)),No solution
when \(9 < 55\) \((x = 12\) to \(x = 18)\),7 solution
when,\(11 < 45\) \((x = 10\) to \(x = 22)\),13 solution
Can you finish the problem……..

Therefore Total solutions = \(13 + 7=20\)

Other useful links

Related Program

Subscribe to Cheenta at Youtube

Categories
AIME I Algebra Arithmetic Coordinate Geometry Math Olympiad USA Math Olympiad

GCD and Ordered pair | AIME I, 1995 | Question 8

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1995 based on GCD and Ordered pair.

GCD and Ordered pair – AIME I, 1995

Find number of ordered pairs of positive integers (x,y) with \(y \lt x \leq 100\) are both \(\frac{x}{y}\) and \(\frac{x+1}{y+1}\) integers.

  • is 107
  • is 85
  • is 840
  • cannot be determined from the given information

Key Concepts

Integers

GCD

Ordered pair

Check the Answer

Answer: is 85.

AIME I, 1995, Question 8

Elementary Number Theory by David Burton

Try with Hints

here y|x and (y+1)|(x+1) \(\Rightarrow gcd(y,x)=y, gcd(y+1,x+1)=y+1\)

\(\Rightarrow gcd(y,x-y)=y, gcd(y+1,x-y)=y+1\)

\(\Rightarrow y,y+1|(x-y) and gcd (y,y+1)=1\)

\(\Rightarrow y(y+1)|(x-y)\)

here number of multiples of y(y+1) from 0 to 100-y \((x \leq 100)\) are

[\(\frac{100-y}{y(y+1)}\)]

\(\Rightarrow \displaystyle\sum_{y=1}^{99}[\frac{100-y}{y(y+1)}\)]=49+16+8+4+3+2+1+1+1=85.

Other useful links

Related Program

Subscribe to Cheenta at Youtube

Categories
AIME I Algebra Arithmetic Math Olympiad USA Math Olympiad

GCD and Sequence | AIME I, 1985 | Question 13

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1985 based on GCD and Sequence.

GCD and Sequence – AIME I, 1985

The numbers in the sequence 101, 104,109,116,…..are of the form \(a_n=100+n^{2}\) where n=1,2,3,——-, for each n, let \(d_n\) be the greatest common divisor of \(a_n\) and \(a_{n+1}\), find the maximum value of \(d_n\) as n ranges through the positive integers.

  • is 107
  • is 401
  • is 840
  • cannot be determined from the given information

Key Concepts

GCD

Sequence

Integers

Check the Answer

Answer: is 401.

AIME I, 1985, Question 13

Elementary Number Theory by David Burton

Try with Hints

\(a_n=100+n^{2}\) \(a_{n+1}=100+(n+1)^{2}=100 + n^{2} +2n +1\) and \(a_{n+1}-a_{n}=2n +1\)

\(d_{n}|(2n+1)\) and \(d_{n}|(100 +n^{2})\) then \(d_{n}|[(100+n^{2})-100(2n+1)]\) then \(d_{n}|(n^{2}-200n)\)

here \(n^{2} -200n=0\) then n=200 then \(d_{n}\)=2n+1=2(200)+1=401.

Other useful links

Related Program

Subscribe to Cheenta at Youtube

Categories
AMC 8 Math Olympiad USA Math Olympiad

Problem based on LCM | AMC 8, 2016 | Problem 20

Try this beautiful problem from Algebra based on LCM from AMC-8, 2016.

Problem based on LCM – AMC 8, 2016

The least common multiple of $a$ and $b$ is $12$, and the least common multiple of $b$ and $c$ is $15$. What is the least possible value of the least common multiple of $a$ and $c$?

  • \(26\)
  • \(20\)
  • \(28\)

Key Concepts

Algebra

Divisor

multiplication

Check the Answer

Answer:20

AMC-8, 2016 problem 20

Challenges and Thrills of Pre College Mathematics

Try with Hints

We have to find out the least common multiple of $a$ and $c$.if you know the value of \(a\) and \(c\) then you can easily find out the required LCM. Can you find out the value of \(a\) and \(c\)?

Can you now finish the problem ……….

Given that the least common multiple of $a$ and $b$ is $12$, and the least common multiple of $b$ and $c$ is $15$ .then b must divide 12 and 15. There is only one possibility that b=3 which divide 12 and 15. therefore \(a\)=\(\frac{12}{3}=4\)

can you finish the problem……..

so\(b\)=3. Given that LCM of \(b\) and \(c\) is 15. Therefore c=5

Now lcm of \(a\) and \(c\) that is lcm of 4 and 5=20

Other useful links

Related Program

Subscribe to Cheenta at Youtube