This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 583

2003 Italy TST, 1
Tags: greatest common divisor , circumcircle , geometry
The incircle of a triangle $ABC$ touches the sides $AB,BC,CA$ at points $D,E,F$ respectively. The line through $A$ parallel to $DF$ meets the line through $C$ parallel to $EF$ at $G$. $(a)$ Prove that the quadrilateral $AICG$ is cyclic. $(b)$ Prove that the points $B,I,G$ are collinear.

PEN L Problems, 2
Tags: linear recurrence , number theory , greatest common divisor
The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $\gcd (F_{m}, F_{n})=F_{\gcd (m, n)}$ for all $m, n \in \mathbb{N}$.

2015 Indonesia MO Shortlist, N4
Tags: number theory , exponential equation , exponential , greatest common divisor , diophantine equation
Suppose that the natural number $a, b, c, d$ satisfy the equation $a^ab^{a + b} = c^cd^{c + d}$. (a) If gcd $(a, b) = $ gcd $(c, d) = 1$, prove that $a = c$ and $b = d$. (b) Does the conclusion $a = c$ and $b = d$ apply, without the condition gcd $(a, b) = $ gcd $(c, d) = 1$?

1995 AMC 12/AHSME, 27
Tags: modular arithmetic , number theory , greatest common divisor , arithmetic series
Consider the triangular array of numbers with $0,1,2,3,...$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows $1$ through $6$ are shown. \begin{tabular}{ccccccccccc} & & & & & 0 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 2 & & 2 & & 2 & & & \\ & & 3 & & 4 & & 4 & & 3 & & \\ & 4 & & 7 & & 8 & & 7 & & 4 & \\ 5 & & 11 & & 15 & & 15 & & 11 & & 5 \end{tabular} Let $f(n)$ denote the sum of the numbers in row $n$. What is the remainder when $f(100)$ is divided by $100$? $\textbf{(A)}\ 12\qquad \textbf{(B)}\ 30 \qquad \textbf{(C)}\ 50 \qquad \textbf{(D)}\ 62 \qquad \textbf{(E)}\ 74$

2008 ISI B.Stat Entrance Exam, 9
Tags: number theory , least common multiple , greatest common divisor
Suppose $S$ is the set of all positive integers. For $a,b \in S$, define \[a * b=\frac{\text{lcm}[a,b]}{\text{gcd}(a,b)}\] For example $8*12=6$. Show that [b]exactly two[/b] of the following three properties are satisfied: (i) If $a,b \in S$, then $a*b \in S$. (ii) $(a*b)*c=a*(b*c)$ for all $a,b,c \in S$. (iii) There exists an element $i \in S$ such that $a *i =a$ for all $a \in S$.

2011 South East Mathematical Olympiad, 2
Tags: greatest common divisor , number theory
If positive integers, $a,b,c$ are pair-wise co-prime, and, \[\ a^2|(b^3+c^3), b^2|(a^3+c^3), c^2|(a^3+b^3) \] find $a,b,$ and $c$

2007 Singapore Junior Math Olympiad, 4
Tags: number theory , greatest common divisor , least common multiple , sum , difference , product
The difference between the product and the sum of two different integers is equal to the sum of their GCD (greatest common divisor) and LCM (least common multiple). Findall these pairs of numbers. Justify your answer.

1994 Tournament Of Towns, (422) 3
Tags: number theory , greatest common divisor
Find five positive integers such that the greatest common divisor of each pair is equal to the difference between them. (SI Tokarev)

1973 Poland - Second Round, 6
Tags: number theory , greatest common divisor
Prove that for every non-negative integer $m$ there exists a polynomial w with integer coefficients such that $2^m$ is the greatest common divisor of the numbers $$ a_n = 3^n + w(n), n = 0, 1, 2, ....$$

2008 Putnam, B5
Tags: function , number theory , greatest common divisor , calculus , derivative , integration
Find all continuously differentiable functions $ f: \mathbb{R}\to\mathbb{R}$ such that for every rational number $ q,$ the number $ f(q)$ is rational and has the same denominator as $ q.$ (The denominator of a rational number $ q$ is the unique positive integer $ b$ such that $ q\equal{}a/b$ for some integer $ a$ with $ \gcd(a,b)\equal{}1.$) (Note: $ \gcd$ means greatest common divisor.)

2014 Korea National Olympiad, 1
Tags: greatest common divisor , number theory
For $x, y$ positive integers, $x^2-4y+1$ is a multiple of $(x-2y)(1-2y)$. Prove that $|x-2y|$ is a square number.

Russian TST 2016, P2
Tags: greatest common divisor , combinatorics
For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

2012 Federal Competition For Advanced Students, Part 1, 1
Tags: function , greatest common divisor , geometry , geometric transformation , number theory
Determine all functions $f: \mathbb{Z}\to\mathbb{Z}$ satisfying the following property: For each pair of integers $m$ and $n$ (not necessarily distinct), $\mathrm{gcd}(m, n)$ divides $f(m) + f(n)$. Note: If $n\in\mathbb{Z}$, $\mathrm{gcd}(m, n)=\mathrm{gcd}(|m|, |n|)$ and $\mathrm{gcd}(n, 0)=n$.

2007 AIME Problems, 8
Tags: polynomial , quadratic , number theory , greatest common divisor , algorithm , least common multiple , algebra
The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$?

2014 Romania Team Selection Test, 4
Tags: greatest common divisor , function , number theory
Let $n$ be a positive integer and let $A_n$ respectively $B_n$ be the set of nonnegative integers $k<n$ such that the number of distinct prime factors of $\gcd(n,k)$ is even (respectively odd). Show that $|A_n|=|B_n|$ if $n$ is even and $|A_n|>|B_n|$ if $n$ is odd. Example: $A_{10} = \left\{ 0,1,3,7,9 \right\}$, $B_{10} = \left\{ 2,4,5,6,8 \right\}$.

2003 Balkan MO, 1
Tags: pigeonhole principle , algebra , polynomial , induction , number theory , greatest common divisor
Can one find 4004 positive integers such that the sum of any 2003 of them is not divisible by 2003?

2008 ISI B.Stat Entrance Exam, 8
Tags: number theory , greatest common divisor
In how many ways can you divide the set of eight numbers $\{2,3,\cdots,9\}$ into $4$ pairs such that no pair of numbers has $\text{gcd}$ equal to $2$?

2014 India PRMO, 11
Tags: number theory , greatest common divisor
For natural numbers $x$ and $y$, let $(x,y)$ denote the greatest common divisor of $x$ and $y$. How many pairs of natural numbers $x$ and $y$ with $x \le y$ satisfy the equation $xy = x + y + (x, y)$?

2007 Tournament Of Towns, 2
Tags: greatest common divisor , least common multiple , combinatorics
[b](a)[/b] Each of Peter and Basil thinks of three positive integers. For each pair of his numbers, Peter writes down the greatest common divisor of the two numbers. For each pair of his numbers, Basil writes down the least common multiple of the two numbers. If both Peter and Basil write down the same three numbers, prove that these three numbers are equal to each other. [b](b)[/b] Can the analogous result be proved if each of Peter and Basil thinks of four positive integers instead?

2004 Korea - Final Round, 2
Tags: quadratic , greatest common divisor , number theory
Prove that the equation $3y^2 = x^4 + x$ has no positive integer solutions.

2005 ITAMO, 3
Tags: circumcircle , incenter , greatest common divisor , angle bisector , geometry
Two circles $\gamma_1, \gamma_2$ in a plane, with centers $A$ and $B$ respectively, intersect at $C$ and $D$. Suppose that the circumcircle of $ABC$ intersects $\gamma_1$ in $E$ and $\gamma_2$ in $F$, where the arc $EF$ not containing $C$ lies outside $\gamma_1$ and $\gamma_2$. Prove that this arc $EF$ is bisected by the line $CD$.

2025 Belarusian National Olympiad, 10.4
Tags: number theory , greatest common divisor
Is it possible to assign every integral point $(x,y)$ of the plane a positive integer $a_{x,y}$ such that for every two integers $i$ and $j$ the following equality holds $$a_{i,j}=\gcd(a_{i-1,j},a_{i+1,j})+\gcd(a_{i,j-1},a_{i,j+1})$$ [i]M. Shutro[/i]

2019 CMIMC, 2
Tags: number theory , greatest common divisor , team
Determine the number of ordered pairs of positive integers $(m,n)$ with $1\leq m\leq 100$ and $1\leq n\leq 100$ such that \[ \gcd(m+1,n+1) = 10\gcd(m,n). \]

2019 Dutch BxMO TST, 4
Tags: gcd , number theory , greatest common divisor , sequence
Do there exist a positive integer $k$ and a non-constant sequence $a_1, a_2, a_3, ...$ of positive integers such that $a_n = gcd(a_{n+k}, a_{n+k+1})$ for all positive integers $n$?

1996 Baltic Way, 8
Tags: number theory , greatest common divisor , least common multiple
Consider the sequence: $x_1=19,x_2=95,x_{n+2}=\text{lcm} (x_{n+1},x_n)+x_n$, for $n>1$, where $\text{lcm} (a,b)$ means the least common multiple of $a$ and $b$. Find the greatest common divisor of $x_{1995}$ and $x_{1996}$.