Olympiad problems

2004 AIME Problems, 10

Let $S$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$'s. If a number is chosen at random from $S$, the probability that it is divisible by $9$ is $p/q$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.

2009 Indonesia TST, 4

Tags: combinatorics , modular arithmetic

2008 boys and 2008 girls sit on 4016 chairs around a round table. Each boy brings a garland and each girl brings a chocolate. In an "activity", each person gives his/her goods to the nearest person on the left. After some activities, it turns out that all boys get chocolates and all girls get garlands. Find the number of possible arrangements.

PEN H Problems, 58

Tags: diophantine equation , algorithm , modular arithmetic

Solve in positive integers the equation $10^{a}+2^{b}-3^{c}=1997$.

PEN A Problems, 72

Tags: divisibility theory , modular arithmetic , number theory

Determine all pairs $(n,p)$ of nonnegative integers such that [list] [*] $p$ is a prime, [*] $n<2p$, [*] $(p-1)^{n} + 1$ is divisible by $n^{p-1}$. [/list]

2008 Germany Team Selection Test, 1

Tags: floor function , modular arithmetic , inequalities

Show that there is a digit unequal to 2 in the decimal represesentation of $ \sqrt [3]{3}$ between the $ 1000000$-th und $ 3141592$-th position after decimal point.

1998 USAMTS Problems, 2

Tags: prime factorization , modular arithmetic , number theory

For a nonzero integer $i$, the exponent of $2$ in the prime factorization of $i$ is called $ord_2 (i)$. For example, $ord_2(9)=0$ since $9$ is odd, and $ord_2(28)=2$ since $28=2^2\times7$. The numbers $3^n-1$ for $n=1,2,3,\ldots$ are all even so $ord_2(3^n-1)>0$ for $n>0$. a) For which positive integers $n$ is $ord_2(3^n-1) = 1$? b) For which positive integers $n$ is $ord_2(3^n-1) = 2$? c) For which positive integers $n$ is $ord_2(3^n-1) = 3$? Prove your answers.

1989 IMO Shortlist, 27

Tags: modular arithmetic , least common multiple , divisibility , number theory

Let $ m$ be a positive odd integer, $ m > 2.$ Find the smallest positive integer $ n$ such that $ 2^{1989}$ divides $ m^n \minus{} 1.$

2008 Junior Balkan MO, 3

Tags: number theory , algorithm , modular arithmetic

Find all prime numbers $ p,q,r$, such that $ \frac{p}{q}\minus{}\frac{4}{r\plus{}1}\equal{}1$

1993 All-Russian Olympiad, 1

Tags: modular arithmetic , parameterization , quadratic , number theory

For integers $x$, $y$, and $z$, we have $(x-y)(y-z)(z-x)=x+y+z$. Prove that $27|x+y+z$.

2002 China Team Selection Test, 3

Tags: modular arithmetic , number theory , induction

Find all groups of positive integers $ (a,x,y,n,m)$ that satisfy $ a(x^n \minus{} x^m) \equal{} (ax^m \minus{} 4) y^2$ and $ m \equiv n \pmod{2}$ and $ ax$ is odd.

2006 Baltic Way, 20

Tags: number theory , modular arithmetic

A $12$-digit positive integer consisting only of digits $1,5$ and $9$ is divisible by $37$. Prove that the sum of its digits is not equal to $76$.

2012 Online Math Open Problems, 26

Tags: modular arithmetic , least common multiple , number theory , logarithm , algebra , floor function

Find the smallest positive integer $k$ such that \[\binom{x+kb}{12} \equiv \binom{x}{12} \pmod{b}\] for all positive integers $b$ and $x$. ([i]Note:[/i] For integers $a,b,c$ we say $a \equiv b \pmod c$ if and only if $a-b$ is divisible by $c$.) [i]Alex Zhu.[/i] [hide="Clarifications"][list=1][*]${{y}\choose{12}} = \frac{y(y-1)\cdots(y-11)}{12!}$ for all integers $y$. In particular, ${{y}\choose{12}} = 0$ for $y=1,2,\ldots,11$.[/list][/hide]

2014 ELMO Shortlist, 10

Tags: geometry , number theory , 3d geometry , modular arithmetic

Find all positive integer bases $b \ge 9$ so that the number \[ \frac{{\overbrace{11 \cdots 1}^{n-1 \ 1's}0\overbrace{77 \cdots 7}^{n-1\ 7's}8\overbrace{11 \cdots 1}^{n \ 1's}}_b}{3} \] is a perfect cube in base 10 for all sufficiently large positive integers $n$. [i]Proposed by Yang Liu[/i]

2023 China Western Mathematical Olympiad, 4

Tags: number theory , modular arithmetic

Let ${p}$ be a prime. $a,b,c\in\mathbb Z,\gcd(a,p)=\gcd(b,p)=\gcd(c,p)=1.$ Prove that: $\exists x_1,x_2,x_3,x_4\in\mathbb Z,| x_1|,|x_2|,|x_3|,|x_4|<\sqrt p,$ satisfying $$ax_1x_2+bx_3x_4\equiv c\pmod p.$$ [i]Proposed by Wang Guangting[/i]

1996 Singapore Team Selection Test, 2

Tags: number theory , modular arithmetic , algebra

Let $ k$ be a positive integer. Show that there are infinitely many perfect squares of the form $ n \cdot 2^k \minus{} 7$ where $ n$ is a positive integer.

1989 IMO Shortlist, 30

Tags: prime number , sequence , power of number , modular arithmetic , number theory

Prove that for each positive integer $ n$ there exist $ n$ consecutive positive integers none of which is an integral power of a prime number.

1975 AMC 12/AHSME, 15

Tags: modular arithmetic

In the sequence of numbers 1, 3, 2, ... each term after the first two is equal to the term preceding it minus the term preceding that. The sum of the first one hundred terms of the sequence is $ \textbf{(A)}\ 5 \qquad \textbf{(B)}\ 4 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 1 \qquad \textbf{(E)}\ \minus{}1$

2006 China Team Selection Test, 3

Tags: polynomial , linear algebra , vector , number theory , greatest common divisor , algebra , modular arithmetic

Let $a_{i}$ and $b_{i}$ ($i=1,2, \cdots, n$) be rational numbers such that for any real number $x$ there is: \[x^{2}+x+4=\sum_{i=1}^{n}(a_{i}x+b)^{2}\] Find the least possible value of $n$.

2008 Junior Balkan Team Selection Tests - Romania, 1

Tags: number theory , logarithm , modular arithmetic , induction

Let $ p$ be a prime number, $ p\not \equal{} 3$, and integers $ a,b$ such that $p\mid a+b$ and $ p^2\mid a^3 \plus{} b^3$. Prove that $ p^2\mid a \plus{} b$ or $ p^3\mid a^3 \plus{} b^3$.

2011 Morocco TST, 1

Tags: number theory , modular arithmetic , binomial coefficient , summation , divisibility

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

2010 Contests, 1

Tags: number theory , modular arithmetic

Find all $ 3$-digit numbers such that placing to the right side of the number its successor we get a $ 6$-digit number which is a perfect square.

2009 USA Team Selection Test, 8

Tags: calculus , number theory , modular arithmetic , polynomial , algebra

Fix a prime number $ p > 5$. Let $ a,b,c$ be integers no two of which have their difference divisible by $ p$. Let $ i,j,k$ be nonnegative integers such that $ i \plus{} j \plus{} k$ is divisible by $ p \minus{} 1$. Suppose that for all integers $ x$, the quantity \[ (x \minus{} a)(x \minus{} b)(x \minus{} c)[(x \minus{} a)^i(x \minus{} b)^j(x \minus{} c)^k \minus{} 1]\] is divisible by $ p$. Prove that each of $ i,j,k$ must be divisible by $ p \minus{} 1$. [i]Kiran Kedlaya and Peter Shor.[/i]

2011 China Team Selection Test, 2

Tags: number theory , modular arithmetic

Let $n>1$ be an integer, and let $k$ be the number of distinct prime divisors of $n$. Prove that there exists an integer $a$, $1<a<\frac{n}{k}+1$, such that $n \mid a^2-a$.

2007 IMO Shortlist, 7

Tags: number theory , modular arithmetic , prime factorization , factorial , combinatorial number theory

For a prime $ p$ and a given integer $ n$ let $ \nu_p(n)$ denote the exponent of $ p$ in the prime factorisation of $ n!$. Given $ d \in \mathbb{N}$ and $ \{p_1,p_2,\ldots,p_k\}$ a set of $ k$ primes, show that there are infinitely many positive integers $ n$ such that $ d\mid \nu_{p_i}(n)$ for all $ 1 \leq i \leq k$. [i]Author: Tejaswi Navilarekkallu, India[/i]

1969 IMO Longlists, 13

Tags: number theory , divisibility , additive number theory , modular arithmetic

$(CZS 2)$ Let $p$ be a prime odd number. Is it possible to find $p-1$ natural numbers $n + 1, n + 2, . . . , n + p -1$ such that the sum of the squares of these numbers is divisible by the sum of these numbers?