Olympiad problems

2018 China Team Selection Test, 4

Let $p$ be a prime and $k$ be a positive integer. Set $S$ contains all positive integers $a$ satisfying $1\le a \le p-1$, and there exists positive integer $x$ such that $x^k\equiv a \pmod p$. Suppose that $3\le |S| \le p-2$. Prove that the elements of $S$, when arranged in increasing order, does not form an arithmetic progression.

2023 Indonesia TST, N

Tags: number theory , primitive root , fermat's little theorem

Let $p,q,r$ be primes such that for all positive integer $n$, $$n^{pqr}\equiv n (\mod{pqr})$$ Prove that this happens if and only if $p,q,r$ are pairwise distinct and $LCM(p-1,q-1,r-1)|pqr-1$

2016 Korea Summer Program Practice Test, 3

Tags: number theory , prime number , prime , primitive root , decimal representation

Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$.

2014 Taiwan TST Round 3, 2

Tags: modular arithmetic , relatively prime , primitive root , number theory

Alice and Bob play the following game. They alternate selecting distinct nonzero digits (from $1$ to $9$) until they have chosen seven such digits, and then consider the resulting seven-digit number by concatenating the digits in the order selected, with the seventh digit appearing last (i.e. $\overline{A_1B_2A_3B_4A_6B_6A_7}$). Alice wins if and only if the resulting number is the last seven decimal digits of some perfect seventh power. Please determine which player has the winning strategy.

PEN B Problems, 3

Tags: modular arithmetic , primitive root

Show that for each odd prime $p$, there is an integer $g$ such that $1<g<p$ and $g$ is a primitive root modulo $p^n$ for every positive integer $n$.

PEN B Problems, 7

Tags: algebra , polynomial , modular arithmetic , primitive root

Suppose that $p>3$ is prime. Prove that the products of the primitive roots of $p$ between $1$ and $p-1$ is congruent to $1$ modulo $p$.

2019 Belarus Team Selection Test, 2.3

Tags: number theory , primitive root , combinatorics

$1019$ stones are placed into two non-empty boxes. Each second Alex chooses a box with an even amount of stones and shifts half of these stones into another box. Prove that for each $k$, $1\le k\le1018$, at some moment there will be a box with exactly $k$ stones. [i](O. Izhboldin)[/i]

2022 Chile TST IMO, 3

Tags: order , number theory , primitive root

Let $n$ be a natural number with more than $2021$ digits, none of which are $8$ or $9$. Suppose that $n$ has no common factors with $2021$. Prove that it is possible to increase one of the digits of $n$ by at most $2$ so that the resulting number is a multiple of 2021.

2015 IFYM, Sozopol, 5

Tags: number theory , primitive root

Let $p>3$ be a prime number. Prove that the product of all primitive roots between 1 and $p-1$ is congruent 1 modulo $p$.

2023 Indonesia TST, N

Tags: number theory , primitive root , fermat's little theorem

Let $p,q,r$ be primes such that for all positive integer $n$, $$n^{pqr}\equiv n (\mod{pqr})$$ Prove that this happens if and only if $p,q,r$ are pairwise distinct and $LCM(p-1,q-1,r-1)|pqr-1$

2016 Croatia Team Selection Test, Problem 4

Tags: number theory , prime number , prime , primitive root , decimal representation

Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$.

PEN B Problems, 1

Tags: quadratic , modular arithmetic , primitive root

Let $n$ be a positive integer. Show that there are infinitely many primes $p$ such that the smallest positive primitive root of $p$ is greater than $n$.

2018 China Team Selection Test, 4

Tags: modular arithmetic , arithmetic sequence , number theory , primitive root , sum of powers

Let $p$ be a prime and $k$ be a positive integer. Set $S$ contains all positive integers $a$ satisfying $1\le a \le p-1$, and there exists positive integer $x$ such that $x^k\equiv a \pmod p$. Suppose that $3\le |S| \le p-2$. Prove that the elements of $S$, when arranged in increasing order, does not form an arithmetic progression.

2016 Croatia Team Selection Test, Problem 4

Tags: prime number , prime , primitive root , decimal representation , number theory

Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$.

PEN B Problems, 6

Tags: modular arithmetic , number theory , relatively prime , primitive root

Suppose that $m$ does not have a primitive root. Show that \[a^{ \frac{\phi(m)}{2}}\equiv 1 \; \pmod{m}\] for every $a$ relatively prime $m$.

2017 Silk Road, 4

Tags: silk way , number theory , primitive root

Prove that for each prime $ P =9k+1$ ,exist natural n such that $P|n^3-3n+1$.

2016 Romanian Master of Mathematics Shortlist, N1

Tags: primitive root , quadratic residue , number theory

Determine all integers $n \ge 3$ whose decimal expansion has less than $20$ digits, such that every quadratic non-residue modulo $n$ is a primitive root modulo $n$. [i]An integer $a$ is a quadratic non-residue modulo $n$, if there is no integer $b$ such that $a - b^2$ is divisible by $n$. An integer $a$ is a primitive root modulo $n$, if for every integer $b$ relatively prime to n there is a positive integer $k$ such that $a^k - b$ is divisible by $n$.[/i]

2024 Thailand October Camp, 3

Tags: number theory , primitive root

Recall that for an arbitrary prime $p$, we define a [b]primitive root[/b] modulo $p$ as an integer $r$ for which the least positive integer $v$ such that $r^{v}\equiv 1\pmod{p}$ is $p-1$.\\ Prove or disprove the following statement: [center] For every prime $p>2023$, there exists positive integers $1\leqslant a<b<c<p$\\ such that $a,b$ and $c$ are primitive roots modulo $p$ but $abc$ is not a primitive root modulo $p$. [/center]

PEN B Problems, 4

Tags: modular arithmetic , primitive root

Let $g$ be a Fibonacci primitive root $\pmod{p}$. i.e. $g$ is a primitive root $\pmod{p}$ satisfying $g^2 \equiv g+1\; \pmod{p}$. Prove that [list=a] [*] $g-1$ is also a primitive root $\pmod{p}$. [*] if $p=4k+3$ then $(g-1)^{2k+3} \equiv g-2 \pmod{p}$, and deduce that $g-2$ is also a primitive root $\pmod{p}$. [/list]