Olympiad problems

2006 Baltic Way, 20

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$.

2014 Baltic Way, 16

Tags: modular arithmetic , number theory , number theory proposed

Determine whether $712! + 1$ is a prime number.

2014 Baltic Way, 18

Tags: symmetry , abstract algebra , modular arithmetic , number theory proposed , number theory

Let $p$ be a prime number, and let $n$ be a positive integer. Find the number of quadruples $(a_1, a_2, a_3, a_4)$ with $a_i\in \{0, 1, \ldots, p^n - 1\}$ for $i = 1, 2, 3, 4$, such that \[p^n \mid (a_1a_2 + a_3a_4 + 1).\]

2010 Turkey Team Selection Test, 1

Tags: modular arithmetic , number theory proposed , number theory

Let $0 \leq k < n$ be integers and $A=\{a \: : \: a \equiv k \pmod n \}.$ Find the smallest value of $n$ for which the expression \[ \frac{a^m+3^m}{a^2-3a+1} \] does not take any integer values for $(a,m) \in A \times \mathbb{Z^+}.$

2008 JBMO Shortlist, 12

Tags: algorithm , modular arithmetic , number theory proposed , number theory

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

2012 Iran MO (3rd Round), 5

Tags: modular arithmetic , number theory proposed , number theory

Let $p$ be a prime number. We know that each natural number can be written in the form \[\sum_{i=0}^{t}a_ip^i (t,a_i \in \mathbb N\cup \{0\},0\le a_i\le p-1)\] Uniquely. Now let $T$ be the set of all the sums of the form \[\sum_{i=0}^{\infty}a_ip^i (0\le a_i \le p-1).\] (This means to allow numbers with an infinite base $p$ representation). So numbers that for some $N\in \mathbb N$ all the coefficients $a_i, i\ge N$ are zero are natural numbers. (In fact we can consider members of $T$ as sequences $(a_0,a_1,a_2,...)$ for which $\forall_{i\in \mathbb N}: 0\le a_i \le p-1$.) Now we generalize addition and multiplication of natural numbers to this set so that it becomes a ring (it's not necessary to prove this fact). For example: $1+(\sum_{i=0}^{\infty} (p-1)p^i)=1+(p-1)+(p-1)p+(p-1)p^2+...$ $=p+(p-1)p+(p-1)p^2+...=p^2+(p-1)p^2+(p-1)p^3+...$ $=p^3+(p-1)p^3+...=...$ So in this sum, coefficients of all the numbers $p^k, k\in \mathbb N$ are zero, so this sum is zero and thus we can conclude that $\sum_{i=0}^{\infty}(p-1)p^i$ is playing the role of $-1$ (the additive inverse of $1$) in this ring. As an example of multiplication consider \[(1+p)(1+p+p^2+p^3+...)=1+2p+2p^2+\cdots\] Suppose $p$ is $1$ modulo $4$. Prove that there exists $x\in T$ such that $x^2+1=0$. [i]Proposed by Masoud Shafaei[/i]

2012 ELMO Shortlist, 5

Tags: modular arithmetic , number theory proposed , number theory

Let $n>2$ be a positive integer and let $p$ be a prime. Suppose that the nonzero integers are colored in $n$ colors. Let $a_1,a_2,\ldots,a_{n}$ be integers such that for all $1\le i\le n$, $p^i\nmid a_i$ and $p^{i-1}\mid a_i$. In terms of $n$, $p$, and $\{a_i\}_{i=1}^{n}$, determine if there must exist integers $x_1,x_2,\ldots,x_{n}$ of the same color such that $a_1x_1+a_2x_2+\cdots+a_{n}x_{n}=0$. [i]Ravi Jagadeesan.[/i]

2000 Iran MO (3rd Round), 1

Tags: number theory proposed , number theory

Does there exist a natural number $N$ which is a power of$2$, such that one can permute its decimal digits to obtain a different power of $2$?

2009 Junior Balkan MO, 2

Tags: number theory proposed , number theory

Solve in non-negative integers the equation $ 2^{a}3^{b} \plus{} 9 \equal{} c^{2}$

2013 Iran MO (3rd Round), 1

Tags: modular arithmetic , number theory , relatively prime , number theory proposed , Modular inverse , Multiplicative order

Let $p$ a prime number and $d$ a divisor of $p-1$. Find the product of elements in $\mathbb Z_p$ with order $d$. ($\mod p$). (10 points)

2007 Iran MO (3rd Round), 2

Tags: floor function , number theory proposed , number theory

We call the mapping $ \Delta:\mathbb Z\backslash\{0\}\longrightarrow\mathbb N$, a degree mapping if and only if for each $ a,b\in\mathbb Z$ such that $ b\neq0$ and $ b\not|a$ there exist integers $ r,s$ such that $ a \equal{} br\plus{}s$, and $ \Delta(s) <\Delta(b)$. a) Prove that the following mapping is a degree mapping: \[ \delta(n)\equal{}\mbox{Number of digits in the binary representation of }n\] b) Prove that there exist a degree mapping $ \Delta_{0}$ such that for each degree mapping $ \Delta$ and for each $ n\neq0$, $ \Delta_{0}(n)\leq\Delta(n)$. c) Prove that $ \delta \equal{}\Delta_{0}$ [img]http://i16.tinypic.com/4qntmd0.png[/img]

2006 All-Russian Olympiad, 5

Tags: number theory proposed , number theory

Let $a_1$, $a_2$, ..., $a_{10}$ be positive integers such that $a_1<a_2<...<a_{10}$. For every $k$, denote by $b_k$ the greatest divisor of $a_k$ such that $b_k<a_k$. Assume that $b_1>b_2>...>b_{10}$. Show that $a_{10}>500$.

2011 Costa Rica - Final Round, 5

Tags: number theory , relatively prime , number theory proposed

Given positive integers $a,b,c$ which are pairwise relatively prime, show that \[2abc-ab-bc-ac \] is the biggest number that can't be expressed in the form $xbc+yca+zab$ with $x,y,z$ being natural numbers.

2011 All-Russian Olympiad Regional Round, 9.7

Tags: number theory , prime numbers , number theory proposed

Find all prime numbers $p$, $q$ and $r$ such that the fourth power of any of them minus one is divisible by the product of the other two. (Author: V. Senderov)

2014 Germany Team Selection Test, 3

Tags: number theory proposed , number theory

Let $a_1 \leq a_2 \leq \cdots$ be a non-decreasing sequence of positive integers. A positive integer $n$ is called [i]good[/i] if there is an index $i$ such that $n=\dfrac{i}{a_i}$. Prove that if $2013$ is [i]good[/i], then so is $20$.

2024 Austrian MO National Competition, 4

Tags: number theory , number theory proposed , powerful numbers

A positive integer is called [i]powerful [/i]if all exponents in its prime factorization are $\ge 2$. Prove that there are infinitely many pairs of powerful consecutive positive integers. [i](Walther Janous)[/i]

2011 Singapore MO Open, 4

Tags: algebra , polynomial , calculus , number theory proposed , number theory

Find all polynomials $P(x)$ with real coefficients such that \[P(a)\in\mathbb{Z}\ \ \ \text{implies that}\ \ \ a\in\mathbb{Z}.\]

1999 Balkan MO, 2

Tags: number theory proposed , number theory

Let $p$ be an odd prime congruent to 2 modulo 3. Prove that at most $p-1$ members of the set $\{m^2 - n^3 - 1 \mid 0 < m,\ n < p\}$ are divisible by $p$.

1993 IberoAmerican, 3

Tags: modular arithmetic , number theory proposed , number theory

Two nonnegative integers $a$ and $b$ are [i]tuanis[/i] if the decimal expression of $a+b$ contains only $0$ and $1$ as digits. Let $A$ and $B$ be two infinite sets of non negative integers such that $B$ is the set of all the [i]tuanis[/i] numbers to elements of the set $A$ and $A$ the set of all the [i]tuanis[/i] numbers to elements of the set $B$. Show that in at least one of the sets $A$ and $B$ there is an infinite number of pairs $(x,y)$ such that $x-y=1$.

2009 China Team Selection Test, 3

Tags: modular arithmetic , inequalities , number theory proposed , number theory

Prove that for any odd prime number $ p,$ the number of positive integer $ n$ satisfying $ p|n! \plus{} 1$ is less than or equal to $ cp^\frac{2}{3}.$ where $ c$ is a constant independent of $ p.$

1996 Brazil National Olympiad, 1

Tags: algorithm , number theory proposed , number theory

Show that there exists infinite triples $(x,y,z) \in N^3$ such that $x^2+y^2+z^2=3xyz$.

1990 Iran MO (2nd round), 2

Tags: number theory proposed , number theory

Find all integer solutions to the equation \[(x^2-x)(x^2-2x+2)=y^2-1\]

2012 Vietnam National Olympiad, 2

Tags: induction , algebra , system of equations , number theory proposed , number theory

Consider two odd natural numbers $a$ and $b$ where $a$ is a divisor of $b^2+2$ and $b$ is a divisor of $a^2+2.$ Prove that $a$ and $b$ are the terms of the series of natural numbers $\langle v_n\rangle$ defined by \[v_1 = v_2 = 1; v_n = 4v_ {n-1}-v_{n-2} \ \ \text{for} \ n\geq 3.\]

2014 ELMO Shortlist, 10

Tags: geometry , 3D geometry , modular arithmetic , number theory proposed , number theory

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]

2013 Cono Sur Olympiad, 5

Tags: number theory proposed , number theory

Let $d(k)$ be the number of positive divisors of integer $k$. A number $n$ is called [i]balanced[/i] if $d(n-1) \leq d(n) \leq d(n+1)$ or $d(n-1) \geq d(n) \geq d(n+1)$. Show that there are infinitely many balanced numbers.