Olympiad problems

2012 Bulgaria National Olympiad, 2

Prove that the natural numbers can be divided into two groups in a way that both conditions are fulfilled: 1) For every prime number $p$ and every natural number $n$, the numbers $p^n,p^{n+1}$ and $p^{n+2}$ do not have the same colour. 2) There does not exist an infinite geometric sequence of natural numbers of the same colour.

2005 AIME Problems, 2

Tags: arithmetic sequence , prime factorization , number theory

For each positive integer $k$, let $S_k$ denote the increasing arithmetic sequence of integers whose first term is $1$ and whose common difference is $k$. For example, $S_3$ is the sequence $1,4,7,10,...$. For how many values of $k$ does $S_k$ contain the term $2005$?

1977 IMO, 3

Tags: number theory , prime number , dirichlet s theorem , prime factorization

Let $n$ be a given number greater than 2. We consider the set $V_n$ of all the integers of the form $1 + kn$ with $k = 1, 2, \ldots$ A number $m$ from $V_n$ is called indecomposable in $V_n$ if there are not two numbers $p$ and $q$ from $V_n$ so that $m = pq.$ Prove that there exist a number $r \in V_n$ that can be expressed as the product of elements indecomposable in $V_n$ in more than one way. (Expressions which differ only in order of the elements of $V_n$ will be considered the same.)

2013 AMC 10, 20

Tags: prime factorization , induction , number theory , factorial

The number $2013$ is expressed in the form \[2013=\frac{a_1!a_2!\cdots a_m!}{b_1!b_2!\cdots b_n!},\] where $a_1\ge a_2\ge\cdots\ge a_m$ and $b_1\ge b_2\ge\cdots\ge b_n$ are positive integers and $a_1+b_1$ is as small as possible. What is $|a_1-b_1|$? ${ \textbf{(A)}\ 1\qquad\textbf{(B)}\ 2\qquad\textbf{(C)}\ 3\qquad\textbf{(D}}\ 4\qquad\textbf{(E)}\ 5 $

2022 IMO Shortlist, N6

Tags: prime , prime number , number theory , prime factorization , function

Let $Q$ be a set of prime numbers, not necessarily finite. For a positive integer $n$ consider its prime factorization: define $p(n)$ to be the sum of all the exponents and $q(n)$ to be the sum of the exponents corresponding only to primes in $Q$. A positive integer $n$ is called [i]special[/i] if $p(n)+p(n+1)$ and $q(n)+q(n+1)$ are both even integers. Prove that there is a constant $c>0$ independent of the set $Q$ such that for any positive integer $N>100$, the number of special integers in $[1,N]$ is at least $cN$. (For example, if $Q=\{3,7\}$, then $p(42)=3$, $q(42)=2$, $p(63)=3$, $q(63)=3$, $p(2022)=3$, $q(2022)=1$.)

2016 BAMO, 3

Tags: prime factorization , prime factor , factor , number theory

The ${\textit{distinct prime factors}}$ of an integer are its prime factors listed without repetition. For example, the distinct prime factors of $40$ are $2$ and $5$. Let $A=2^k - 2$ and $B= 2^k \cdot A$, where $k$ is an integer ($k \ge 2$). Show that, for every integer $k$ greater than or equal to $2$, [list=i] [*] $A$ and $B$ have the same set of distinct prime factors. [*] $A+1$ and $B+1$ have the same set of distinct prime factors. [/list]

2021 Azerbaijan Senior NMO, 1

Tags: prime factorization , number theory , factorial

At least how many numbers must be deleted from the product $1 \times 2 \times \dots \times 46 \times 47$ in order to make it a perfect square?

2021 Thailand TSTST, 1

Tags: prime factorization , divisor , number theory

For each positive integer $n$, let $\rho(n)$ be the number of positive divisors of $n$ with exactly the same set of prime divisors as $n$. Show that, for any positive integer $m$, there exists a positive integer $n$ such that $\rho(202^n+1)\geq m.$

2017 SDMO (High School), 2

Tags: prime factorization , number theory

There are $5$ accents in French, each applicable to only specific letters as follows: [list] [*] The cédille: ç [*] The accent aigu: é [*] The accent circonflexe: â, ê, î, ô, û [*] The accent grave: à, è, ù [*] The accent tréma: ë, ö, ü [/list] Cédric needs to write down a phrase in French. He knows that there are $3$ words in the phrase and that the letters appear in the order: \[cesontoiseaux.\] He does not remember what the words are and which letters have what accents in the phrase. If $n$ is the number of possible phrases that he could write down, then determine the number of distinct primes in the prime factorization of $n$.

2010 Purple Comet Problems, 2

Tags: prime factorization , number theory

The prime factorization of $12 = 2 \cdot 2 \cdot 3$ has three prime factors. Find the number of prime factors in the factorization of $12! = 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1.$

2018 Canadian Mathematical Olympiad Qualification, 7

Tags: prime factorization , polynomial , number theory , algebra

Let $n$ be a positive integer, with prime factorization $$n = p_1^{e_1}p_2^{e_2} \cdots p_r^{e_r}$$ for distinct primes $p_1, \ldots, p_r$ and $e_i$ positive integers. Define $$rad(n) = p_1p_2\cdots p_r,$$ the product of all distinct prime factors of $n$. Find all polynomials $P(x)$ with rational coefficients such that there exists infinitely many positive integers $n$ with $P(n) = rad(n)$.

2007 China Girls Math Olympiad, 1

Tags: prime factorization , number theory

A positive integer $ m$ is called [i]good[/i] if there is a positive integer $ n$ such that $ m$ is the quotient of $ n$ by the number of positive integer divisors of $ n$ (including $ 1$ and $ n$ itself). Prove that $ 1, 2, \ldots, 17$ are good numbers and that $ 18$ is not a good number.

2023 Brazil Team Selection Test, 3

Tags: prime factorization , prime number , prime , function , number theory

Let $Q$ be a set of prime numbers, not necessarily finite. For a positive integer $n$ consider its prime factorization: define $p(n)$ to be the sum of all the exponents and $q(n)$ to be the sum of the exponents corresponding only to primes in $Q$. A positive integer $n$ is called [i]special[/i] if $p(n)+p(n+1)$ and $q(n)+q(n+1)$ are both even integers. Prove that there is a constant $c>0$ independent of the set $Q$ such that for any positive integer $N>100$, the number of special integers in $[1,N]$ is at least $cN$. (For example, if $Q=\{3,7\}$, then $p(42)=3$, $q(42)=2$, $p(63)=3$, $q(63)=3$, $p(2022)=3$, $q(2022)=1$.)

2010 Junior Balkan MO, 2

Tags: induction , prime factorization , inequalities , number theory

Find all integers $n$, $n \ge 1$, such that $n \cdot 2^{n+1}+1$ is a perfect square.

2004 Mediterranean Mathematics Olympiad, 1

Tags: prime factorization , factorial , number theory , inequalities

Find all natural numbers $m$ such that \[1! \cdot 3! \cdot 5! \cdots (2m-1)! = \biggl( \frac{m(m+1)}{2}\biggr) !.\]

2013 USAMTS Problems, 4

Tags: inequalities , prime factorization , arithmetic sequence , modular arithmetic , relatively prime , number theory

Bunbury the bunny is hopping on the positive integers. First, he is told a positive integer $n$. Then Bunbury chooses positive integers $a,d$ and hops on all of the spaces $a,a+d,a+2d,\dots,a+2013d$. However, Bunbury must make these choices so that the number of every space that he hops on is less than $n$ and relatively prime to $n$. A positive integer $n$ is called [i]bunny-unfriendly[/i] if, when given that $n$, Bunbury is unable to find positive integers $a,d$ that allow him to perform the hops he wants. Find the maximum bunny-unfriendly integer, or prove that no such maximum exists.

1997 IMO, 5

Tags: prime factorization , equation , number theory

Find all pairs $ (a,b)$ of positive integers that satisfy the equation: $ a^{b^2} \equal{} b^a$.

2019 Tournament Of Towns, 1

Tags: number of divisors , divisor , factor , prime factorization , inequalities , prime , number theory

Let us call the number of factors in the prime decomposition of an integer $n > 1$ the complexity of $n$. For example, [i]complexity [/i] of numbers $4$ and $6$ is equal to $2$. Find all $n$ such that all integers between $n$ and $2n$ have complexity a) not greater than the complexity of $n$. b) less than the complexity of $n$. (Boris Frenkin)

1985 Canada National Olympiad, 4

Tags: prime factorization , logarithm , inequalities , number theory , floor function

Prove that $2^{n - 1}$ divides $n!$ if and only if $n = 2^{k - 1}$ for some positive integer $k$.

2022 OMpD, 1

Tags: phi function , prime factorization , function , number theory

Given a positive integer $n \geq 2$, whose canonical prime factorization is $n = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}$, we define the following functions: $$\varphi(n) = n\bigg(1 -\frac{1}{p_1}\bigg) \bigg(1 -\frac{1}{p_2}\bigg) \ldots \bigg(1 -\frac {1}{p_k}\bigg) ; \overline{\varphi}(n) = n\bigg(1 +\frac{1}{p_1}\bigg) \bigg(1 +\frac{1}{p_2}\bigg) \ldots \bigg(1 + \frac{1}{p_k}\bigg)$$ Consider all positive integers $n$ such that $\overline{\varphi}(n)$ is a multiple of $n + \varphi(n) $. (a) Prove that $n$ is even. (b) Determine all positive integers $n$ that satisfy this property.

2000 Baltic Way, 14

Tags: prime factorization , function , induction , number theory , inequalities

Find all positive integers $n$ such that $n$ is equal to $100$ times the number of positive divisors of $n$.

2007 Princeton University Math Competition, 1

Tags: prime factorization , number theory

If you multiply all positive integer factors of $24$, you get $24^x$. Find $x$.

1973 AMC 12/AHSME, 19

Tags: function , prime factorization , number theory

Define $ n_a!$ for $ n$ and $ a$ positive to be \[ n_a ! \equal{} n (n\minus{}a)(n\minus{}2a)(n\minus{}3a)...(n\minus{}ka)\] where $ k$ is the greatest integer for which $ n>ka$. Then the quotient $ 72_8!/18_2!$ is equal to $ \textbf{(A)}\ 4^5 \qquad \textbf{(B)}\ 4^6 \qquad \textbf{(C)}\ 4^8 \qquad \textbf{(D)}\ 4^9 \qquad \textbf{(E)}\ 4^{12}$

2006 AIME Problems, 4

Tags: factorial , number theory , prime factorization

Let $N$ be the number of consecutive 0's at the right end of the decimal representation of the product $1!\times2!\times3!\times4!\cdots99!\times100!.$ Find the remainder when $N$ is divided by 1000.

2003 Putnam, 3

Tags: least common multiple , prime factorization , number theory , floor function

Show that for each positive integer n, \[n!=\prod_{i=1}^n \; \text{lcm} \; \{1, 2, \ldots, \left\lfloor\frac{n}{i} \right\rfloor\}\] (Here lcm denotes the least common multiple, and $\lfloor x\rfloor$ denotes the greatest integer $\le x$.)