Olympiad problems

2019 Tournament Of Towns, 7

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$. (Ilke Chanakchi, Ralf Schiffler)

2021 Saudi Arabia IMO TST, 2

Tags: perfect number , phi function , power of 2 , number theory

Find all positive integers $n$, such that $n$ is a perfect number and $\varphi (n)$ is power of $2$. [i]Note:a positive integer $n$, is called perfect if the sum of all its positive divisors is equal to $2n$.[/i]

2020 Peru Cono Sur TST., P4

Tags: phi function , euler s phi function , perfect square , number theory

Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.

2003 Kurschak Competition, 3

Tags: phi function , analytic number theory , expected value , probabilistic method , summation , number theory , inequalities

Prove that the following inequality holds with the exception of finitely many positive integers $n$: \[\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)>4n^2.\]

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.

2023 OMpD, 3

Tags: euler s totient function , phi function , parity , number theory

For each positive integer $x$, let $\varphi(x)$ be the number of integers $1 \leq k \leq x$ that do not have prime factors in common with $x$. Determine all positive integers $n$ such that there are distinct positive integers $a_1,a_2, \ldots, a_n$ so that the set: $$S = \{a_1, a_2, \ldots, a_n, \varphi(a_1), \varphi(a_2), \ldots, \varphi(a_n)\}$$ Have exactly $2n$ consecutive integers (in some order).

2008 Brazil Team Selection Test, 4

Tags: perfect square , phi function , euler s phi function , number theory

Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.

2020 Peru Iberoamerican Team Selection Test, P4

Tags: number theory , perfect square , phi function , euler s phi function

Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.

Kvant 2019, M2561

Tags: phi function , combinatorics

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$. (Ilke Chanakchi, Ralf Schiffler)

2024 Turkey Olympic Revenge, 5

Tags: number theory , phi function , sigma function

Let $a$ be a positive real number. Prove that a) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} > a$. b) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} < a$. (As usual, $\sigma(n) = \sum_{d\mid n} d$ and $\varphi(n)$ is the number of integers $1\le m\le n$ which are coprime with $n$.) Proposed by [i]Deniz Can Karaçelebi[/i]

2024 Girls in Mathematics Tournament, 4

Tags: phi function , number theory

Find all integers $a$ such that there are infinitely many positive integers $n$ such that $n$ divides $\phi(n)!+a$.

2022 Vietnam TST, 1

Tags: functional equation , phi function , function , algebra

Given a real number $\alpha$ and consider function $\varphi(x)=x^2e^{\alpha x}$ for $x\in\mathbb R$. Find all function $f:\mathbb R\to\mathbb R$ that satisfy: $$f(\varphi(x)+f(y))=y+\varphi(f(x))$$ forall $x,y\in\mathbb R$

2016 Balkan MO Shortlist, N1

Tags: coprime , phi function , number theory

Find all natural numbers $n$ for which $1^{\phi (n)} + 2^{\phi (n)} +... + n^{\phi (n)}$ is coprime with $n$.

VMEO III 2006 Shortlist, N10

Tags: number theory , phi function , inequalities

The notation $\phi (n)$ is the number of positive integers smaller than $n$ and coprime with $n$, $\pi (n)$ is the number of primes that do not exceed $n$. Prove that for any natural number $n > 1$, we have $$\phi (n) \ge \frac{\pi (n)}{2}$$

2022 Durer Math Competition Finals, 1

Tags: number theory , euler s phi function , phi function , sequence

Let $c \ge 2$ be a fixed integer. Let $a_1 = c$ and for all $n \ge 2$ let $a_n = c \cdot \phi (a_{n-1})$. What are the numbers $c$ for which sequence $(a_n)$ will be bounded? $\phi$ denotes Euler’s Phi Function, meaning that $\phi (n)$ gives the number of integers within the set $\{1, 2, . . . , n\}$ that are relative primes to $n$. We call a sequence $(x_n)$ bounded if there exist a constant $D$ such that $|x_n| < D$ for all positive integers $n$.

2021 Vietnam National Olympiad, 4

Tags: number theory , sum , phi function

For an integer $ n \geq 2 $, let $ s (n) $ be the sum of positive integers not exceeding $ n $ and not relatively prime to $ n $. a) Prove that $ s (n) = \dfrac {n} {2} \left (n + 1- \varphi (n) \right) $, where $ \varphi (n) $ is the number of integers positive cannot exceed $ n $ and are relatively prime to $ n $. b) Prove that there is no integer $ n \geq 2 $ such that $ s (n) = s (n + 2021) $

2024 Brazil Team Selection Test, 1

Tags: number theory , phi function , coprime

Given an integer $n > 1$, let $1 = a_1 < a_2 < \cdots < a_t = n - 1$ be all positive integers less than $n$ that are coprime to $n$. Find all $n$ such that there is no $i \in \{1, 2, \ldots , t - 1\}$ satisfying $3 | a_i + a_{i+1}$.

2022 Serbia National Math Olympiad, P4

Tags: inequalities , phi function , number theory

Let $f(n)$ be number of numbers $x \in \{1,2,\cdots ,n\}$, $n\in\mathbb{N}$, such that $gcd(x, n)$ is either $1$ or prime. Prove $$\sum_{d|n} f(d) + \varphi(n) \geq 2n$$ For which $n$ does equality hold?