We say that a prime $p$ is $n$-$\textit{rephinado}$ if $n | p - 1$ and all $1, 2, \ldots , \lfloor \sqrt[\delta]{p}\rfloor$ are $n$-th residuals modulo $p$, where $\delta = \varphi+1$. Are there infinitely many $n$ for which there are infinitely many $n$-$\textit{rephinado}$ primes? Notes: $\varphi =\frac{1+\sqrt{5}}{2}$. We say that an integer $a$ is a $n$-th residue modulo $p$ if there is an integer $x$ such that $$x^n \equiv a \text{ (mod } p\text{)}.$$
Problem
Source: OlimphÃada 2023 - Problem 4/Level 3
Tags: floor function, prime numbers, Golden Ratio, residue, number theory
10.07.2023 09:40
This is somewhat funny. The answer is no. If, for certain $n$, there are infinitely many prime $p$ which is n-rephinado, then all the positive integer smaller than $p$ which is the product of some positive integers smaller than $p^{\frac{1}{\delta}}$ is a $n$-th power residue $\mathrm{mod}p$. It is well-known that there are exactly $\frac{p-1}{n}$ n-th power residues, so there are at least $\frac{\left(p-1\right)\left(n-1\right)}{n}$ positive integers (smaller than p) which have a prime divisor $\geq p^{\frac{1}{\delta}}$. Thus, $\frac{\left(p-1\right)\left(n-1\right)}{n}\leq p\sum\limits_{q\in \left[p^{\frac{1}{\delta},p}\right]}\frac{1}{q}=p\left(\mathrm{ln}p-\mathrm{ln}p^{\frac{1}{\delta}}+o\left(1\right)\right)=p\left(\mathrm{ln}\delta+o\left(1\right)\right)$. However, $\mathrm{ln}\delta\leq 0.999$, so for sufficiently large prime $p$, the above inequality rearranges to $\frac{n-1}{n}\leq 0.9995$, which gives an upper bound for $n$, finishing the proof.
11.01.2024 16:04
The answer is no. Suppose, FTSoC that there exists a $n$ satisfying the condition and let $p$ be a $n$-$\textit{rephinado}$ prime. It's known that we have $\frac{(p-1)(n-1)}{n}$ no $n$-th residues modulo $p$. Since $(\sqrt[\delta]{p})^2>p$, any integer in the interval $[1,p-1]$ has at most one prime greater than $\sqrt[\delta]{p}$. Furthermore, if $a$ and $b$ are $n$-th residues, then $ab$ is also one, and if exactly one of them is a $n$-th residue, then $ab$ is $\textbf{not}$ a $n$-th residue. We call $\textit{small primes}$, all primes smaller than $\sqrt[\delta]{p}$ and $\textit{big prime}$ otherwise.Thus, any non $n$-th residue is of the form $qM$, where $M$ is a product of $\textit{small primes}$ and $q$ a $\textit{big prime}$. (not all numbers of this form are non $n$-th residues, but all of those are of this form) Thus, if $S$ is the total number of non $n$-th residues. We know that $S=\frac{(p-1)(n-1)}{n}$. But also, we have $$S\leq\sum_{q\text{ is a }\textit{big prime}}\left\lfloor\frac{p}{q}\right\rfloor<p\cdot\sum_{q\text{ is a }\textit{big prime}}\frac{1}{q}.$$It is know that there exists a constant $C$ for which $$\lim_{n\to\infty}\left(\ln\ln{n}-\sum_{p<n}\frac{1}{p}\right)=C.$$Thus, we have $$\sum_{q\text{ is a }\textit{big prime}}=\ln\ln{p}+C+o(1)-\ln\ln{\sqrt[\delta]{p}}-C-o(1)=\ln{\delta}+o(1)$$and therefore we must have $$S\leq p\ln{\delta}\implies\frac{(p-1)(n-1)}{n}\leq p\ln{\delta}$$and by taking $n\to\infty$ we have $$1<\ln{\delta}\iff \delta>e,$$which is a contradiction. Thus, it follows that there is only a finite number of $n$ for which there exists infinite $n$-$\textit{rephined}$ primes.$\blacksquare$