Olympiad problems

2016 Korea Summer Program Practice Test, 3

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, 4

Tags: primitive root , modular arithmetic

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]

2017 Silk Road, 4

Tags: primitive root , silk way , number theory

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

PEN B Problems, 3

Tags: primitive root , modular arithmetic

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

2022 Chile TST IMO, 3

Tags: order , primitive root , number theory

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.

2014 Taiwan TST Round 3, 2

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

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.

2016 Croatia Team Selection Test, Problem 4

Tags: decimal representation , prime number , prime , primitive root , 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$.

2015 IFYM, Sozopol, 5

Tags: primitive root , number theory

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: decimal representation , prime , prime number , primitive root , 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$.

2018 China Team Selection Test, 4

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

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.

2024 Thailand October Camp, 3

Tags: primitive root , number theory

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]

2023 Indonesia TST, N

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

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$

2018 China Team Selection Test, 4

Tags: number theory , modular arithmetic , arithmetic sequence , 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.

PEN B Problems, 1

Tags: modular arithmetic , primitive root , quadratic

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

PEN B Problems, 6

Tags: relatively prime , number theory , modular arithmetic , 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$.

2019 Belarus Team Selection Test, 2.3

Tags: number theory , combinatorics , primitive root

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

2016 Romanian Master of Mathematics Shortlist, N1

Tags: number theory , quadratic residue , primitive root

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]

PEN B Problems, 7

Tags: algebra , modular arithmetic , polynomial , 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$.